Дерево AVL винайшли Г. М. Адельсон-Вельський та Е. М. Ландіс у 1962 році. Дерево названо AVL на честь своїх винахідників.
Дерево AVL можна визначити як збалансоване за висотою бінарне дерево пошуку, у якому кожен вузол пов’язаний із коефіцієнтом балансу, який обчислюється шляхом віднімання висоти правого піддерева від висоти лівого піддерева.
Дерево вважається збалансованим, якщо коефіцієнт балансу кожного вузла становить від -1 до 1, інакше дерево буде незбалансованим і його потрібно збалансувати.
Фактор балансу (k) = висота (ліворуч (k)) - висота (праворуч (k))
Якщо коефіцієнт балансу будь-якого вузла дорівнює 1, це означає, що ліве піддерево на один рівень вище, ніж праве піддерево.
Якщо коефіцієнт балансу будь-якого вузла дорівнює 0, це означає, що ліве піддерево та праве піддерево мають однакову висоту.
Якщо коефіцієнт балансу будь-якого вузла дорівнює -1, це означає, що ліве піддерево на один рівень нижче, ніж праве піддерево.
Дерево AVL наведено на наступному малюнку. Ми бачимо, що коефіцієнт балансу, пов’язаний з кожним вузлом, знаходиться в межах від -1 до +1. отже, це приклад дерева AVL.
Складність
| Алгоритм | Середній випадок | Найгірший випадок |
|---|---|---|
| космос | o(n) | o(n) |
| Пошук | o(log n) | o(log n) |
| Вставка | o(log n) | o(log n) |
| Видалити | o(log n) | o(log n) |
Операції над деревом AVL
Через те, що дерево AVL також є бінарним деревом пошуку, тому всі операції виконуються так само, як і в бінарному дереві пошуку. Пошук і обхід не призводять до порушення властивості дерева AVL. Однак операції вставки та видалення можуть порушити цю властивість, тому їх потрібно переглянути.
сортування кортежів python
| SN | Операція | опис |
|---|---|---|
| 1 | Вставка | Вставка в дерево AVL виконується так само, як і в бінарному дереві пошуку. Однак це може призвести до порушення властивості дерева AVL, і тому дерево може потребувати збалансування. Дерево можна збалансувати, застосувавши обертання. |
| 2 | Видалення | Видалення також можна виконати так само, як це виконується в бінарному дереві пошуку. Видалення також може порушити баланс дерева, тому для відновлення балансу дерева використовуються різні типи обертань. |
Чому AVL Tree?
Дерево AVL контролює висоту бінарного дерева пошуку, не допускаючи його перекосу. Час, витрачений на всі операції в бінарному дереві пошуку висотою h, дорівнює O(h) . Однак його можна поширити на O(n) якщо BST стає перекошеним (тобто найгірший випадок). Обмежуючи цю висоту до log n, дерево AVL накладає верхню межу на кожну операцію O(log n) де n – кількість вузлів.
Обертання AVL
Ми виконуємо обертання в дереві AVL лише у випадку, якщо коефіцієнт балансу відрізняється від -1, 0 і 1 . В основному є чотири типи обертання, які є такими:
- Обертання L L: вставлений вузол знаходиться в лівому піддереві лівого піддерева A
- R R обертання: вставлений вузол знаходиться в правому піддереві правого піддерева A
- Обертання L R: вставлений вузол знаходиться в правому піддереві лівого піддерева A
- R L обертання: вставлений вузол знаходиться в лівому піддереві правого піддерева A
Де вузол A – це вузол, коефіцієнт балансу якого відрізняється від -1, 0, 1.
Перші два обертання LL і RR є одинарними обертаннями, а наступні два обертання LR і RL є подвійними обертаннями. Щоб дерево було незбалансованим, мінімальна висота повинна бути не менше 2. Розберемо кожне обертання
1. Обертання RR
Коли BST стає незбалансованим через те, що вузол вставляється в праве піддерево правого піддерева A, тоді ми виконуємо обертання RR, обертання RR – це обертання проти годинникової стрілки, яке застосовується до краю під вузлом, що має коефіцієнт балансу -2
У наведеному вище прикладі вузол A має коефіцієнт балансу -2, оскільки вузол C вставлено в праве піддерево правого піддерева A. Виконуємо поворот RR на ребрі під А.
2. Л. Л. Ротація
Коли BST стає незбалансованим через те, що вузол вставляється в ліве піддерево лівого піддерева C, тоді ми виконуємо обертання LL, обертання LL є обертанням за годинниковою стрілкою, яке застосовується до краю під вузлом, що має коефіцієнт балансу 2.
У наведеному вище прикладі вузол C має коефіцієнт балансу 2, оскільки вузол A вставлено в ліве піддерево лівого піддерева C. Виконуємо поворот LL на ребрі під А.
3. Обертання LR
Подвійне обертання трохи складніше, ніж одиночне обертання, про що вже пояснювалося вище. Обертання LR = обертання RR + обертання LL, тобто спочатку обертання RR виконується на піддереві, а потім обертання LL виконується на повному дереві, під повним деревом ми маємо на увазі перший вузол із шляху вставленого вузла, коефіцієнт балансу якого відрізняється від -1 , 0 або 1.
Давайте дуже чітко зрозуміємо кожен крок:
| Держава | Дія |
|---|---|
 | Вузол B було вставлено в праве піддерево A, ліве піддерево C, через що C став незбалансованим вузлом із коефіцієнтом балансу 2. Цей випадок є обертанням L R, де: Вставлений вузол знаходиться в правому піддереві лівого піддерева C |
 | Оскільки обертання LR = обертання RR + LL, отже, спочатку виконується RR (проти годинникової стрілки) на піддереві з коренем A. Виконуючи обертання RR, вузол А , став лівим піддеревом Б . |
 | Після виконання обертання RR вузол C все ще незбалансований, тобто має коефіцієнт балансу 2, оскільки вставлений вузол A знаходиться зліва зліва від C |
 | Тепер виконуємо LL обертання за годинниковою стрілкою на повному дереві, тобто на вузлі C. node C тепер став правим піддеревом вузла B, A є лівим піддеревом B |
 | Коефіцієнт балансу кожного вузла тепер дорівнює -1, 0 або 1, тобто BST тепер збалансований. |
