Ответ
AVL-дерево — это самобалансирующееся бинарное дерево поиска, где для каждой вершины высота её левого и правого поддеревьев отличается не более чем на 1. Это гарантирует, что операции поиска, вставки и удаления выполняются за O(log n) в худшем случае.
Основные свойства:
- Для каждой вершины:
|height(left) - height(right)| ≤ 1. - После вставки/удаления выполняется балансировка с помощью поворотов (левый, правый, лево-правый, право-левый).
Пример балансировки (правый поворот):
def right_rotate(y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
# Обновление высот
y.height = max(height(y.left), height(y.right)) + 1
x.height = max(height(x.left), height(x.right)) + 1
return x