АВЛ-дерево — Вікіпедія

Ця стаття є сирим перекладом з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. Будь ласка, допоможіть поліпшити переклад. (березень 2016)

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

АВЛ — абревіатура, утворена першими літерами творців (радянських учених) Адельсон-Вельського Георгія Максимовича і Ландіса Євгена Михайловича.

У АВЛ-дереві висоти ${\displaystyle h}$ є не менше ${\displaystyle F_{h}}$ вузлів, де ${\displaystyle F_{h}}$ — число Фібоначчі. Оскільки ${\displaystyle 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}}}}$,

де ${\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}}$ — золотий перетин,

то маємо оцінку на висоту АВЛ-дерева ${\displaystyle h=O(log(n))}$, де ${\displaystyle n}$ — число вузлів. Слід пам'ятати, що ${\displaystyle O(log(n))}$ — мажоранта, і її можна використовувати лише для оцінки (Наприклад, якщо в дереві тільки два вузли, значить в дереві два рівні, хоча ${\displaystyle 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, описаному вище. Безпосередньо при вставці (листу) присвоюється нульовий баланс. Процес включення вершини складається з трьох частин:

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

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

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

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

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:

Pivot і Current — ті ж самі, але додається третій учасник повороту. Позначимо його за «Bottom»: це (при подвійному правому повороті) лівий син Pivot'а, а при подвійному лівому — правий син Pivot'а.

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

Наведемо зведену таблицю залежності фінальних балансів від напрямку повороту і вихідного балансу вузла Bottom:

Г. М. Адельсон-Вельський і Е. М. Ландіс довели теорему, згідно з якою висота АВЛ-дерева з 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.

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