 ПОЗНАВАТЕЛЬНОЕ
| Алгоритм додавання об'єкта до дерева
Наведемо кроки алгоритму. Крок 1. Почати з кореня. Крок 2. Якщо об'єкт менший, ніж ключ у вершині, то перейти до лівого сина. Крок 3. Якщо об'єкт більший, ніж ключ у вершині, то перейти до правого сина. Крок 4. Повторювати кроки 2 та 3, доки не досягнемо вершини, яку не визначено (тобто її немає). Крок 5. Якщо досягнуто невизначену вершину, то визначити (тобто додати) вершину з новим об'єктом як ключем. Приклад 4.11. Побудуємо бінарне дерево пошуку для такого списку слів в українському алфавіті: математика, фізика, географія, зоологія, метеорологія, біологія, психологія, хімія. Процес побудови зображено на рис. 4.17.
Рис. 4.17. Бінарне дерево наук
Оскільки метод побудови дерева пошуку описано, легко зрозуміти, як відбувається пошук елемента в дереві. Застосовують переважно той самий підхід. Окрім перевірки того, чи даний об'єкт більший або менший, ніж ключ у вершині, перевіряють також, чи збігається даний об'єкт із ключем у вершині. Якщо так, то процес пошуку завершено, якщо ні - описані дії повторюють. Якщо ж досягнуто вершину, яку не визначено, то це означає, що даний об'єкт не зберігається в дереві. Нижче наведено алгоритм пошуку об'єкта в бінарному дереві. Алгоритм пошуку об'єкта в дереві Наведемо кроки алгоритму. Крок 1. Почати з кореня. Крок 2. Якщо об'єкт менший, ніж ключ у вершині, то перейти до лівого сина. Крок 3. Якщо об'єкт більший, ніж ключ у вершині, то перейти до правого сина. Крок 4. Якщо об'єкт дорівнює ключу у вершині, то об'єкт знайдено; виконати потрібні дії й вийти. Крок 5. Повторювати кроки 2, 3 та 4, доки не досягнемо вершини, яку не визначено. Крок 6. Якщо досягнуто невизначену вершину, то даний об'єкт не зберігається в дереві; виконати потрібні дії й вийти. Оцінимо обчислювальну складність алгоритмів включення та пошуку (локалізації) об'єкта в бінарному дереві пошуку. Припустимо, що є бінарне дерево пошуку T для списку з n об'єктів. Із дерева Т утворимо повне бінарне дерево U, для чого додамо нові вершини (без ключів) так, щоб кожна вершина з ключем мала двох синів. Це показано на рис. 4.18, де вершини без ключів позначено подвійними кружечками.
Рис. 4.18. Оцінка обчислювальної складності
Коли це зроблено, можна легко локалізувати об'єкт або додати новий об'єкт як ключ без додавання вершини. Найбільша кількість порівнянь, потрібних для додавання нового об'єкта, дорівнює довжині найдовшого шляху в U від кореня до листка, тобто висоті дерева. Внутрішні вершини дерева U — це (всі) вершини дерева Т. Отже, дерево U має n внутрішніх вершин. За теоремою 4.2 кількість листків у ньому дорівнює 2n+1–n=n+1. Згідно з наслідком із теореми 4.3 висота дерева U більша чи дорівнює élog(n+1)ù. Отже, потрібно щонайменше і élog(n+1)ù порівнянь, щоб додати чи локалізувати довільний об'єкт. Якщо дерево збалансоване, то його висота дорівнює élog(n+1)ù. Отже, у цьому разі для додавання чи локалізації об'єкта потрібно не більше ніж élog(n+1)ù порівнянь. Бінарне дерево пошуку може розбалансуватись унаслідок додавання нових об'єктів, тому потрібен алгоритм ребалансування (тобто відновлення зба-лансованості). Проте процедура додавання об'єкта, яка відновлює збалансоване дерево, навряд чи завжди доцільна, бо відновлення збалансованості дерева після випадкового додавання — досить складна операція. Тому розглядають також збалансованість із дещо послабленими вимогами; зокрема, означають АВЛ-дерево — бінарне дерево, у якому висоти двох піддерев кожної з його вершин відрізняються не більше ніж на одиницю. Таке означення збалансованості широко використовують на практиці; його ввели 1962 р. Г. М. Адель-сон-Вельський і Є. М. Ландіс. Приклад АВЛ-дерева наведено на рис. 4.19.
Рис. 4.19. Приклад АВЛ-дерева
Для АВЛ-дерев є дуже ефективна процедура ребалансування. Водночас висота АВЛ-дерева незалежно від кількості вершин ніколи не перевищує висоту збалансованого дерева більше, ніж на 45%. Якщо позначити висоту АВЛ-дерева з n вершинами як h(n), то log(n+1) ≤ h(n) < 1.44 log(n + 2)–0.328.
|
