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