Page 51 - 6110

6 else x:= right[y]
7 if x <> NULL
8 then p[x]:=p[y]
9 if p[y]:=NULL
10 then root[T]:=x
11 else if y=left[p[y]]
12 then left[p[y]] :=x
13 else right[p[y]]:=x
14 if y <> z
15 then val[z]:=val[y]
16 //копіювання додаткових даних з y
17 return y

В програмуванні збалансоване дерево в загальному розумінні
цього слова – це такий різновид бінарного дерева пошуку, яке
автоматично підтримує свою висоту, тобто кількість рівнів вершин
під коренем, мінімальною. Ця властивість є важливою тому, що час
виконання більшості алгоритмів на бінарних деревах пошуку
пропорційний до їх висоти, і звичайні бінарні дерева пошуку
можуть мати досить велику висоту в тривіальних ситуаціях.
Процедура зменшення (балансування) висоти дерева виконується за
допомогою трансформацій, відомих як обернення дерева, в певні
моменти часу (переважно при видаленні або додаванні нових
елементів).
Більш строге визначення збалансованих дерев було дане
Г.Адельсон-Вельським та Є.Ландісом. Ідеально збалансованим
деревом за Адельсон-Вельським та Ландісом є таке, у якого для
кожної вершини різниця між висотами лівого та правого піддерев
не перевищує одиниці. Однак, така умова доволі складна для
виконання на практиці і може вимагати значної перебудови дерева
при додаванні або видаленні елементів.
Тому було запропоноване менш строге визначення, яке
отримало назву умови АВЛ(AVL)-збалансованості і говорить, що
бінарне дерево є збалансованим, якщо висоти лівого та правого
піддерев різняться не більше ніж на одиницію. Дерева, що
задовольняють таким умовам, називаються AVL-деревами.
Зрозуміло, що кожне ідеально збалансоване дерево є також АВЛ-
збалансованим, але не навпаки.
Червоно-чорне дерево (red-black tree) в інформатиці – це
різновид бінарного дерева пошуку, вершини якого мають додаткові
властивості (RB-властивості), зокрема “колір” (червоний або
чорний). Червоно-чорні дерева – це різновид збалансованих дерев, в
яких за допомогою спеціальних трансформацій гарантується, що
висота дерева h не буде перевищувати Т(log n). Зважаючи на те, що
50