🌴 AVL-дерево
Самобалансувальні повороти
Налаштування
Статистика
Кількість вузлів
0
Висота дерева
0
Останній поворот
—
Кількість поворотів
0
Довідка та теорія

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

Фактор балансу

Кожен вузол зберігає фактор балансу: висота(лівого) − висота(правого). Інваріант AVL вимагає, щоб це значення завжди залишалося в межах {−1, 0, 1} для кожного вузла. Після зміни висоти перераховуються знизу вгору, від зміненого вузла до кореня.

Виявлення дисбалансу

Рухаючись вгору, перший предок, чий фактор балансу виходить за межі {−1,0,1}, стає точкою повороту.

Чотири випадки повороту

  • LL: перевантажене ліве піддерево, лівий нащадок теж лівий — одинарний правий поворот.
  • RR: перевантажене праве піддерево, правий нащадок теж правий — одинарний лівий поворот.
  • LR: перевантажене ліве піддерево, лівий нащадок правий — спочатку поворот лівого нащадка ліворуч, потім вузла праворуч.
  • RL: перевантажене праве піддерево, правий нащадок лівий — спочатку поворот правого нащадка праворуч, потім вузла ліворуч.

Кожен поворот — це перезапис покажчиків за O(1); після вставки потрібен щонайбільше один (одинарний чи подвійний) поворот, тоді як видалення може вимагати поворотів на кожному рівні аж до кореня.

Чому це важливо

Незбалансоване звичайне ДДП вироджується до O(n) на відсортованих вхідних даних (стає зв'язаним списком). Суворий баланс AVL утримує висоту на рівні O(log n) ≈ 1.44·log₂(n+2), тож пошук залишається швидким незалежно від порядку вставки.

Про AVL-дерево — самобалансувальні повороти

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Оновлено: 11 липня 2026 р.

AVL-дерево, назване на честь Георгія Адельсона-Вельського та Євгена Ландіса, які опублікували його в 1962 році, є найранішим самобалансувальним двійковим деревом пошуку. Кожен вузол зберігає фактор балансу, що дорівнює висоті лівого піддерева мінус висота правого, і дерево підтримує інваріант: це значення завжди залишається в межах {−1, 0, 1}. Після вставки чи видалення висоти перераховуються вздовж шляху назад до кореня, а перший знайдений незбалансований предок виправляється одинарним поворотом (при перекосі LL або RR) чи подвійним поворотом (при перекосі LR або RL) — кожен є перезаписом покажчиків за O(1). Ця сувора дисципліна утримує висоту дерева на рівні O(log n) у найгіршому випадку, на відміну від наївного ДДП, яке може вирודитись до зв'язаного списку на відсортованих даних. Порівняно з червоно-чорними деревами, AVL-дерева балансуються суворіше, що дає швидший пошук ціною частіших поворотів при вставці й видаленні — тому AVL-дерева вигідні, коли читання значно переважає над записом.

Часті запитання

Чому фактор балансу має залишатися в межах {−1, 0, 1}?

Цей діапазон — точний поріг, що гарантує висоту дерева O(log n). Адельсон-Вельський і Ландіс довели: дерево, що дотримується цього інваріанта, має висоту не більше приблизно 1.44·log₂(n+2), тож допустимі фактори балансу ±1 дають достатню гнучкість для ефективної вставки, водночас гарантуючи логарифмічну висоту.

У чому різниця між одинарним і подвійним поворотом?

Одинарний поворот (випадок LL або RR) виправляє дисбаланс, коли перевантажене піддерево має нащадка, перевантаженого в той самий бік — достатньо одного перезапису покажчиків. Подвійний поворот (випадок LR або RL) обробляє «зигзагоподібний» дисбаланс, коли перевантажений нащадок нахилений у протилежний бік: спочатку повертається нащадок, щоб звести ситуацію до одинарного випадку, потім — сам вузол.

Як AVL-дерево порівнюється з червоно-чорним деревом?

Обидва гарантують висоту O(log n), але AVL-дерева застосовують суворіший інваріант балансу, що дає коротші дерева й швидший пошук. Червоно-чорні дерева послаблюють обмеження балансу (найдовший шлях від кореня до листка може бути вдвічі довшим за найкоротший), тому потребують менше поворотів при вставці й видаленні. Це робить AVL-дерева вигіднішими для навантажень з переважанням читання, а червоно-чорні — для навантажень з переважанням запису.

Чому видалення може вимагати поворотів на кожному рівні аж до кореня, на відміну від вставки?

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