АВЛ-деревья

Можно ли при работе с бинарными деревьями поиска гарантировать оценку T(n) = O(log(n)) для поиска и вставки не только в среднем, но и в худшем случае? Ответ положительный. Однако для этого следует выбрать подходящий класс деревьев. Для произвольных бинарных деревьев операция вставки выполняется просто и быстро, но поиск может быть долгим в случае вырождения. ИС-деревья гарантируют быстрый поиск, но много времени уходит на поддержание баланса при вставке и удалении. Желательно найти какой-то «средний» тип деревьев, чтобы они были не намного хуже, чем идеально сбалансированные, но вставка выполнялась значительно быстрее.

Было предложено несколько подобных типов деревьев. Среди них АВЛ-деревья [1, 5], 2-3-деревья [3, 5], красно-черные деревья [4]. Мы рассмотрим только АВЛ-деревья, которые были названы в честь предложивших их советских математиков Г.М.Адельсона-Вельского и Е.М.Ландиса и которые до настоящего времени остаются одним из лучших средств решения задачи поиска со вставкой.

АВЛ-деревом [3] называется такое бинарное дерево поиска, для каждой вершины которого высота ее левого и правого поддеревьев отличаются не более, чем на единицу.

Легко видеть, что всякое ИС-дерево поиска является АВЛ-деревом. Обратное, вообще говоря, неверно.

На рис. 4.3 показаны примеры самых худших (т.е. наиболее разбалансированных, «перекошенных») АВЛ-деревьев для различных значений высоты. Как видно из рисунка, даже в худшем случае АВЛ-деревья далеки от вырожденности. Это становится все более заметно при увеличении высоты. Можно доказать, что высота АВЛ-дерева превышает высоту ИС-дерева с тем же количеством вершин не более, чем на 45 %. Таким образом, логарифмическая зависимость высоты от числа вершин сохраняется даже в худшем случае.

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

Рис. 4.3. Наихудшие АВЛ-деревья разной высоты

Прежде всего, надо выяснить, каким образом вообще обнаруживается нарушение сбалансированности при вставке. Наиболее удобное решение – хранить в каждой вершине АВЛ-дерева дополнительное поле bal (баланс), которое может принимать одно из трех значений:

t^.bal = –1, если левое поддерево вершины t выше, чем правое;

t^.bal = 0, если оба поддерева одинаковы по высоте;

t^.bal = +1, если правое поддерево t выше, чем левое.

При выполнении вставки сначала происходит рекурсивный спуск по дереву, затем новая вершина добавляется как лист (и для нее, естественно, устанавливается начальное значение bal = 0), а затем, в процессе возврата вверх, для всех вершин соответствующей ветви дерева выполняется корректировка значений поля bal, если вставка новой вершины вызвала увеличение высоты левого или правого поддерева.

Пусть при возврате вверх после вставки выяснилось, что для некоторой вершины C баланс нарушен: левое поддерево C теперь оказалось на 2 единицы выше, чем правое (случай перекоса вправо рассматривается аналогично). При этом для вершин, лежащих ниже C, баланс остается в пределах нормы (от –1 до +1). В этой ситуации возможны два существенно разных случая, проиллюстрированных на рис. 4.4.

Рис. 4.4. Нарушение баланса при вставке в АВЛ-дерево

Буквой A обозначен левый сын вершины C. Высота поддерева A могла увеличиться либо при вставке в левое поддерево A (случай 1), либо при вставке в правое поддерево (случай 2). Прямоугольники 1, 2, 3, 4 обозначают поддеревья произвольной сложности, а перечеркнутый квадрат – добавленную вершину. Во втором случае показаны два возможных положения добавленной вершины, одно из них – пунктиром. Можно доказать, что в случае 1 высоты поддеревьев 1, 2 и 3 равны одной и той же величине h, а в случае 2 высоты поддеревьев 1 и 4 на единицу больше, чем 2 и 3.

Для восстановления баланса изображенные части дерева должны быть переставлены так, как показано на рис. 4.5.

Рис. 4.5. Восстановление баланса АВЛ-дерева

Такие преобразования АВЛ-дерева принято называть его поворотами.

Прежде всего заметим, что повороты не нарушают упорядоченность дерева поиска (например, в случае 1 и до поворота, и после него ключи в различных частях дерева упорядочены следующим образом: 1 £ A £ 2 £ C £ 3). При этом восстанавливается баланс вершин дерева.

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

var

t: Tree; {Корень поворачиваемой части дерева}

p: Tree; {Рабочая переменная}

...

p:= t^.left; {p -> A}

t^.left:= p^.right; {C -> 2}

p^.right:= t; {A -> C}

t^.bal:= 0; {Оба поддерева C стали одной высоты}

t:= p; {A – новый корень повернутой части}

t^.bal:= 0; {Оба поддерева A тоже одной высоты}

...

Из сравнения рис. 4.4 и 4.5 можно заметить, что высота рассматриваемой части дерева не увеличивается после вставки и последующего поворота. Это значит, что баланс вышележащих вершин дерева не изменяется и эти вершины не потребуют дополнительных поворотов.