Реализации алгоритмов/АВЛ-дерево

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

Общие свойства

В АВЛ-дереве высоты $h$ не меньше $F_{h}$ узлов, где $F_{h}$ — число Фибоначчи. Поскольку $F_{n}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}}={\frac {\phi ^{n}-(-\phi )^{-n}}{\phi -(-\phi )^{-1}}}$ ,

где $\phi ={\frac {1+{\sqrt {5}}}{2}}$ — золотое сечение,

то имеем оценку на высоту АВЛ-дерева $h=O(log(n))$ , где $n$ — число узлов. Следует помнить, что $O(log(n))$ — мажоранта, и её можно использовать только для оценки (Например, если в дереве только два узла, значит в дереве два уровня, хотя $log(2)=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, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей (данный процесс описан Николасом Виртом в «Алгоритмы и структуры данных»):

Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
Включения новой вершины в дерево и определения результирующих показателей балансировки.
«Отступления» назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо — балансировка.

Будем возвращать в качестве результата функции, уменьшилась высота дерева или нет. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { h_l — высота левого поддерева, h_r — высота правого поддерева } Включение вершины в левое поддерево приведет к

h_l < h_r: выравняется h_l = h_r. Ничего делать не нужно.
h_l = h_r: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.
h_l > h_r: теперь h_l — h_r = 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;

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

ищем удаляемый элемент и попутно находим нашу замечательную вершину
производим изменение балансов, в случае необходимости делаем ребалансировку
удаляем наш элемент (в действительности не удаляем, а заменяем его ключ и значение, учёт перестановок вершин будет немного сложнее)