Збалансоване дерево

Матеріал з Вікіпедії — вільної енциклопедії.

В програмуванні збалансоване дерево в загальному розумінні цього слова -- це такий різновид бінарного дерева пошуку, яке автоматично підтримує свою висоту, тобто кількість рівнів вершин під коренем, мінімальною. Ця властивість є важливою тому, що час виконання більшість алгоритмів на бінарних деревах пошуку пропорційний до їхньої висоти, і звичайні бінарні дерева пошуку можуть мати досить велику висоту в тривіальних ситуаціях. Процедура зменшення (балансування) висоти дерева виконується за допомогою трансформацій, відомих як обернення дерева, в певні моменти часу (переважно при видаленні або додаванні нових елементів).

Більш строге визначення збалансованих дерев було дане Г.Адельсон-Вельським та Є.Ландісом. Ідеально збалансованим деревом за Адельсон-Вельським та Ландісом є таке, у якого для кожної вершини різниця між висотами лівого та правого піддерев не перевищує одиниці. Однак, така умова доволі складна для виконання на практиці і може вимагати значної перебудови дерева при додаванні або видаленні елементів.

Тому було запропоноване менш строге визначення, яке отримало назву умови АВЛ(AVL)-збалансованості і говорить, що бінарне дерево є збалансованим, якщо висоти лівого та правого піддерев різняться не більше ніж на одиницію. Дерева, що задовольняють таким умовам, називаються AVL-деревами. Зрозуміло, що кожне ідеально збалансоване дерево є також АВЛ-збалансованим, але не навпаки.

[ред.] Дивись також

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