У програмуванні збалансоване дерево в загальному розумінні цього слова — це такий різновид двійкового дерева пошуку, яке автоматично підтримує свою висоту, тобто кількість рівнів вершин під коренем є мінімальною.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWhMMkU1TDFWdVltRnNZVzVqWldSZlltbHVZWEo1WDNSeVpXVXVjM1puTHpJMU1YQjRMVlZ1WW1Gc1lXNWpaV1JmWW1sdVlYSjVYM1J5WldVdWMzWm5MbkJ1Wnc9PS5wbmc=.png)
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHdMekEyTDBGV1RIUnlaV1ZtTG5OMlp5OHlOVEZ3ZUMxQlZreDBjbVZsWmk1emRtY3VjRzVuLnBuZw==.png)
Загальні відомості
Швидкість роботи більшості операцій на деревах залежить від висоти дерева. Такими операціями в першу чергу є:
- пошук вершини
- вставка вершини
- видалення вершини
Швидкість цих операцій напряму залежить від висоти дерева -- O(Height). Якщо говорити про залежність між кількістю вершин в дереві та його висотою, то висота дерева лежить у таких межах:
- H = N Висота дерева дорівнює кількості вершин у дереві, якщо дерево є виродженим.
- H = log(N) Висота дерева дорівнює логарифму, якщо дерево є повним.
Збалансованість дерева є важливою саме тому, що час виконання більшості алгоритмів на двійкових деревах пошуку є пропорційний до їхньої висоти. Звичайні двійкові дерева пошуку можуть мати досить велику висоту в тривіальних ситуаціях, що від’ємно впливає на швидкість виконання операцій.
Процедура зменшення (балансування) висоти дерева виконується за допомогою трансформацій, відомих як обернення дерева, у певні моменти часу (переважно при видаленні або додаванні нових елементів).
Ступені збалансованості
Ідеально збалансоване дерево
Ідеально збалансоване дерево — це дерево, у якого для кожної вершини різниця між висотами лівого та правого піддерев не перевищує одиниці[ ][]. Однак, така умова може вимагати значної перебудови дерева при додаванні або видаленні елементів, тому їх застосовують лише для пошуку, коли дані в них практично незмінні.
АВЛ-збалансованість
При додаванні в дерево нових вузлів або внаслідок їх вилучення ідеальна збалансованість втрачається. Дерево можна перебудувати, але така операція триває досить довго. Тому було запропоновано слабші вимоги щодо збалансованості, які отримали назву АВЛ-збалансованості. Дерево є АВЛ-збалансованим, якщо висоти лівого та правого піддерев різняться не більше, ніж на одиницю. Дерева, що задовольняють таким умовам, називають (АВЛ-деревами) (за прізвищами їх винахідників — Адельсон-Вельського і (Ландіса)). Зрозуміло, що кожне ідеально збалансоване дерево є також АВЛ-збалансованим, але не навпаки.
Див. також
- АВЛ-дерево
- (B-дерево)
- Червоно-чорне дерево
- Розширюване дерево
Примітки
- Адельсон-Вельський, Ландіс, 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.(рос.)
![]() | Це незавершена стаття про інформаційні технології. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет