АВЛ-дерево

АВЛ-дерево — збалансоване по висоті двійкове дерево пошуку: для кожної його вершини висота її двох піддерев відрізняється не більше ніж на 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.Мале ліве обертання

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

 2.Велике ліве обертання

Дане обертання використовується тоді, коли (висота 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.Мале праве обертання

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

 4.Велике праве обертання

Дане обертання використовується тоді, коли (висота 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; DropedNode:TAVLTree): Boolean;
// 2.рух тільки вправо
// function AVL_DropNodeRight(Var Tree : TAVLTree; DropedNode:TAVLTree): Boolean;
// 3.пошук
// function AVL_DropNode(Var Tree : TAVLTree; const aKey : TKey): Boolean; 
function AVL_DropNode(Var Tree : TAVLTree; const aKey : TKey;DropedNode: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
    DropedNode:=Tree;
    c:=-DropedNode.balance;//підемо в більш високу або ліву гілку дерева якщо їх висоти рівні
  end;
  if (Tree^.childs[c>0]=nil)and(DropedNode<>nil) then begin
    DropedNode^.Key:=Tree^.Key;
    DropedNode^.info:=Tree^.info;
    DropedNode:=Tree;
    //поставимо замість поточного лист з протилежного напрямку
    Tree:=Tree^.childs[c<=0];
    Dispose(DropedNode);
    Result:=true;
    exit;
  end;
  Result:=AVL_DropNode(Tree^.childs[c>0],aKey,DropedNode);
  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:=AVL_FixWithRotateLeft(Tree);
      -1,1: Result:=false;
      2: Result:=AVL_FixWithRotateRight(Tree);
    end;
  end;
end;

Доведемо, що даний алгоритм зберігає балансування. Для цього доведемо по індукції по висоті дерева, що після видалення деякої вершини з дерева і наступної балансування висота дерева зменшується не більше, ніж на 1. База індукції: Для листа очевидно вірно. Крок індукції: Або умова балансування в корені (після видалення корінь може зміниться) не порушилося, тоді висота даного дерева не змінилася, або зменшилася суворо менше з піддерев => висота до балансування не змінилася => після зменшиться не більше ніж на 1.

Очевидно, в результаті вказаних дій процедура видалення викликається не більше 3 разів, так як у вершини, що видаляється по 2-му викликом, немає одного з піддерев. Але пошук найближчого щоразу вимагає 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;
  DropedNode:PAVLNode;
begin
  p:=nil;
  q:=@Root;
  PrimeNode:=q;
  last:=false;
  DropedNode:=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
      DropedNode:=p^;
    end;
  end;
  if DropedNode=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;
  DropedNode^.Key:=p^^.Key;
  DropedNode^.info:=p^^.info;
  DropedNode:=p^;
  //поставимо замість поточного лист з протилежного напрямку
  p^:=p^^.childs[(p^^.Left=nil)];
  Dispose(DropedNode);
end;

Сам алгоритм без всіх оптимізацій для спрощення його розуміння. На відміну від рекурсивного алгоритму при знаходженні удаляемой вершини вона буде замінена значенням з лівої подветві, даний алгоритм можна оптимізувати так само як і для рекурсивної версії за рахунок того що після знаходження удаляемой вершини напрямок руху нам відомо

Шукаємо видаляється елемент і попутно знаходимо нашу чудову вершину
Виконуємо зміна балансів, в разі необхідності робимо ребалансировки
Видаляємо наш елемент (в дійсності не видаляємо, а заміняємо його ключ і значення, врахування перестановок вершин буде трохи складніше)

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

Як вже говорилося, якщо видаляється вершина — листок, то вона видаляється, і зворотний обхід дерева походить від батька віддаленого листка. Якщо не лист — їй знаходиться «заміна», і зворотний обхід дерева походить від батька «заміни». Безпосередньо після видалення елемента — «заміна» отримує баланс видаляється вузла.

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

Це робиться до тих пір, поки при зміні балансу він не стане рівним −1 або 1 (зверніть увагу на відмінність з вставкою елемента!): В даному випадку така зміна балансу буде гласить про незмінною дельта-висоті піддерев. Повороти відбуваються за тими ж правилами, що і при вставці.

Розстановка балансів при одинарному повороті

Позначимо:

«Current» — вузол, баланс якого дорівнює −2 або 2: тобто той, який потрібно повернути (на схемі — елемент a)

«Pivot» — вісь обертання. +2: Лівий син Current'а, −2: правий син Current'а (на схемі — елемент b)

Якщо поворот здійснюється при вставці елементу, то баланс 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

Оцінка ефективності

Г. М. Адельсон-Вельський і Е. М. Ландіс довели теорему, згідно з якою висота АВЛ-дерева з N внутрішніми вершинами укладена між log2 (N +1) і 1.4404 * log2 (N +2) −0.328, тобто висота АВЛ -дерева ніколи не перевищить висоту ідеально збалансованого дерева більш, ніж на 45%. Для великих N має місце оцінка 1.04 * log2 (N). Таким чином, виконання основних операцій 1 — 3 вимагає порядку log ₂ (N) порівнянь. Експериментально з'ясовано, що одна балансування припадає на кожні два включення і на кожні п'ять видалень.

Література

Ніклаус Вірт (2004) [1975]. Algorithms and Data Structures (PDF). ETH Zürich. с. 366.(англ.)
Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — ISBN 0-201-89685-0.(англ.)
Г. М. Адельсон-Вельский, Е. М. Ландис. Один алгоритм организации информации // Доклады АН СССР. 1962. Т. 146, № 2. C. 263–266.
GNU libavl 2012 Ben Pfaff.

Див. також

Червоно-чорне дерево

п о р Деревні структури даних
Дерева пошуку (динамічні множини/асоціативні масиви)	2–3^[en] 2–3–4^[en] АА^[en] (a,b)(інші мови) АВЛ Б Б+ Б*(інші мови) Б^x^[en] (Оптимальний^[en]) Двійковий пошук Збалансоване за вагою^[en] Інтервальне^[en] Порядкова статистика^[en] Рандомізований двійковий пошук^[en] Розширюване Т^[en] Танцювальне^[en] ХДерево^[en] Цап-відбувайло^[en] (Лівобічне^[en]) Червоно-чорне UB
Купи	Біноміальна Ван Емде Боаса Двійкова Лівацька^[en] Скошена^[en] Спарена^[en] Фібоначчієва
Префіксні дерева	Базисне Суфіксне Тернарного пошуку Хеш^[en] X-швидке^[en] Y-швидке^[en]
Дерева просторового розбиття даних	БВП^[en] БК^[en] БРП Відрізків ВП^[en] Гільбертове R^[en] Декартове k-вимірне (неявне k-вимірне^[en]) Дерево квадрантів М^[en] Метричне^[en] Октодерево Пріоритетизоване R^[en] R R+^[en] R* X^[en]
Інші дерева	Двозв'язкове^[en] Динамічне^[en] Діапазонне^[en] Експоненційне^[en] Злиття^[en] iDistance^[en] k-арне^[en] LSM Дерево Меркла Над^[en] Некореневе двійкове Пальцеве^[en] PQ Покриттів^[en] SPQR^[en] Фенвіка Хеш-календар^[en]