Балансування дерев: AVL-дерева

4.1 Проблеми незбалансованих дерев

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

1. Збільшення висоти дерева:

У незбалансованих деревах висота може досягати n (де n — кількість вузлів), що призводить до деградації продуктивності.

Час виконання основних операцій (пошук, вставка, видалення) в найгіршому випадку стає O(n).

2. Нерівномірний розподіл вузлів:

У незбалансованих деревах деякі піддерева можуть містити значно більше вузлів, ніж інші, що призводить до неефективного використання пам'яті та збільшення часу обробки.

3. Погіршення часу виконання операцій:

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

Приклад незбалансованого дерева:

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

4.2 Визначення AVL-дерева та його властивості

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

Властивості AVL-дерева:

1. Збалансованість:

Різниця висот лівого і правого піддерев будь-якого вузла не перевищує 1.

Це забезпечує висоту дерева O(log n), де n — кількість вузлів, що гарантує ефективне виконання операцій пошуку, вставки і видалення.

2. Бінарне дерево пошуку:

AVL-дерево має всі властивості бінарного дерева пошуку: для будь-якого вузла всі ключі в лівому піддереві менші за ключ вузла, а всі ключі в правому піддереві більші за ключ вузла.

3. Автоматичне балансування:

Після кожної операції вставки або видалення виконується балансування дерева, щоб зберегти його властивості.

4.3 Приклади балансування дерев

Обертання — це операції, які виконуються для відновлення балансу у AVL-дереві після вставки або видалення вузлів. Існує чотири типи обертань: ліве, праве, ліво-праве і право-ліве.

1. Ліве обертання (Left Rotation):

В лівому обертанні вузол x піднімається вгору, а його правий дочірній вузол y стає його батьком. Ліве піддерево y стає правим піддеревом x.

2. Праве обертання (Right Rotation):

В правому обертанні вузол x піднімається вгору, а його лівий дочірній вузол y стає його батьком. Праве піддерево y стає лівим піддеревом x.

3. Ліво-праве обертання (Left-Right Rotation):

Спочатку виконується ліве обертання на лівому дочірньому вузлі, а потім праве обертання на самому вузлі.

4. Право-ліве обертання (Right-Left Rotation):

Спочатку виконується праве обертання на правому дочірньому вузлі, а потім ліве обертання на самому вузлі.

4.4 Основні операції в AVL-деревах

Основні операції в AVL-деревах включають вставку, видалення та пошук.

Вставка (Insertion)

Потрібно вставити новий вузол у AVL-дерево та збалансувати його, якщо потрібно.

Кроки:

1. Вставка вузла:
   • Починаємо з кореня дерева та рекурсивно знаходимо правильне місце для нового вузла, порівнюючи його значення з поточними вузлами.
   • Вставляємо новий вузол у знайдене місце, як у звичайному бінарному дереві пошуку.
2. Оновлення висот:
   • Після вставки оновлюємо висоти всіх вузлів по шляху від нового вузла до кореня.
3. Балансування дерева:
   • Перевіряємо баланс кожного вузла по шляху від нового вузла до кореня.
   • Якщо баланс якогось вузла порушено (різниця висот лівого і правого піддерев більше 1), виконуємо відповідне обертання для відновлення балансу.

Приклад:

2. Видалення (Deletion)

Потрібно видалити вузол із AVL-дерева та збалансувати його, якщо потрібно.

Кроки:

1. Пошук та видалення вузла:

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

2. Оновлення висот:

• Після видалення оновлюємо висоти всіх вузлів по шляху від видаленого вузла до кореня.

3. Балансування дерева:

• Перевіряємо баланс кожного вузла по шляху від видаленого вузла до кореня.
• Якщо баланс якогось вузла порушено, виконуємо відповідне обертання для відновлення балансу.

Приклад:

3. Пошук (Search)

Потрібно знайти вузол з заданим значенням у AVL-дереві.

Кроки:

1. Рекурсивний пошук:

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

Приклад: