Бинарные деревья. Построение дерева. Обход дерева. Поиск по дереву. Удаление элементов. Сбалансированные деревья. АВЛ-деревья. Красно-черные деревья. Оптимальные деревья поиска

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

Упорядоченное дерево – это дерево, у которого ветви каждого узла упорядочены. Узел y, который находится непосредственно под узлом x, называется потомком x; если x находится на уровне i, то говорят, что y – на уровне i + 1. Наоборот, узел x называется предком y. Считается, что корень дерева расположен на уровне 1. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.

Если элемент не имеет потомков, он называется терминальным элементом или листом, а элемент, не являющийся терминальным, называется внутренним узлом. Число потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева. Число ветвей, или ребер, которые нужно пройти, чтобы продвинуться от корня к узлу x, называется длиной пути к x. Длина пути дерева определяется как сумма длин путей всех его узлов. Она также называется длиной внутреннего пути.

Для того чтобы определить, что называется длиной внешнего пути, мы будем дополнять дерево специальным узлом каждый раз, когда в нем встречается нулевое поддерево (рис. 18). При этом, все узлы должны иметь одну и ту же степень – степень дерева.

Рисунок 18 - Дерево со специальными узлами

Длина внешнего пути теперь определяется как сумма длин путей всех специальных узлов.

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

Упорядоченные деревья степени 2 играют особо важную роль. Они называются бинарными деревьями(рис. 19). Упорядоченное бинарное дерево – конечное множество элементов (узлов), каждый из которых либо пуст, либо состоит из корня (узла), связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями корня. Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями (multiway trees).

Рисунок 19 - Бинарное дерево

Бинарные деревья

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

Изображение рекурсивных структур с разветвлениями предполагает использование ссылок. Очевидно, что не имеет смысла описывать переменные с фиксированной древовидной структурой, вместо этого узлы определяются как переменные с фиксированной структурой, т. е. фиксированного типа, где степень дерева определяет число компонент-ссылок, указывающих на поддеревья данного узла. Ссылка на пустое поддерево обозначается через nil.

type node = record

key: integer;

left, right: ^node;

end;

Обход дерева

Распространенная задача на древовидной структуре – выполнение заданной операции P с каждым элементом дерева. Здесь P рассматривается как параметр более общей задачи посещения всех узлов, или, как это обычно называют, обхода дерева.

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

Существуют три принципа упорядочения, которые естественно вытекают из структуры деревьев. Так же, как и саму древовидную структуру, их удобно выразить с помощью рекурсии. Обозначив R – корнем, а A и B – левым и правым поддеревьями, можно определить 3 упорядочения:

1) сверху вниз: R, A, B (посетить корень до поддеревьев);

2) слева направо: А, R, В;

3) снизу вверх: А, В, R (посетить корень после поддеревьев).

Поиск элементов

Бинарные деревья часто используются для представления множеств данных, элементы которых ищутся по уникальному, только им присущему ключу. Если дерево организовано таким образом, что для каждого узла t[i] все ключи в левом поддереве меньше ключа t[i], а ключи в правом поддереве больше ключа t[i], то это дерево называется деревом поиска. В дереве поиска можно найти место каждого ключа, двигаясь, начиная от корня, и переходя на левое или правое поддерево каждого узла в зависимости от значения его ключа. Дерево – намного более подходящая форма организации такого множества данных, чем линейный список.

Т.к. этот поиск проходит по единственному пути от корня к искомому узлу, его можно запрограммировать с помощью итерации:

Function Loc (x: integer; t: ref): ref;

Var

found: boolean;

Begin

found: = false;

While (t <> nil) and (Not found) do

Begin

if t^.key = x then found:= true

else

if t^.key > x then t:= t^.Left

else t:= t^.right

end;

Loc:= t;

End;

Функция Loc (x, t) имеет значение nil, если в дереве с корнем t не найдено ключа со значением x. Так же как в случае поиска по списку, сложность условия окончания цикла заставляет искать лучшее решение. При поиске по списку в конце его помещается барьер. Этот прием можно применить и в случае поиска по дереву. Использование ссылок позволяет связать все терминальные узлы дерева с одним и тем же барьером (рис. 20). Полученная структура – это уже не просто дерево, а скорее, дерево, все листья которого прицеплены внизу к одному якорю.

Рисунок 20 - Дерево с барьером

Включение элементов

Рассмотрим случай постоянно растущего, но никогда не убывающего дерева. Хорошим примером является задача построения частотного словаря. В этой задаче задана последовательность слов, и нужно установить число появлений каждого слова. Это означает, что, начиная с пустого дерева, каждое слово ищется в дереве. Если оно найдено, увеличивается его счётчик появлений, если нет – в дерево вставляется новое слово (с начальным значением счетчика, равным 1).

