Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке AVL-дерево і що робить його збалансованим?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**AVL-дерево** - це самобалансуюче бінарне дерево пошуку (BST), у якому для кожного вузла контролюється баланс висот піддерев. **Ключове:** це гарантує, що пошук, вставка та видалення виконуються за O(log n), а структура дерева залишається "щільною".Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення**AVL-дерево** - це **самобалансуюче бінарне дерево пошуку (BST)**, у якому для кожного вузла контролюється **баланс висот піддерев**. Воно назване на честь винахідників - **Адельсона-Вельського і Ландіса (AVL)**. --- ## Головна властивість балансування Для **кожного вузла** різниця висот його лівого та правого піддерева не більша за **1**: [ |height(left) - height(right)| \leq 1 ] Якщо після вставки або видалення цей баланс порушується, дерево автоматично **виконує поворот (rotation)**, щоб відновити рівновагу. --- ## Чому це важливо Завдяки цій умові висота AVL-дерева завжди залишається приблизно **O(log n)**, тому всі операції: пошук, вставка, видалення, працюють швидко. --- ## Приклад ```javascript До вставки: 30 / 20 / 10 Після балансування: 20 / \ 10 30 ``` Дерево виконує **правий поворот**, щоб відновити баланс. --- ## Основні типи поворотів 1. **Правий (Right Rotation)** - якщо дисбаланс у лівому піддереві. 2. **Лівий (Left Rotation)** - якщо дисбаланс у правому піддереві. 3. **Ліво-правий** і **право-лівий** - для складних випадків. --- ## Підсумок **AVL-дерево** - це бінарне дерево пошуку, у якому після кожної операції підтримується майже ідеальний баланс висоти. Це гарантує, що **пошук, вставка та видалення виконуються за O(log n)**, а структура дерева залишається "щільною" і ефективною.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.