4. РЛ Обертання
Як уже обговорювалося, подвійне обертання трохи складніше, ніж одинарне обертання, про що вже пояснювалося вище. Обертання R L = обертання LL + обертання RR, тобто спочатку обертання LL виконується на піддереві, а потім обертання RR виконується на повному дереві, під повним деревом ми маємо на увазі перший вузол із шляху вставленого вузла, коефіцієнт балансу якого відрізняється від -1 , 0 або 1.
| Держава | Дія |
|---|---|
 | Вузол Б було вставлено в ліве піддерево C праве піддерево А , через що A став незбалансованим вузлом із коефіцієнтом балансу - 2. Цей випадок є поворотом RL, де: Вставлений вузол знаходиться в лівому піддереві правого піддерева A |
 | Оскільки обертання RL = обертання LL + обертання RR, отже, LL (за годинниковою стрілкою) на піддереві з коренем у C виконується першим. Виконуючи обертання RR, вузол C стало правим піддеревом Б . |
 | Після виконання повороту LL вузл А все ще незбалансований, тобто має коефіцієнт балансу -2, що пов’язано з правим піддеревом вузла A правого піддерева. |
 | Тепер виконуємо обертання RR (обертання проти годинникової стрілки) на повному дереві, тобто на вузлі A. node C тепер став правим піддеревом вузла B, а вузол A став лівим піддеревом B. |
 | Коефіцієнт балансу кожного вузла тепер дорівнює -1, 0 або 1, тобто BST тепер збалансований. |
Q: Побудуйте дерево AVL, що має такі елементи
H, I, J, B, A, E, C, F, D, G, K, L
1. Вставте H, I, J
При вставці вищезгаданих елементів, особливо у випадку H, BST стає незбалансованим, оскільки коефіцієнт балансу H становить -2. Оскільки BST зміщений вправо, ми виконаємо обертання RR на вузлі H.
Результуюче дерево балансу:
2. Вставте B, A
При вставці вищезазначених елементів, особливо у випадку A, BST стає незбалансованим, оскільки коефіцієнт балансу H і I дорівнює 2, ми розглядаємо перший вузол з останнього вставленого вузла, тобто H. Оскільки BST з H зміщений вліво, ми виконаємо LL Rotation на вузлі H.
Результуюче дерево балансу:
3. Вставте E
Після вставки E BST стає незбалансованим, оскільки коефіцієнт балансу I дорівнює 2, оскільки, якщо ми подорожуємо від E до I, ми виявляємо, що він вставлений у ліве піддерево правого піддерева I, ми виконаємо обертання LR на вузлі I. LR = RR + LL обертання
3 a) Спочатку ми виконуємо RR обертання на вузлі B
Результуюче дерево після обертання RR:
екта капур актор
3b) Спочатку виконуємо LL обертання на вузлі I
Результуюче збалансоване дерево після обертання LL:
4. Вставте C, F, D
Після вставки C, F, D BST стає незбалансованим, оскільки коефіцієнт балансу B і H дорівнює -2, оскільки, якщо ми подорожуємо від D до B, ми виявимо, що він вставлений у праве піддерево лівого піддерева B, ми виконаємо Обертання RL на вузлі I. Обертання RL = LL + RR.
4a) Спочатку виконуємо LL обертання на вузлі E
Результуюче дерево після обертання LL є:
4b) Потім ми виконуємо обертання RR на вузлі B
Результатом збалансованого дерева після обертання RR є:
5. Вставте Г
Після вставки G BST стає незбалансованим, оскільки коефіцієнт балансу H дорівнює 2, оскільки, якщо ми подорожуємо від G до H, ми виявимо, що він вставлений у ліве піддерево правого піддерева H, ми виконаємо обертання LR на вузлі I. LR = RR + LL обертання.
5 a) Спочатку ми виконуємо обертання RR на вузлі C
Результуюче дерево після обертання RR:
5 b) Потім ми виконуємо LL обертання на вузлі H
Результуюче збалансоване дерево після обертання LL:
6. Вставте К
aes проти des
Після введення K BST стає незбалансованим, оскільки коефіцієнт балансу I становить -2. Оскільки BST зміщений вправо від I до K, отже, ми будемо виконувати обертання RR на вузлі I.
Результатом збалансованого дерева після обертання RR є:
7. Вставте L
Після вставки L-дерево залишається збалансованим, оскільки коефіцієнт балансу кожного вузла тепер дорівнює -1, 0, +1. Отже, дерево є збалансованим деревом AVL
