Сбалансированное дерево поиска

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

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962.

Алгоритм добавления вершины

Первый шаг аналогичен добавлению вершины в Двоичное дерево поиска. Далее производится балансировка всех предков добавленной вершины в порядке от родителя к корню.

Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.

Используются 4 типа вращений:

1.Малое правое вращение
    

Данное вращение используется тогда, когда (высота b-поддерева - высота L) = 2 и высота С <= высота R.

2.Большое правое вращение
 

Данное вращение используется тогда, когда (высота b-поддерева - высота L) = 2 и высота c-поддерева > высота R.

3.Малое левое вращение
    

Данное вращение используется тогда, когда (высота b-поддерева — высота R) = 2 и высота С <= высота L.

4.Большое левое вращение
 

Данное вращение используется тогда, когда (высота b-поддерева - высота R) = 2 и высота c-поддерева > высота L.

В каждом случае достаточно просто доказать то, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться.

Из-за условия балансированности высота дерева О(lg(N)), где N- количество вершин, поэтому добавление элемента требует O(lg(N)) операций.

Алгоритм удаления вершины

Для простоты опишем рекурсивный алгоритм удаления. Если вершина - лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.

Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.

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

Расстановка балансов при вставке

Непосредственно после вставки нового элемента в дерево — ему присваивается баланс 0, и производится обратный проход в сторону корня дерева: при переходе к родителю если пришли слева — баланс увеличивается на 1, а если пришли справа — баланс уменьшается на 1.

Это делается до тех пор, пока при изменении баланса он не станет нулевым.

Если в процессе обновления баланс изменился на −2 — проверяется правый сын текущего узла: если его баланс равен +1 — выполняется двойной правый поворот, в противном же случае — одинарный правый поворот.

Если же баланс изменяется на +2 — проверяется левый сын текущего узла: если его баланс равен −1 — выполняется двойной левый поворот, в противном случае — одинарный левый поворот.

Расстановка балансов при удалении

Как уже говорилось, если удаляемая вершина — лист, то она удаляется, и обратный обход дерева происходит от родителя удалённого листа. Если не лист — ей находится «замена», и обратный обход дерева происходит от родителя «замены». Непосредственно после удаления элемента — «замена» получает баланс удаляемого узла.

При обратном обходе: если при переходе к родителю пришли слева — баланс уменьшается на 1, если же пришли справа — на увеличивается 1.

Это делается до тех пор, пока при изменении баланса он не станет равным −1 или 1 (обратите внимание на различие с вставкой элемента!): в данном случае такое изменение баланса будет гласить о неизменной дельта-высоте поддеревьев. Повороты происходят по тем же правилам, что и при вставке.

Расстановка балансов при одинарном повороте

Обозначим:

«Current» — узел, баланс которого равен −2 или 2: то есть тот, который нужно повернуть

«Pivot» — ось вращения. +2: левый сын Current’а, −2: правый сын Current’а

Если поворот осуществляется при вставке элемента, то баланс Pivot’а равен либо 1, либо −1. В таком случае после поворота балансы обоих устанавливаются равными 0.

При удалении всё иначе: баланс Pivot’а может стать равным 0 (в этом легко убедиться).

Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Pivot:

Направление поворота	Old Pivot.Balance	New Current.Balance	New Pivot.Balance
Правый или Левый	-1 или +1	0	0
Правый	0	-1	+1
Левый	0	+1	-1

Расстановка балансов при двойном повороте

Pivot и Current — те же самые, но добавляется третий участник поворота. Обозначим его за «Bottom»: это (при двойном правом повороте) левый сын Pivot’а, а при двойном левом — правый сын Pivot’а.

При данном повороте — Bottom в результате всегда приобретает баланс 0, но от его исходного баланса зависит расстановка балансов для Pivot и Current.

Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Bottom:

Направление	Old Bottom.Balance	New Current.Balance	New Pivot.Balance
Правый или Левый	0	0	0
Правый	+1	0	-1
Правый	-1	+1	0
Левый	+1	-1	0
Левый	-1	0	+1

Реализация на языках программирования

Имеется пример реализации АВЛ-дерева на Object Pascal и C.

Литература

Г. М. Адельсон-Вельский, Е. М. Ландис. Один алгоритм организации информации // Доклады АН СССР. 1962. Т. 146, № 2. C. 263–266.

См. также

• Сбалансированные (самобалансирующиеся) деревья:

• Красно-чёрное дерево
• Идеально сбалансированное дерево
• Расширяющееся дерево