У програмуванні збалансоване дерево в загальному розумінні цього слова це такий різновид двійкового дерева пошуку яке ав

У програмуванні збалансоване дерево в загальному розумінні цього слова — це такий різновид двійкового дерева пошуку, яке автоматично підтримує свою висоту, тобто кількість рівнів вершин під коренем є мінімальною.

Загальні відомості

Швидкість роботи більшості операцій на деревах залежить від висоти дерева. Такими операціями в першу чергу є:

пошук вершини
вставка вершини
видалення вершини

Швидкість цих операцій напряму залежить від висоти дерева -- O(Height). Якщо говорити про залежність між кількістю вершин в дереві та його висотою, то висота дерева лежить у таких межах:

H = N Висота дерева дорівнює кількості вершин у дереві, якщо дерево є виродженим.
H = log(N) Висота дерева дорівнює логарифму, якщо дерево є повним.

Збалансованість дерева є важливою саме тому, що час виконання більшості алгоритмів на двійкових деревах пошуку є пропорційний до їхньої висоти. Звичайні двійкові дерева пошуку можуть мати досить велику висоту в тривіальних ситуаціях, що від’ємно впливає на швидкість виконання операцій.

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

Ступені збалансованості

Ідеально збалансоване дерево

Ідеально збалансоване дерево — це дерево, у якого для кожної вершини різниця між висотами лівого та правого піддерев не перевищує одиниці^{[ — ]}^[]. Однак, така умова може вимагати значної перебудови дерева при додаванні або видаленні елементів, тому їх застосовують лише для пошуку, коли дані в них практично незмінні.

АВЛ-збалансованість

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

Див. також

Примітки

Адельсон-Вельський, Ландіс, 1962, с. 263—266.

Джерела

Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.)
Гудзь Р. В., Ярошко С. А. Використання динамічних структур даних у програмах на Borland Pascal: Тексти лекцій. — Львів : Ред.-вид. відділ ОЦ ЛНУ ім. І. Франка, 2000.
Г. М. Адельсон-Вельський. Один алгоритм организации информации / Г. М. Адельсон-Вельський, Е. М. Ландис // Докл. АН СССР. — 1962. — Т. 146, № 2. — С. 263–266.(рос.)

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

[FOOTNOTEАдельсон-Вельський,_Ландіс1962263—266-1] Адельсон-Вельський, Ландіс, 1962, с. 263—266.