Реализации алгоритмов/АВЛ-дерево
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
Общие свойства
правитьВ АВЛ-дереве высоты не меньше узлов, где — число Фибоначчи. Поскольку ,
где — золотое сечение,
то имеем оценку на высоту АВЛ-дерева , где — число узлов. Следует помнить, что — мажоранта, и её можно использовать только для оценки (Например, если в дереве только два узла, значит в дереве два уровня, хотя ). Для точной оценки глубины дерева следует использовать пользовательскую подпрограмму.
function TreeDepth(Tree : TAVLTree) : byte;
begin
if Tree <> nil then
result := 1 + Max(TreeDepth(Tree^.left),TreeDepth(Tree^.right))
else
result := 0;
end;
Тип дерева можно описать так
TKey = LongInt;
TInfo = LongInt;
TBalance = -2..2; // диапазон в районе от -1 до 1 , но включим для простоты нарушения -2 и 2
PAVLNode = ^ TAVLNode;
TAVLNode = record
case integer of
0:(left, right : PAVLNode;
key : TKey;
info : TInfo;
{ Поле определяющее сбалансированность вершины }
balance : TBalance;);
1:(childs:array[boolean] of PAVLNode); // представление веток дерева в виде массива для упрощения переходов
end;
TAVLTree = PAVLNode;
AVL-условия можно проверить так
function TestAVLTree(V:PAVLNode):integer; //возвращает высоту дерева
var a,b:integer;
begin
Result:=0;
if V=nil then exit;
a:=TestAVLTree(V.Left);
b:=TestAVLTree(V.Right);
if ((a-b)<>V.Balance)or(abs(a-b)>=2) then begin
raise Exception.CreateFmt('%d - %d balancefactor %d',[a,b,V.Balance]);
end;
Result:=1+max(a,b);
end;
Балансировка
правитьОтносительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.
Используются 4 типа вращений:
1.Малое левое вращение w:Файл:AVL LR.GIF
Данное вращение используется тогда, когда (высота b-поддерева — высота L) = 2 и высота С <= высота R.
2.Большое левое вращение w:Файл:AVL BR.GIF
Данное вращение используется тогда, когда (высота b-поддерева — высота L) = 2 и высота c-поддерева > высота R.
//Функция для устранения правого нарушения с помощью вышеописанных поворотов,
//возвращает True если высота дерева уменьшилась, False - если осталась той же
function AVL_FixWithRotateLeft(var N:PAVLNode):boolean;
var R,RL,RLR,RLL:PAVLNode;
begin
R:=N.Right;
RL:=R.Left;
Result:=true;
case R.Balance of
-1 :begin
N.Balance:= 0; // h(RL)=H-3 h(L)=H-3 => h(N) =H-2
R.Balance:= 0; // h(RR)=H-2 => h(R)= H-1
N.Right:=RL;
R.Left:=N;
N:=R;
end;
0 :begin
N.Balance:= -1; // h(RL)=H-2 h(L)=H-3 => h(N) =H-1
R.Balance:= 1; // h(RR)=H-2 => h(L)= H
N.Right:=RL;
R.Left:=N;
N:=R;
Result:=false;
end;
1:begin
RLR:=RL.Right;
RLL:=RL.Left;
R.Left:=RLR;
R.Balance:=min(-RL.Balance,0); //1 =>-1, 0 =>0, -1 =>0
N.Right:=RLL;
N.Balance:=max(-RL.Balance,0); //1 => 0, 0 =>0, -1 => 1
RL.Right:=R;
RL.Left:=N;
RL.Balance:=0;
N:=RL;
end;
end;
end;
3.Малое правое вращение w:Файл:AVL LL.GIF
Данное вращение используется тогда, когда (высота b-поддерева — высота R) = 2 и высота С <= высота L.
4.Большое правое вращение w:Файл:AVL BL.GIF
Данное вращение используется тогда, когда (высота b-поддерева — высота R) = 2 и высота c-поддерева > высота L.
//Функция для устранения левого нарушения с помощью вышеописанных поворотов,
//возвращает True если высота дерева уменьшилась, False - если осталась той же
function AVL_FixWithRotateRight(var N:PAVLNode):boolean;
var L,LR,LRL,LRR:PAVLNode;
begin
L:=N.Left;
LR:=L.Right;
Result:=true;
case L.Balance of
1:begin
N.Balance:= 0; // h(LR)=H-3 h(R)=H-3 => h(N) =H-2
L.Balance:= 0; // h(LL)=H-2 => h(L)= H-1
N.Left:=LR;
L.Right:=N;
N:=L;
end;
0 :begin
N.Balance:=1; // h(LR)=H-2 h(R)=H-3 => h(N) =H-1
L.Balance:= -1; // h(LL)=H-2 => h(L)= H
N.Left:=LR;
L.Right:=N;
N:=L;
Result:=false;
end;
-1 :begin
LRL:=LR.Left;
LRR:=LR.Right;
L.Right:=LRL;
L.Balance:=max(-LR.Balance,0); //1 =>0, 0 =>0, -1 =>1
N.Left:=LRR;
N.Balance:=min(-LR.Balance,0); //1 => -1, 0 =>0, -1 => 0
LR.Left:=L;
LR.Right:=N;
LR.Balance:=0;
N:=LR;
end;
end;
end;
В каждом случае достаточно просто доказать то, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться.
Также можно заметить, что большое вращение это комбинация правого и левого малого вращения.
Из-за условия балансированности высота дерева О(log(N)), где N- количество вершин, поэтому добавление элемента требует O(log(N)) операций.
Алгоритм добавления вершины
правитьПоказатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей (данный процесс описан Николасом Виртом в «Алгоритмы и структуры данных»):
- Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
- Включения новой вершины в дерево и определения результирующих показателей балансировки.
- «Отступления» назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо — балансировка.
Будем возвращать в качестве результата функции, уменьшилась высота дерева или нет. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { hl — высота левого поддерева, hr — высота правого поддерева } Включение вершины в левое поддерево приведет к
- hl < hr: выравняется hl = hr. Ничего делать не нужно.
- hl = hr: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.
- hl > hr: теперь hl — hr = 2, — требуется балансировка.
В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.
вспомогательная функция сравнивающая два ключа
function KeyCompare(const V1,V2:TKey):integer;
begin
if V2>V1 then begin
Result:=-1;
end else
if V2=V1 then begin
Result:=0;
end else
Result:=1;
end;
Рекурсивная процедура вставки:
function AVL_InsertNode(Var Tree : TAVLTree; const aKey : TKey; const ainfo : TInfo): Boolean;
Var
c:integer;
begin
if Tree = nil then begin
New(Tree);
Result := true;
with Tree^ do
begin
key := akey;
info := ainfo;
left := nil;
right := nil;
balance := 0;
end;
end else begin
c:= KeyCompare(aKey,Tree^.key);
if c=0 then begin
Tree^.info:=ainfo;
Result := false;
end else begin
Result:=AVL_InsertNode(Tree^.childs[c>0],akey,ainfo);
if Result then begin
if c>0 then Tree^.balance:= Tree^.balance-1 else Tree^.balance:= Tree^.balance+1;
case Tree^.balance of
2: Result:=not AVL_FixWithRotateRight(Tree);
-2: Result:=not AVL_FixWithRotateLeft(Tree);
0: Result:=false;
end
end;
end;
end;
end;
Алгоритм удаления вершины
правитьДля простоты опишем рекурсивный алгоритм удаления. Если вершина — лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.
Упрощённый вариант удаления можно описать таким образом
// Функция очень далека от оптимальной,
// сравнение происходит даже после нахождения удаляемого ключа
// передаются сразу все параметры, некоторые из которые можно не использовать,
// разбив на 3 процедуры с более упрощённой функциональностью :
// 1.движение только влево
// function AVL_DropNodeLeft(Var Tree : TAVLTree; DroppedNode:TAVLTree): Boolean;
// 2.движение только вправо
// function AVL_DropNodeRight(Var Tree : TAVLTree; DroppedNode:TAVLTree): Boolean;
// 3.поиск
// function AVL_DropNode(Var Tree : TAVLTree; const aKey : TKey): Boolean;
function AVL_DropNode(Var Tree : TAVLTree; const aKey : TKey; DroppedNode : TAVLTree = nil): Boolean;
var c : Integer;
begin
if Tree = nil then
begin
Result := false;
exit;
end;
c := KeyCompare(aKey, Tree^.key);
if c = 0 then
begin
DroppedNode := Tree;
c := -DroppedNode.balance; // пойдём в более высокую или левую ветвь дерева если их высоты равны
end;
if (Tree^.childs[c > 0] = nil) and (DroppedNode <> nil) then
begin
DroppedNode^.Key := Tree^.Key;
DroppedNode^.info := Tree^.info;
DroppedNode := Tree;
// поставим вместо текущего лист с противоположного направления
Tree := Tree^.childs[c <= 0];
Dispose(DroppedNode);
Result := true;
exit;
end;
Result := AVL_DropNode(Tree^.childs[c > 0], aKey, DroppedNode);
if Result then
begin
if c > 0 then
begin
Tree^.balance := Tree^.balance + 1;
end
else
Tree^.balance := Tree^.balance - 1;
end;
case Tree^.balance of
-2: Result := AVL_FixWithRotateLeft(Tree);
-1,1: Result := false;
2: Result := AVL_FixWithRotateRight(Tree);
end;
end;
end;
Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.
Очевидно, что в результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по второму вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует O(N) операций. Становится очевидной возможность оптимизации: поиск ближайшей вершины может быть выполнен по краю поддерева, что сокращает сложность до O(log(N)).
Нерекурсивная вставка в АВЛ-дерево сверху-вниз
правитьНерекурсивный алгоритм сложнее рекурсивного.
- Находится место вставки и вершина, высота которой не изменится при вставке (это вершина, у которой высота левого поддерева не равна высоте правого; будем называть её PrimeNode)
- Выполняется спуск от PrimeNode до места вставки с изменением балансов
- Выполняется ребалансировка PrimeNode при наличии переполнения
type
PAVLTree = ^TAVLTree; //дополнительный тип для указания на место, где хранится указатель на лист
// функция возвращает True если было добавление нового литка, false - произошла замена значения ключа
function AVL_InsertNode2(var Root : TAVLTree; const aKey : TKey; const Value : TInfo) : Boolean;
var PrimeNode, p, q : PAVLTree;
c : Integer;
begin
q := @Root;
PrimeNode := q;
// 1-я часть алгоритма
if q^ <> nil then
begin
repeat
c := KeyCompare(aKey, q^.Key);
if c = 0 then
begin
q^.info := Value;
Result := false;
exit;
end;
if (q^.Balance <> 0) then
begin
PrimeNode := q;
end;
q := @q^.Childs[c > 0];
until q^ = nil;
end;
New(q^);
with q^^ do
begin
key := akey;
info := Value;
left := nil;
right := nil;
balance := 0;
end;
if PrimeNode <> q then
begin
// 2-я часть алгоритма
p := PrimeNode;
repeat
c := KeyCompare(aKey, p^.Key);
if c > 0 then
begin
p^.Balance := p^.Balance - 1;
p := @p^.Right;
end
else
begin
p^.Balance := p^.Balance + 1;
p := @p^.Left;
end;
until p = q;
// 3-я часть алгоритма
case PrimeNode^.Balance of
+2: AVL_FixWithRotateRight(PrimeNode^);
-2: AVL_FixWithRotateLeft(PrimeNode^);
end;
end;
Result := true;
end;
Нерекурсивное удаление из АВЛ-дерева сверху вниз
правитьДля реализации удаления будем исходить из того же принципа, что и при вставке: найдём вершину, удаление из которой не приведёт к изменению её высоты. Существует два случая:
- высота левого поддерева равна высоте правого поддерева (исключая случай, когда у листа нет поддеревьев)
- высота дерева по направлению движения меньше противоположной(«брат» направления) и баланс «брата» равен 0 (разбор этого варианта довольно сложен, так что пока без доказательства)
function AVL_DropNode2(var Root : PAVLNode; const Key : TKey): Boolean;
var PrimeNode, p, q, b : PAVLTree;
c : Integer;
last : Boolean;
DroppedNode : PAVLNode;
begin
p := nil;
q := @Root;
PrimeNode := q;
last := false;
DroppedNode := nil;
while q^ <> nil do
begin
if (p <> nil) then
begin
if (q^^.Balance = 0) and (q^^.Left <> nil) then
begin
PrimeNode := q;
end
else
if (last and (p^^.Balance = 1)) or ((not last) and (p^^.Balance = -1)) then
begin
b := @p^^.Childs[not last];
if b^.Balance = 0 then
begin
PrimeNode := p;
end;
end;
end;
c := KeyCompare(Key, q^^.Key);
last := c > 0;
p := q;
q := @q^^.Childs[last];
if c = 0 then
begin
DroppedNode := p^;
end;
end;
if DroppedNode = nil then
begin
Result := false;
exit;
end;
Result := true;
while PrimeNode <> p do
begin
c := KeyCompare(Key, PrimeNode^.Key);
if c > 0 then
begin
PrimeNode^.Balance := PrimeNode^.Balance + 1;
if PrimeNode^.Balance = 2 then
begin
AVL_FixWithRotateRight(PrimeNode^);
PrimeNode := @PrimeNode^.Right; // исключаем из обработки, теперь там находится текущая вершина
end;
PrimeNode := @PrimeNode^.Right;
end
else
begin
PrimeNode^.Balance := PrimeNode^.Balance - 1;
if PrimeNode^.Balance = -2 then
begin
AVL_FixWithRotateLeft(PrimeNode^);
PrimeNode := @PrimeNode^.Left; // исключаем из обработки, теперь там находится текущая вершина
end;
PrimeNode := @PrimeNode^.Left;
end;
end;
DroppedNode^.Key := p^^.Key;
DroppedNode^.info := p^^.info;
DroppedNode := p^;
// заменим текущий лист на лист с противоположного направления
p^ := p^^.childs[(p^^.Left = nil)];
Dispose(DroppedNode);
end;
Для облегчения понимания приведённый алгоритм не содержит каких-либо оптимизаций. В отличие от рекурсивного алгоритма, найденная удаляемая вершина заменяется значением из левой подветви. Этот алгоритм можно оптимизировать так же, как и рекурсивный (за счёт того, что после нахождения удаляемой вершины известно направление движения):
- ищем удаляемый элемент и попутно находим нашу замечательную вершину
- производим изменение балансов, в случае необходимости делаем ребалансировку
- удаляем наш элемент (в действительности не удаляем, а заменяем его ключ и значение, учёт перестановок вершин будет немного сложнее)