Дерева AVL: Балансовий коефіцієнт, який ніколи не досягає ±2

Дерево бінарного пошуку з обітми

Звичайне дерево бінарного пошуку забезпечує O(log n) швидкість пошуку лише за умови, що воно залишається приблизно збалансованим; якщо вставляти ключі в відсортованому порядку в незабалансоване дерево бінарного пошуку, воно деградує до зв’язного списку, з O(n) швидкістю пошуку. Дерево AVL, назване на честь його розробників Георгія Адлесона-Вільського та Євгенія Ландіса (1962 рік), було першою структурою даних, яка гарантує висоту O(log n) незалежно від порядку прибуття ключів, шляхом забезпечення простої інваріантності після кожного вставлення та видалення: для кожного вузла різниця висот його лівого та правого піддерев не може перевищувати 1.

Балансуючий фактор

Кожен вузол відстежує (або обчислює) балансуючий фактор: різницю між висотою правої піддерева та висотою лівого піддерева. Легальне дерево AVL має балансуючий фактор -1, 0 або +1. При вставці або видаленні ключа балансуючий фактор кожного предка на шляху до кореня може змінитися на одиницю; якщо балансуючий фактор будь-якого з цих передків досягне -2 або +2, дерево більше не є легальним деревом AVL у цій точці і потребує негайної перевірки та виправлення через обертання перед поверненням від операції.

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

Існує рівно чотири форми дисбалансу, і кожна з них має фіксоване механічне виправлення. Дисбаланс «ліво-ліво» (вставлений у ліву піддерево лівого дитини) виправляється одним праворуч обертанням; дисбаланс «право-право» – одним ліворуч обертанням. Змішані випадки – «ліво-право» (вставлений у правий піддеревo лівої дитини) та «право-ліво» – потребують двох обертань послідовно, спочатку вирівнюючи внутрішній зигзаг у нахил в одну сторону, а потім застосовуючи відповідне однобічне обертання:

// однобічне праворуч обертання, яке виправляє дисбаланс «ліво-ліво» у вузлі z, дитина y = z.left rotateRight(z): y = z.left z.left = y.right y.right = z оновіть висоти z, потім y повернути y // y є новим коренем піддерева // «ліво-право» випадок: два обертання fixLeftRight(z): z.left = rotateLeft(z.left) // спочатку вирівнюємо зигзаг повернути rotateRight(z) // потім застосовуємо відповідне однобічне обертання Обертання – це невелике, постійно час перерозподіл покажчиків — воно ніколи не торкається більше, ніж кількох десятків вузлів — і після вставки потрібно максимум одне обертання (однобічне або подвійне), щоб відновити баланс усього дерева, оскільки виправлення найнижчого несбалансованого предка також відновлює висоту, яку очікував власний батько цього предка. Видалення менш просте: воно може потребувати обертань на кожному рівні шляху назад до кореня, до O(log n) обертів у найгіршому випадку, оскільки видалення вузла може зменшити висоту піддерева таким чином, що дисбаланс посилюється вгору.

// single right rotation, fixing a left-left imbalance at node z, child y = z.left
rotateRight(z):
  y = z.left
  z.left = y.right
  y.right = z
  update heights of z, then y
  return y                      // y is the new subtree root

// left-right case: two rotations
fixLeftRight(z):
  z.left = rotateLeft(z.left)   // straighten the zigzag first
  return rotateRight(z)          // then apply the matching single rotation

Чому варто, коли червоно-чорні дерева також гарантують O(log n)?

AVL-дерева підтримують більш жорстку інваріантну балансу – висота AVL-дерева ніколи не перевищує приблизно 1,44 * log2(n), що значно ближче до теоретичного мінімуму log2(n), ніж розріджене обмеження червоно-чорних дерев близько 2 * log2(n) – що робить пошуки в AVL-деревах швидшими на практиці для завдань з великою кількістю пошуків. Компроміс полягає в тому, що AVL-дерева перебалансуються більш агресивно і, отже, виконують більше поворотів в середньому під час вставки або видалення, що пояснює, чому червоно-чорні дерева є більш поширеним за замовчуванням у реалізаціях загального призначення (багато стандартних бібліотечних відсортованих карт і множини використовують їх), тоді як AVL-дерева використовуються частіше в структурах з домінуючим читанням, таких як індекси баз даних та файлових систем, де додаткова дисципліна балансування виправдовується кожного разу, коли дерево переглядається.

Frequently asked questions

Спробуйте наживо

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