Удаление из дерева

Удаление элемента обычно не так просто, как включение. Оно просто в случае, когда удаляемый элемент является терминальным узлом или имеет одного потомка.

Различают три случая:

1. Компоненты с ключом, равным x, нет.

2. Компонента с ключом x имеет не более одного потомка.

3. Компонента с ключом x имеет двух потомков.

Легко удалить терминальный узел, или узел, имеющий одного потомка. В случае двух потомков удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. Ясно, что такие элементы не могут иметь более одного потомка.

АВЛ-деревья

Легко найти наихудший случай: ключи поступают в порядке возрастания, и дерево оказывается полностью вырожденным, т. е. превращается в линейный список. В этом случае среднее число сравнений ключей равно N/2. Наилучший вариант получается, если дерево строится идеально сбалансированным, в этом случае среднее число сравнения равно log₂N.

Критерий сбалансированности дерева (Адельсон-Вельский, Ландис, 1962): дерево является сбалансированным тогда и только тогда, когда для каждого его узла высота его двух поддеревьев различается не более чем на 1.

Дерево, удовлетворяющее этому критерию, называют АВЛ-деревом (рис. 21) или сбалансированным деревом. Идеально сбалансированное дерево является АВЛ-деревом.

Рисунок 21 - АВЛ-дерево

Рассмотрим включение элемента в сбалансированное дерево.

Возможны 3 случая:

1. h_L = h_R: L и R становятся неравной высоты, но критерий сбалансированности не нарушается.

2. h_L < h_R: L и R приобретают равную высоту, т.е. сбалансированность даже улучшается.

3. h_L > h_R: критерий сбалансированности нарушается, и дерево нужно трансформировать, такая перестройка называется поворотом.

В общих чертах процесс включения узла состоит из последовательности таких трех этапов:

1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве.

2. Включить новый узел и определить новый показатель сбалансированности.

3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла.

Рассмотрим бинарное дерево (a), которое состоит только из двух узлов. Включение ключа 7 вначале дает несбалансированное дерево (т.е. линейный список). Его балансировка требует однократного правого (RR) поворота, давая в результате идеально сбалансированное дерево (b). Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным левым (LL) поворотом (d). Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5. Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR); результатом является дерево (e). Теперь при следующем включении потерять сбалансированность может лишь узел 5. Действительно, включение узла 6 должно привести к четвертому виду балансировки: двукратному повороту направо и налево (RL).Окончательное дерево показано на рис.21.2 (f).

Рисунок 21.2 – Принцип работы алгоритма

Красно-чёрное дерево

Красно-черные деревья - один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O(log n).

Красно-чёрное дерево — двоичное дерево поиска, в котором каждый узел имеет атрибут цвет, принимающий значения красный или черный. В дополнение к обычным требованиям, налагаемым на двоичные деревья поиска, к красно-чёрным деревьям применяются следующие требования:

- Узел либо красный, либо чёрный.

-Корень — чёрный. (Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на чёрный, но не обязательно наоборот).

- Все листья(NIL) — черные.

- Оба потомка каждого красного узла — черные.

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

Эти ограничения реализуют критическое свойство красно-черных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа (если дальний лист расположен на 3-м уровне). Результатом является то, что дерево примерно сбалансировано. Так как такие операции как вставка, удаление и поиск значений требуют в худшем случае времени, пропорционального длине дерева, эта теоретическая верхняя граница высоты позволяет красно-чёрным деревьям быть более эффективными в худшем случае, чем обычные двоичные деревья поиска.

Во многих реализациях структуры дерева возможно, чтобы узел имел только одного потомка и листовой узел содержал данные. В этих предположениях реализовать красно-чёрное дерево возможно, но изменятся несколько свойств и алгоритм усложнится. По этой причине данная статья использует «фиктивные листовые узлы», которые не содержат данных и просто служат для указания, где дерево заканчивается. Эти узлы часто опускаются при графическом изображении, в результате дерево выглядит противоречиво с вышеизложенными принципами, но на самом деле противоречия нет. Следствием этого является то, что все внутренние (не являющиеся листовыми) узлы имеют два потомка, хотя один из них может быть нулевым листом. Свойство 5 гарантирует, что красный узел обязан иметь в качестве потомков либо два черных нулевых листа, либо два черных внутренних узла. Для чёрного узла с одним потомком нулевым листовым узлом и другим потомком, не являющимся таковым, свойства 3, 4 и 5 гарантируют, что последний должен быть красным узлом с двумя черными нулевыми листьями в качестве потомков.

Пример:

Рисунок 24 - Пример красно-черного дерева