Используя средства текстового процессора изобразите двоичное дерево соответствующее этому коду
Кодирование - это перевод информации с одного языка, в последовательность кодов. Для удобства ее хранения, передачи и обработки.
При вводе в компьютер информации, происходит ее двоичное кодирование. Информация может быть текстовая, графическая, звуковая. Код символа хранится в оперативной памяти компьютера. В процессе вывода символа на экран производится обратная операция — декодирование , т. е. преобразование кода символа в его изображение, символ или звук.
Декодирование - процесс обратный кодированию, т.е. расшифровка кодов.
Кодирование информации может быть равномерным и неравномерным.
При равномерном кодировании каждому символу соответствует код одинаковой длины.
При неравномерном кодировании различным символам могут соответствовать коды различной длины.
Представление двоичного дерева
Узел двоичного дерева можно представить структурой, содержащей данные и два указателя на другие структуры того же типа.
Тема: Кодирование и декодирование информации.
Что нужно знать:
· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)
· обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход
· кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование
· условие Фано – это достаточное, но не необходимое условие однозначного декодирования.
Вставка элемента
Сложность в среднем: O(log n)
Сложность в худшем случае: ΘO(n)
Операция вставки значения похожа на поиск элемента. Мы также придерживаемся правила: левое поддерево меньше корня, правое поддерево — больше.
Мы продолжаем переходить либо к правому поддереву, либо к левому поддереву в зависимости от значения узла, и когда достигаем точки, в которой левое или правое поддерево имеет значение NULL, помещаем туда новый узел.
Алгоритм:
Алгоритм не такой простой, как может показаться на первый взгляд. Давайте визуализируем процесс.
• 4 > 3 → идем через правого «ребенка» 3.
• Левого «ребенка» у 6 нет → вставляем 4 как левый дочерний элемент 6.
Мы вставили узел в нужное место, но нам всё еще нужно выйти из функции, не повредив при этом остальную часть дерева. Здесь пригодится return node; . В случае с NULL , вновь созданный узел возвращается и присоединяется к родительскому узлу, иначе тот же узел возвращается без каких-либо изменений по мере продвижения вверх, пока мы не вернемся к корню.
Таким образом, когда мы будем двигаться обратно вверх по дереву, связи других узлов не изменятся.
Корень возвращаем в конце — так ничего не сломается.
Пример задания:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Б – 01 2) это невозможно
3) для буквы В – 01 4) для буквы Г – 01
Решение (1 способ, проверка условий Фано):
1) для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано;
2) проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);
3) проверяем вариант 1: А–00, Б– 01 , В–011, Г–101, Д–111.
«прямое» условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В);
«обратное» условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит ;
4) проверяем вариант 3: А–00, Б–010, В– 01 , Г–101, Д–111.
«прямое» условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б);
«обратное» условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит ;
5) проверяем вариант 4: А–00, Б–010, В–011, Г– 01 , Д–111.
«прямое» условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит ;
6) правильный ответ – 4 .
Решение (2 способ, дерево):
1) построим двоичное дерево, в котором от каждого узла отходит две ветки, соответствующие выбору следующей цифры кода – 0 или 1; разместим на этом дереве буквы А, Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах, составляющих путь от корня до данной буквы (красным цветом выделен код буквы В – 011):
2) здесь однозначность декодирования получается за счёт того, что при движении от корня к любой букве в середине пути не встречается других букв (выполняется условие Фано);
3) теперь проверим варианты ответа: предлагается перенести одну из букв, Б, В или Г, в узел с кодом 01, выделенный синим цветом
4) видим, что при переносе любой из этих букв нарушится условие Фано; например, при переносе буквы Б в синий узел она оказывается на пути от корня до В, и т.д.; это значит, что предлагаемые варианты не позволяют выполнить прямое условие Фано
5) хочется уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца):
видно, что обратное условие Фано также выполняется, потому что на пути от корня к любой букве нет других букв
6) в заданных вариантах ответа предлагается переместить букву Б, В или Г в синий узел; понятно, что Б или В туда перемещать нельзя – перемещённая буква отказывается на пути от корня к букве Г; а вот букву Г переместить можно, при этом обратное условие Фано сохранится
7) правильный ответ – 4 .
Типы двоичных деревьев
Полное двоичное дерево
Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.
Совершенное двоичное дерево
Совершенное двоичное дерево — особый тип бинарного дерева, в котором у каждого внутреннего узла по два ребенка, а листовые вершины находятся на одном уровне.
Законченное двоичное дерево
Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.
- Все уровни должны быть заполнены.
- Все листовые вершины склоняются влево.
- У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.
Вырожденное двоичное дерево
Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.
Скошенное вырожденное дерево
Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.
Сбалансированное двоичное дерево
Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.
Еще пример задания:
Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится
14) из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный
15) последовательность БАВГ кодируется так: 01 00 10 11 = 1001011
16) разобьем такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем
1001011 = 0100 10112 = 4B 16
17) правильный ответ – 1.
Возможные ловушки :
· расчет на то, что при переводе тетрад в шестнадцатеричную систему можно забыть заменить большие числа (10–15) на буквы (10112 = 11, получаем неверный ответ 41116)
· может быть дан неверный ответ, в котором нужные цифры поменяли местами (расчет на невнимательность), например, B 416
· в ответах дана последовательность, напоминающая исходную (неверный ответ BACD 16), чтобы сбить случайное угадывание
Еще пример задания:
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Дерево двоичного поиска — это структура данных, которая позволяет быстро работать с отсортированном списком чисел.
- Дерево двоичное, потому что у каждого узла не более двух дочерних элементов.
- Дерево поиска, потому что его можно использовать для проверки вхождения числа — за время O(log(n)) .
Чем отличается от обычного двоичного дерева
- Все узлы левого поддерева меньше корневого узла.
- Все узлы правого поддерева больше корневого узла.
- Оба поддерева каждого узла тоже являются деревьями двоичного поиска, т. е. также обладают первыми двумя свойствами.
У правого дерева есть поддерево со значением 2, которое меньше, чем корень 3 — таким дерево двоичного поиска быть не может.
Удаление элемента
Сложность в среднем: O(log n)
Сложность в худшем случае: O(n)
Всего может быть три случая при удаление элемента из дерева двоичного поиска. Давайте рассмотрим каждый.
Случай I: лист
Первый случай — когда нужно удалить листовой элемент. Просто удаляем узел из дерева.
• Нужно удалить 4.
• Просто удалили узел.
Случай II: есть дочерний элемент
Во втором случае у узла, который мы хотим удалить, есть один дочерний узел. В этом случае действуем так:
Операции с двоичным деревом поиска
Поиск элемента
Сложность в среднем: O(log n)
Сложность в худшем случае: O(n)
Алгоритм зависит от свойств дерева: у каждого левого поддерева есть значения, которые ниже корня или у каждого правого поддерева есть значения, которые выше корня.
Если значение ниже корня, мы можем точно сказать, что оно находится не в правильном поддереве. Тогда нам нужно искать только в левом поддереве. А если значение выше корня, можно точно сказать, что значения нет в левом поддереве. Тогда ищем только в правом поддереве.
Алгоритм:
Изобразим это на диаграмме.
• Не нашли 4 → идем по левому поддереву корня 8
• Не нашли 4 → идем по левому поддереву корня 3
• Не нашли 4 → идем по левому поддереву корня 6
Если мы нашли значение, мы возвращаем его так, чтобы оно распространялось на каждом шаге рекурсии — рассмотрите рисунок ниже.
Как вы могли заметить, мы четыре раза вызывали search(struct node*) . Когда мы возвращаем новый узел или NULL , значение возвращается снова и снова, пока search(root) не вернет окончательный результат.
Если мы не нашли значение, значит, мы достигли левого или правого дочернего элемента листового узла, который имеет значение NULL — это значение также рекурсивно распространяется и возвращается.
Ещё пример задания:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.
1) 00 2) 01 3)11 4) 010
8) заметим, что для известной части кода выполняется условие Фано – никакое кодовое слово не является началом другого кодового слова
9) если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому первый вариант не подходит
10) если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит
11) если Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит
12) для четвертого варианта, Д = 010, условие Фано не нарушено;
13) правильный ответ – 4 .
Возможные ловушки :
· условие Фано – это достаточное, но не необходимое условие однозначного декодирования, поэтому для уверенности полезно найти для всех «неправильных» вариантов контрпримеры: цепочки, для которых однозначное декодирование невозможно
Условие Фано
Например пара кодовых слов 10 и 101 не выполняют условие Фано, потому что 101 является началом 10. А вот 100 и 101 уже выполняют условие Фано.
В конце статьи мы разберем задание в котором нужно найти кодовое слово для буквы удовлетворяющее условию Фано. На примере часто бывает проще разобраться!
Код который удовлетворяет условию Фано, называется префиксным . Префиксный код однозначно декодируется с начала.
Бинарное дерево на рисунке построено до значений из таблицы триад, можно продолжить строить дерево, но принцип я думаю понятен.
Укажите кратчайшее возможное кодовое слово для буквы Н , при котором код будет удовлетворять указанному условию. Если таких кодов несколько, то укажите код с наименьшим числовым значением.
В тех местах где мы находим кодовые слова букв которые нам уже известны, ветка дерева обрывается. Если мы продолжим ее строить, то коды которые будем получать дальше не будут удовлетворять условию Фано.
Если вы уже знакомились с Разбором демоверсии 2021 и делали это внимательно, то вы заметите, что данная задача очень похожа на №4. Я вам предлагаю решить четвертый номер из демоверсии, будьте внимательны, там есть подвох!
А свои ответы и разборы можете писать в комментариях. И не забывайте подписываться, чтобы не пропустить новые статьи!
Используя средства текстового процессора, изобразите двоичное дерево, соответствующее этому коду.
2. Выполняется ли для этой кодовой таблицы условие Фано? Обратное условие Фано? Почему?
Проверьте свой ответ с помощью программы decode.
4. Замените код одного символа так, чтобы выполнилось условие Фано (или обратное условие Фано). Выделите зеленым фоном ячейку таблицы с измененным кодом символа.
5. Сократите код одного символа в таблице, полученной в п. 4 так, чтобы условие Фано (или обратное условие Фано) по-прежнему выполнялось. Выделите фиолетовым фоном ячейку таблицы с измененным кодом символа.
Практическая работа № 6 «Необычные системы счисления»
1. Найдите в Интернете информацию о факториальной системе счисления. Для этого можно использовать веб-страницы
2. Переведите в десятичную систему числа, записанные в факториальной системе
3. Переведите числа из десятичной системы счисления в факториальную :
4. Найдите в Интернете информацию о фибоначчиевой системе счисления. Для этого можно использовать веб-страницы
5. Переведите в десятичную систему числа, записанные в фибоначчиевой системе
6. Найдите все способы перевода следующих чисел из десятичной системы счисления в фибоначчиеву:
© 2014-2022 — Студопедия.Нет — Информационный студенческий ресурс. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав (0.007)
Двоичное дерево — древовидная структура данных, в которой у родительских узлов не может быть больше двух детей.
Читайте также: