Пояснення фактору вставки, обертання та балансу дерева AVL

Що таке дерево AVL?

Дерево AVL - це підтип двійкового дерева пошуку. Дерева AVL, названі на честь винахідників Адельсона, Вельського та Ландіса, мають властивість динамічного самобалансування на додаток до всіх властивостей, виявлених бінарними деревами пошуку.

BST - це структура даних, що складається з вузлів. Він має такі гарантії:

  1. Кожне дерево має кореневий вузол (вгорі).
  2. Кореневий вузол має нуль, один або два дочірніх вузли.
  3. Кожен дочірній вузол має нуль, один або два дочірніх вузли тощо.
  4. Кожен вузол має до двох дітей.
  5. Для кожного вузла його ліві нащадки менше, ніж поточний вузол, що менше, ніж праві нащадки.

Дерева AVL мають додаткову гарантію:

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

Дерева AVL мають найгірший варіант пошуку, вставки та видалення часу O (журнал n).

Правильне обертання

Дерево AVL обертання вправо

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

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

Процес вставки AVL

Ви зробите вставку, подібну до звичайної вставки бінарного дерева пошуку. Після вставки ви виправляєте властивість AVL, використовуючи обертання ліворуч або праворуч.

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

Дерево AVL - це самозбалансоване бінарне дерево пошуку. Дерево AVL - це бінарне дерево пошуку, яке має такі властивості: -> Піддерева кожного вузла відрізняються за висотою щонайбільше на одне. -> Кожне піддерево - це дерево AVL.

Дерево AVL перевіряє висоту лівого та правого піддерев та запевняє, що різниця не перевищує 1. Ця різниця називається коефіцієнтом балансу. Висота дерева AVL завжди дорівнює O (Logn), де n - кількість вузлів у дереві.

Обертання дерев AVL

У дереві AVL після виконання кожної операції, як вставка та видалення, нам потрібно перевірити коефіцієнт балансу кожного вузла в дереві. Якщо кожен вузол задовольняє умові коефіцієнта балансу, тоді ми робимо висновок про операцію, інакше ми повинні зробити її збалансованою. Ми використовуємо операції обертання, щоб зробити дерево збалансованим, коли дерево стає незбалансованим внаслідок будь-якої операції.

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

Обертання вліво вліво (обертання LL)

При LL Rotation кожен вузол переміщується на одну позицію вліво від поточної позиції.

Одне обертання вправо (RR обертання)

У RR Rotation кожен вузол рухається на одну позицію вправо від поточної позиції.

Обертання вліво вправо (обертання LR)

Поворот LR - це поєднання одного повороту вліво з наступним поворотом вправо. У режимі LR Rotation спочатку кожен вузол переміщується на одну позицію вліво, а потім на одну позицію вправо від поточної позиції.

Обертання праворуч ліворуч (обертання RL)

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

Аналіз часу дерев AVL

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

Алгоритм Середній Найгірший випадок: Пробіл:, O(n)Час:O(n)

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

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