Ан Дерево AVL визначається як самобалансування Різниця між висотами лівого піддерева і правого піддерева для будь-якого вузла відома як фактор балансу вузла.

Дерево AVL названо на честь його винахідників Георгія Адельсона-Вельського та Євгенія Ландіса, які опублікували його у своїй статті «Алгоритм організації інформації» 1962 року.

Приклад дерев AVL:

Дерево AVL

Наведене вище дерево є AVL, оскільки різниця між висотами лівого та правого піддерев для кожного вузла менше або дорівнює 1.

Операції над деревом AVL:

• Вставка
• Видалення
• Пошук [Це схоже на виконання пошуку в BST]

Обертання піддерев у дереві AVL:

Дерево AVL може обертатися одним із наступних чотирьох способів, щоб підтримувати баланс:

Обертання вліво :

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

Обертання вліво в дереві AVL

Обертання вправо :

Якщо до лівого піддерева лівого піддерева додається вузол, дерево AVL може вийти з рівноваги, ми виконуємо один поворот праворуч.

Обертання вправо в дереві AVL

Обертання вліво-вправо :

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

Обертання вліво-вправо в дереві AVL

Обертання вправо-вліво :

замінити всю java

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

Обертання вправо-вліво в дереві AVL

Застосування дерева AVL:

1. Він використовується для індексування величезних записів у базі даних, а також для ефективного пошуку в ній.
2. Для всіх типів колекцій у пам’яті, включаючи набори та словники, використовуються дерева AVL.
3. Програми баз даних, де вставки та видалення менш поширені, але потрібен частий пошук даних
4. Програмне забезпечення, яке потребує оптимізованого пошуку.
5. Застосовується в корпоративних зонах і сюжетних іграх.

Переваги AVL Tree:

1. Дерева AVL можуть самостійно балансувати.
2. Він точно не перекошений.
3. Він забезпечує швидший пошук, ніж Red-Black Trees
4. Краща складність часу пошуку порівняно з іншими деревами, такими як двійкове дерево.
5. Висота не може перевищувати log(N), де N — загальна кількість вузлів у дереві.

Недоліки AVL Tree:

1. Важко реалізувати.
2. Він має високі постійні коефіцієнти для деяких операцій.
3. Менше використовується порівняно з червоно-чорними деревами.
4. Завдяки досить суворому балансу дерева AVL забезпечують складні операції вставки та видалення, оскільки виконується більше обертань.
5. Візьміть більше обробки для балансування.

Пов'язані статті:

• Вступ до бінарних дерев пошуку – Навчальні посібники зі структури даних і алгоритмів
• Вставка в дерево AVL
• Видалення в дереві AVL