Ранее мы уже познакомились с тем, как и в каком виде информация хранится в компьютере, как происходят процессы кодирования и декодирования информации. В прошлой статье мы также затронули тему распределения кодовых слов по буквам. А для того, чтобы это сделать, необходимо научиться правильно строить двоичные деревья.
В этой статье мы познакомимся с понятием структуры данных и разберём, зачем вообще нужны такие особые способы организации информации. Мы посмотрим на примеры, а затем подробно остановимся на структуре данных «дерево» и её разновидности – двоичном дереве.
Двоичные деревья встречаются повсюду: от сжатия данных и построения кодировок до поиска информации и работы баз данных. Именно поэтому они часто попадаются в задании 4 ЕГЭ по информатике. Мы разберём все основные понятия, связанные с деревьями: корень, вершины, листья, уровни.
А ещё научимся строить двоичные деревья с префиксным и постфиксным кодом, что позволит уверенно решать задания и лучше понимать, как устроены алгоритмы работы с информацией.
Эта тема не только для экзамена – она помогает взглянуть на компьютерные задачи иначе и увидеть, что за сухими нулями и единицами скрывается настоящая логика и красота структур.
Структуры данных
Прежде чем углубляться в деревья, нужно понять, что вообще такое структура данных. Если сказать просто, структура данных – это способ организации и хранения информации в памяти компьютера.
Представьте, что у вас есть список дел на день. Вы можете записать его на стикере столбиком (как список), можете разложить каждое дело по папкам (как дерево), а можете составить таблицу с временем и приоритетами (как массив или матрица). Информация вроде бы одна и та же, но от того, как вы её организуете, зависит, насколько быстро и удобно вы сможете ей пользоваться.
В информатике всё то же самое. Например:
- если нужно быстро находить элемент по номеру, используют массивы;
- если важен порядок добавления и удаления элементов, удобнее всего стек или очередь;
- если нужно хранить данные в виде «кто с кем связан», лучше подходит граф;
- а когда данные имеют иерархическую структуру (например, папки на компьютере, где одна вложена в другую), здесь идеально работает дерево.
Каждая структура данных решает свою задачу. А выбор неправильной структуры может привести к тому, что программа будет работать медленно или займёт слишком много памяти.
В ЕГЭ по информатике нам предстоит работать с разными структурами данных. Например, в задании 3 мы будем работать с таблицами, в задании 1 у нас будут графы, в файлах 17 задания – списки из чисел. Ну а в 4 задании, которому и будут посвящены следующие статьи, нам на выручку придут деревья. Если быть точнее, то двоичные деревья.
Двоичные деревья
Деревья в программировании – это структуры данных, которые представляют собой иерархическую организацию элементов. Такая структура напоминает перевёрнутое дерево из реального мира: вверху находится корень, от него отходят ветви, а на концах находятся листья. Каждый элемент дерева называется узлом, и у него могут быть дочерние элементы (потомки).
Главная особенность дерева в том, что у каждого узла (кроме корня) есть ровно один «родитель», но при этом потомков может быть сколько угодно (зависит от типа дерева). Благодаря этому деревья позволяют хранить информацию в виде строгой иерархии.
Например, структура папок на компьютере: у каждой папки может быть вложено несколько других, но у вложенной папки всегда есть только одна «родительская» папка.
Деревья активно применяются в самых разных задачах: для поиска и сортировки данных, для представления выражений в математике и программировании, для обработки графов, в файловых системах, в компиляторах и даже в базах данных.
Выглядят деревья следующим образом:
Чтобы лучше понимать работу деревьев, нужно разобраться с основными понятиями:
- Узел дерева – это основная структурная единица, представляющая собой точку соединения ветвей. Узлы могут содержать данные и ссылки на другие узлы. На изображении узлы обозначены латинскими буквами.
- Корень – А – начальный узел дерева. Это основа для построения всей структуры. Корень является родителем всех остальных узлов в дереве и не имеет предков.
- Лист – узел, который не имеет потомков. Листовые узлы представляют конечные точки или результаты обработки данных. Они являются терминальными элементами дерева. На изображении листами являются узлы E, F, G и H.
- Ветви – связи между узлами. Они представляют собой линии или стрелки, которые соединяют один узел с другим. Ветви позволяют перемещаться по дереву от одного узла к другому. На изображении ветви обозначены синим цветом.
- Уровень (глубина) узла отсчитывается от корневого узла и определяет его положение в структуре дерева. Корневой узел находится на уровне 0, его потомки – на уровне 1 и так далее. Уровень узла помогает понять его позицию в иерархии дерев. Например, у узла B уровень 1, у узла H уровень 3.
- Высота дерева – максимальное расстояние от корня до самого дальнего листа. Высота определяет высоту дерева в уровнях. Если высота дерева равна 3 (как на изображении выше), то самое дальнее расстояние от корня до листа составляет 3 уровня.
Деревья делятся на разные виды: бывают n-арные деревья, где у каждого узла может быть до n потомков, бывают сбалансированные и несбалансированные деревья, где важна форма и глубина.
Но в рамках задачи ЕГЭ мы будем использовать двоичные деревья, у которых каждый узел может иметь не более двух дочерних узлов.
Такое дерево удобно для представления информации в двоичной системе: левую ветвь условно называют «нулевой», а правую – «единичной». Это сразу связывает дерево с двоичным кодированием, ведь каждый путь от корня до листа можно интерпретировать как последовательность нулей и единиц.
Давайте построим простейшее двоичное дерево. Корень в этом случае не несёт собственного значения – он играет роль отправной точки.
От него отходят две ветви: слева ветвь с меткой «0», справа – ветвь с меткой «1».
На втором уровне узлы будут обозначены как «00» и «01» для левой ветви и «10» и «11» для правой.
На следующем уровне добавляем ещё один символ: если ветвь идёт налево, то к коду добавляется ноль, если направо – единица.
В итоге получаем такое дерево:
Здесь мы дописывали новые значения в конец (нули оранжевым цветом, единицы – зелёным). Такое дерево подходит для работы с префиксным кодом (условием Фано).
При решении задания 4 ЕГЭ по информатике мы же можем использовать лишь одну из рассмотренных ветвей, а зависимости от кодовых слов, которые даны нам в задании.
Теперь давайте предположим, что мы строим двоичное дерево, у которого в корне находится единица и уже использован код «110». Проверим, какие коды будут удовлетворять условию Фано.
Начнем с тех, которые нам не подходят. А это будут все коды, которые начинаются с «110», то есть потомки этого узла: «1100», «1101» и все остальные.
Но нам также не подходят и узлы-предки: «11» и «1», которые тоже содержат в себе значения, на которые начинается наш код. Все неподходящие коды выделены на изображении оранжевым цветом, подходящие – зелёным.
Теперь давайте построим дерево, у которого значения нового узла будут дописываться в начало. То есть такое дерево нам подойдет для работы с постфиксными кодами (обратным условием Фано).
И таким же образом давайте найдем коды, неудовлетворяющие обратному условию Фано в случае, если использован код «010». Это будут все коды, оканчивающиеся на «010». То есть все потомки узла со значением «010» («0010» и «1010»), и также два его предка: «10» и «0».
В целом, именно по такому алгоритму мы будем строить двоичные деревья и находить недостающие коды для букв в заданиях 4 ЕГЭ по информатике, о чем и поговорим в следующей статье.
