АВЛ-дерево

АВЛ-дерево — збалансоване по висоті двійкове дерево пошуку: для кожної його вершини висота її двох піддерев відрізняється не більше ніж на 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, описаному вище. Безпосередньо при вставці (листу) присвоюється нульовий баланс. Процес включення вершини складається з трьох частин:

  1. Прохода по шляху пошуку, поки не переконаємося, що ключа в дереві немає.
  2. Включення нової вершини у дерево і визначення результуючих показників балансування.
  3. «Відступи» назад по шляху пошуку і перевірки в кожній вершині показника збалансованості. Якщо необхідно — балансування.

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

  1. hl < hr: вирівняється hl = hr. Нічого робити не потрібно.
  2. hl = hr: тепер ліве піддерево буде більше на одиницю, але балансування поки не потрібно.
  3. 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; 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)).

Нерекурсивна вставка в АВЛ-дерево зверху-вниз

Нерекурсивний алгоритм складніший ніж рекурсивна реалізація.

  1. Знаходиться місце вставки і вершина висота якої не зміниться при вставці (це вершина у якої висота лівого піддерева не дорівнює висоті правого, будемо називати її PrimeNode)
  2. Виконується спуск від PrimeNode до місця вставки зі зміною балансів
  3. Виконується ребалансування 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;

Нерекурсивне видалення з АВЛ-дерева зверху-вниз

Для реалізації видалення будемо виходити з того ж принципу що і при вставці, будемо шукати вершину, видалення з якої не призведе до зміни її висоти, існують усього два таких варіанти

  1. Найпростіший, коли висота лівого піддерева дорівнює висоті правого піддерева (виключаючи випадок коли у листка немає піддерев)
  2. Коли висота дерева у напрямку руху менше протилежної («брат» напряму) і баланс «брата» дорівнює 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. Шукаємо видаляється елемент і попутно знаходимо нашу чудову вершину
  2. Виконуємо зміна балансів, в разі необхідності робимо ребалансировки
  3. Видаляємо наш елемент (в дійсності не видаляємо, а заміняємо його ключ і значення, врахування перестановок вершин буде трохи складніше)

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

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

При зворотному обході: якщо при переході до батька прийшли зліва — баланс збільшується на 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 2 (N) порівнянь. Експериментально з'ясовано, що одна балансування припадає на кожні два включення і на кожні п'ять видалень.

Література

  • Вирт Н. Алгоритмы и структуры данных М.:Мир, 1989. Глава 4.5 (С. 272-286)
  • Г. М. Адельсон-Вельский, Е. М. Ландис. Один алгоритм организации информации // Доклады АН СССР. 1962. Т. 146, № 2. C. 263–266.
  • GNU libavl 2012 Ben Pfaff.

Див. також


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.