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