Збалансоване дерево
У програмуванні збалансоване дерево в загальному розумінні цього слова — це такий різновид двійкового дерева пошуку, яке автоматично підтримує свою висоту, тобто кількість рівнів вершин під коренем є мінімальною.
Загальні відомості
Швидкість роботи більшості операцій на деревах залежить від висоти дерева. Такими операціями в першу чергу є:
- пошук вершини
- вставка вершини
- видалення вершини
Швидкість цих операцій напряму залежить від висоти дерева -- O(Height). Якщо говорити про залежність між кількістю вершин в дереві та його висотою, то висота дерева лежить у таких межах:
- H = N Висота дерева дорівнює кількості вершин у дереві, якщо дерево є виродженим.
- H = log(N) Висота дерева дорівнює логарифму, якщо дерево є повним.
Збалансованість дерева є важливою саме тому, що час виконання більшості алгоритмів на двійкових деревах пошуку є пропорційний до їхньої висоти. Звичайні двійкові дерева пошуку можуть мати досить велику висоту в тривіальних ситуаціях, що від’ємно впливає на швидкість виконання операцій.
Процедура зменшення (балансування) висоти дерева виконується за допомогою трансформацій, відомих як обернення дерева, в певні моменти часу (переважно при видаленні або додаванні нових елементів).
Визначення збалансованості
Більш точне визначення збалансованих дерев було дане Г. Адельсон-Вельським та Є. Ландісом.
Ідеально збалансоване дерево
Ідеально збалансоване дерево, за Г. Адельсон-Вельським та Є. Ландісом— це дерево, у якого для кожної вершини різниця між висотами лівого та правого піддерев не перевищує одиниці. Однак, така умова доволі складна для виконання на практиці і може вимагати значної перебудови дерева при додаванні або видаленні елементів.
АВЛ-збалансованість (AVL-збалансованість)
Підтримка ідеальної збалансованості на практиці може бути досягнуто частими перебудовами дерева, що може помітно вплинути на час виконання операцій. Тому було запропоноване менш строге визначення, яке отримало назву АВЛ-збалансованості. Воно говорить, що бінарне дерево є збалансованим, якщо висоти лівого та правого піддерев різняться не більше ніж на одиницю. Дерева, що задовольняють таким умовам, називаються АВЛ-деревами. Зрозуміло, що кожне ідеально збалансоване дерево є також АВЛ-збалансованим, але не навпаки.
Див. також
Джерела
- Г. М. Адельсон-Вельський, Є. М. Ландіс, “Один алгоритм організації інформацій”, Докл. АН СССР, 146:2 (1962) (російською мовою)
 | Ця стаття не містить посилань на джерела. (січень 2010) |
|
Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її. |