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

АВЛ-дерево — збалансоване по висоті двійкове дерево пошуку: для кожної його вершини висота її двох піддерев відрізняється не більше ніж на 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. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.)
Г. М. Адельсон-Вельский, Е. М. Ландис. Один алгоритм организации информации // Доклады АН СССР. 1962. Т. 146, № 2. C. 263–266.
GNU libavl 2012 Ben Pfaff.

Див. також

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