Построение двоичного дерева

Ранее мы уже познакомились с тем, как и в каком виде информация хранится в компьютере, как происходят процессы кодирования и декодирования. В прошлой статье мы также затронули тему распределения кодовых слов по буквам. А чтобы делать это наглядно, необходимо научиться правильно строить двоичные деревья.

В этой статье мы познакомимся с понятием структуры данных и разберём, зачем вообще нужны такие особые способы организации информации. Мы посмотрим на примеры, а затем подробно остановимся на структуре данных «дерево» и её разновидности – двоичном дереве.

Двоичные деревья встречаются во многих областях: от сжатия данных и построения кодов до поиска информации и работы баз данных. В задании 4 ЕГЭ дерево удобно использовать как наглядную модель кодовых слов. Мы разберём основные понятия: корень, узлы, листья и уровни.

А ещё научимся строить двоичные деревья для префиксных и постфиксных кодов. Это позволит уверенно решать задания и лучше понимать, как устроено двоичное кодирование.

Эта тема не только для экзамена – она помогает взглянуть на компьютерные задачи иначе и увидеть, что за сухими нулями и единицами скрывается настоящая логика и красота структур.

Структуры данных

Прежде чем углубляться в деревья, нужно понять, что вообще такое структура данных. Если сказать просто, структура данных – это способ организации и хранения информации в памяти компьютера.

Представьте, что у вас есть список дел на день. Вы можете записать его на стикере столбиком (как список), можете разложить каждое дело по папкам (как дерево), а можете составить таблицу с временем и приоритетами (как массив или матрица). Информация вроде бы одна и та же, но от того, как вы её организуете, зависит, насколько быстро и удобно вы сможете ей пользоваться.

В информатике всё то же самое. Например:

• если нужно быстро находить элемент по номеру, используют массивы;
• если важен порядок добавления и удаления элементов, удобнее всего стек или очередь;
• если нужно хранить данные в виде «кто с кем связан», лучше подходит граф;
• а когда данные имеют иерархическую структуру (например, папки на компьютере, где одна вложена в другую), здесь идеально работает дерево.

Каждая структура данных решает свою задачу. А выбор неправильной структуры может привести к тому, что программа будет работать медленно или займёт слишком много памяти.

В ЕГЭ по информатике нам предстоит работать с разными структурами данных. Например, в задании 3 мы работаем с таблицами, в задании 1 – с графами, а в задании 17 – с последовательностями чисел. В задании 4 нам на выручку придут деревья. Если быть точнее, двоичные деревья.

Двоичные деревья

Деревья в программировании – это структуры данных, которые представляют собой иерархическую организацию элементов. Такая структура напоминает перевёрнутое дерево из реального мира: вверху находится корень, от него отходят ветви, а на концах находятся листья. Каждый элемент дерева называется узлом, и у него могут быть дочерние элементы (потомки).

Главная особенность дерева в том, что у каждого узла (кроме корня) есть ровно один «родитель», но при этом потомков может быть сколько угодно (зависит от типа дерева). Благодаря этому деревья позволяют хранить информацию в виде строгой иерархии.

Например, структура папок на компьютере: у каждой папки может быть вложено несколько других, но у вложенной папки всегда есть только одна «родительская» папка.

Деревья активно применяются в самых разных задачах: для поиска и сортировки данных, для представления выражений в математике и программировании, для обработки графов, в файловых системах, в компиляторах и даже в базах данных.

Выглядят деревья следующим образом:

Чтобы лучше понимать работу деревьев, нужно разобраться с основными понятиями:

• Узел дерева – это основная структурная единица, представляющая собой точку соединения ветвей. Узлы могут содержать данные и ссылки на другие узлы. На изображении узлы обозначены латинскими буквами.
• Корень – А – начальный узел дерева. Это основа для построения всей структуры. Корень является предком всех остальных узлов и сам не имеет предков.
• Лист – узел, который не имеет потомков. Листовые узлы представляют конечные точки или результаты обработки данных. Они являются терминальными элементами дерева. На изображении листами являются узлы E, F, G и H.
• Ветви, или рёбра, – связи между узлами. Они изображаются линиями или стрелками и позволяют переходить от одного узла к другому. На рисунке ветви обозначены синим цветом.
• Уровень, или глубина, узла отсчитывается от корня. Корень находится на уровне 0, его дети – на уровне 1 и так далее. Например, у узла B глубина равна 1, а у узла H – 3.
• Высота дерева – максимальная глубина его узлов, то есть наибольшее число рёбер на пути от корня до листа. На рисунке высота дерева равна 3.

Деревья делятся на разные виды: бывают n-арные деревья, где у каждого узла может быть до n потомков, бывают сбалансированные и несбалансированные деревья, где важна форма и глубина.

Но в рамках задачи ЕГЭ мы будем использовать двоичные деревья, у которых каждый узел может иметь не более двух дочерних узлов.

Такое дерево удобно для представления информации в двоичной системе: левую ветвь условно называют «нулевой», а правую – «единичной». Это сразу связывает дерево с двоичным кодированием, ведь каждый путь от корня до листа можно интерпретировать как последовательность нулей и единиц.

Давайте построим простейшее двоичное дерево. Корень в этом случае не несёт собственного значения – он играет роль отправной точки.

От него отходят две ветви: слева ветвь с меткой «0», справа – ветвь с меткой «1».

На первом уровне появляются узлы «0» и «1». На втором – «00» и «01» под нулевой ветвью, а также «10» и «11» под единичной.

На следующем уровне добавляем ещё один символ: если ветвь идёт налево, то к коду добавляется ноль, если направо – единица.

В итоге получаем такое дерево:

Здесь мы дописывали новые значения в конец (нули оранжевым цветом, единицы – зелёным). Такое дерево подходит для работы с префиксным кодом (условием Фано).

При решении задания 4 ЕГЭ по информатике мы можем строить только нужную часть дерева – в зависимости от кодовых слов, данных в условии.

Теперь предположим, что рассматриваем ветвь, начинающуюся с единицы, и код «110» уже занят. Проверим, какие другие коды нельзя использовать по условию Фано.

Начнём с кодов, которые нам не подходят. Это все коды, начинающиеся с «110», то есть потомки этого узла: «1100», «1101» и так далее.

Не подходят и узлы-предки: «11» и «1», потому что каждый из этих кодов является началом кода «110». Все неподходящие коды выделены на рисунке оранжевым цветом, а подходящие – зелёным.

Теперь построим дерево, в котором новый знак дописывается в начало кода. Такое дерево подходит для работы с постфиксными кодами, то есть с обратным условием Фано.

Таким же образом найдём коды, не удовлетворяющие обратному условию Фано, если уже использован код «010». Нам не подходят все коды, оканчивающиеся на «010»: его потомки «0010» и «1010», а также предки «10» и «0».

Именно по такому алгоритму мы будем строить двоичные деревья и находить недостающие коды для букв в задании 4 ЕГЭ по информатике. Об этом и поговорим в следующей статье.