ся тоді, коли (висота b-поддерева - висота L)=2 і висота З lt;=висота R.
. Велике ліве обертання
Дане обертання використовується тоді, коли (висота b-поддерева - висота L)=2 і висота c-поддерева gt; висота R.
. Мале праве обертання
Дане обертання використовується тоді, коли (висота b-поддерева - висота R)=2 і висота З lt;=висота L.
. Велике праве обертання
Дане обертання використовується тоді, коли (висота b-поддерева - висота R)=2 і висота c-поддерева gt; висота L.
У кожному випадку досить просто довести те, що операція приводить до потрібного результату і що повна висота зменшується не більше ніж на 1 і не може збільшитися.
Через умови балансуванні висота дерева О (lg (N)), де N - кількість вершин, тому додавання елемента вимагає O (lg (N)) операцій.
Алгоритм додавання вершини
Показник збалансованості надалі будемо інтерпретувати як різниця між висотою лівого і правого піддерева, а алгоритм буде заснована на типі TAVLTree, описаному вище. Безпосередньо при вставці (листу) присвоюється нульовий баланс. Процес включення вершини складається з трьох частин:
. Проходу по шляху пошуку, поки не переконаємося, що ключа в дереві немає.
2. Включення нової вершини в дерево і визначення результуючих показників балансування.
. Нехтування назад по шляху пошуку і перевірки в кожній вершині показника збалансованості. Якщо необхідно - балансування.
Розширимо список параметрів звичайної процедури вставки параметром-змінною flag, що означає, що висота дерева збільшилася. Припустимо, що процес з лівої гілки повертається до батькові чи матері (рекурсія йде назад), тоді можливі три випадки: {hl - висота лівого піддерева, hr - висота правого піддерева} Включення вершини в ліве піддерево призведе до
. h l lt; h r: вирівняється h l=h r. Нічого робити не потрібно.
2. hl=hr: тепер ліве піддерево буде більше на одиницю, але балансування поки не потрібно.
. h l gt; hr: тепер hl - hr=2, - потрібно балансування.
У третій ситуації потрібно визначити балансування лівого піддерева. Якщо ліве піддерево цієї вершини (Tree ^. Left ^. Left) вище правого (Tree ^. Left ^. Right), то потребує подвійного правий поворот, інакше вистачить і малого. Аналогічні (симетричні) міркування можна привести і для включення в праве піддерево. Процедура вставки запропонована Н. Віртом
TAVL. InsertNode (Var Tree: TAVLTree; const akey: TKey; const ainfo: TInfo; Var flag: Boolean);
Var, Node2: TAVLTree; Tree=nil then (Tree) ;:=true; Tree ^ do:=akey ;:=ainfo ;:=nil ;:=nil ;:=0 ;; (AVL. FNodes); if Tree ^. key gt; akey then (Tree ^. left, akey, ainfo, flag); flag thenTree ^. balance of
: begin Tree ^. balance:=0; flag:=false; end;
: Tree ^. balance:=- 1;
: {Balance}:=Tree ^. left; Node1 ^. balance=- 1 then
{LL} ^. left:=Node1 ^. right; ^. right:=Tree; ^. balance:=0 ;:=Node1;
{LR}:=Node1 ^. right; ^. right:=Node2 ^. left; ^. left:=Node1; ^. left:=Node2 ^. right; ^. right:=Tree; Node2 ^. balance=- 1 then Tree ^. balance:=1 else Tree ^. balance:=0; Node2 ^. balance=1 then Node1 ^. balance:=- 1 else Node1 ^. balance:=0 ;:=Node2 ;; ^. balance:=0 ;:=falseif Tree ^. key lt; akey then (Tree ^. right, akey, ainfo, flag); flag thenTree ^. balance of
: begin Tree ^. balance:=0; flag:=false; end;
: Tree ^. balance:=1;
: {Balance}:=Tree ^. right; Node1 ^. balance=1 then
{RR} ^. right:=Node1 ^. left; ^. left:=Tree; ^. balance:=0 ;:=Node1;
{RL}:=Node1 ^. left; ^. left:=Node2 ^. right; ^. right:=Node1; ^. right:=Node2 ^. left; ^. left:=Tree; Node2 ^. balance=1 then Tree ^. balance:=- 1 else Tree ^. balance:=0; Node2 ^. balance=- 1 then Node1 ^. balance:=1 else Node1 ^. balance:=0 ;:=Node2 ;; ^. balance:=0 ;:=false;
Алгоритм видалення вершини
Для простоти опишемо рекурсивний алгоритм видалення. Якщо вершина - лист, то видалимо його і викличемо балансування всіх її предків у порядку від батька до кореня. Інакше знайдемо саму близьку за значенням вершину в поддереве найбільшої висоти (правому або лівому) і перемістимо її на місце удаляемой вершини, при цьому викликавши процедуру її видалення.
Доведемо, що даний алгоритм зберігає балансування. Для цього доведемо по інду...
