AVL-дерево

AVL-дерево — это самобалансирующееся бинарное дерево поиска, в котором разница высот между левым и правым поддеревьями любого узла (коэффициент баланса) не превышает 1.

Названо в честь своих создателей — Адельсона-Вельского и Ландиса (1962) — первое изобретённое самобалансирующееся BST.

Основная концепция: коэффициент баланса

Коэффициент баланса (BF) = Высота(Левого Поддерева) - Высота(Правого Поддерева)
Значение BF Значение
-1, 0, +1 ✅ Сбалансировано — корректный узел AVL
≤ -2 ❌ Перекос вправо — требуется вращение
≥ +2 ❌ Перекос влево — требуется вращение

Структура

graph TD A["30 (BF=0)"] B["20 (BF=0)"] C["40 (BF=0)"] D["10 (BF=0)"] E["25 (BF=0)"] A --> B A --> C B --> D B --> E

4 случая вращений

Когда узел становится несбалансированным после вставки или удаления, одно из четырёх вращений восстанавливает баланс:

1. Left-Left (LL) → Правое вращение

Дисбаланс возникает в левом поддереве левого ребёнка.

    z                y
   / \             /   \
  y   T4   →     x     z
 / \            / \   / \
x   T3         T1 T2 T3 T4

2. Right-Right (RR) → Левое вращение

Дисбаланс возникает в правом поддереве правого ребёнка.

  z                  y
 / \               /   \
T1   y    →       z     x
    / \          / \   / \
   T2   x       T1 T2 T3 T4
       / \
      T3  T4

3. Left-Right (LR) → Сначала левое, затем правое вращение

Дисбаланс возникает в правом поддереве левого ребёнка.

  z          z          x
 / \        / \        / \
y   T4 →  x   T4 →   y   z
 \        /          / \ / \
  x      y          T1 T2T3 T4

4. Right-Left (RL) → Сначала правое, затем левое вращение

Дисбаланс возникает в левом поддереве правого ребёнка.

  z            z              x
 / \          / \            / \
T1   y   →  T1   x    →    z   y
    /              \       /\ / \
   x                y    T1 T2T3 T4

Временная и пространственная сложность

Операция Средний случай Худший случай
Поиск O(log n) O(log n)
Вставка O(log n) O(log n)
Удаление O(log n) O(log n)
Память O(n) O(n)

Худший случай гарантированно O(log n) — в отличие от обычного BST, которое деградирует до O(n) при отсортированных входных данных.

Реализация на Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # Новый узел начинается с высоты 1


class AVLTree:

    # ── Вспомогательные методы ──────────────────────────

    def get_height(self, node):
        return node.height if node else 0

    def get_balance(self, node):
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def update_height(self, node):
        node.height = 1 + max(self.get_height(node.left),
                               self.get_height(node.right))

    # ── Вращения ────────────────────────────────────────

    def rotate_right(self, z):
        y = z.left
        T3 = y.right

        y.right = z          # выполняем вращение
        z.left = T3

        self.update_height(z)
        self.update_height(y)
        return y             # новый корень поддерева

    def rotate_left(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        self.update_height(z)
        self.update_height(y)
        return y

    # ── Вставка ─────────────────────────────────────────

    def insert(self, node, key):
        # 1. Обычная вставка BST
        if not node:
            return Node(key)
        if key < node.key:
            node.left = self.insert(node.left, key)
        elif key > node.key:
            node.right = self.insert(node.right, key)
        else:
            return node  # дубликаты запрещены

        # 2. Обновляем высоту
        self.update_height(node)

        # 3. Получаем коэффициент баланса и балансируем дерево
        balance = self.get_balance(node)

        # LL
        if balance > 1 and key < node.left.key:
            return self.rotate_right(node)

        # RR
        if balance < -1 and key > node.right.key:
            return self.rotate_left(node)

        # LR
        if balance > 1 and key > node.left.key:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)

        # RL
        if balance < -1 and key < node.right.key:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)

        return node

    # ── Поиск ───────────────────────────────────────────

    def search(self, node, key):
        if not node or node.key == key:
            return node
        if key < node.key:
            return self.search(node.left, key)
        return self.search(node.right, key)

    # ── Симметричный обход (In-order Traversal) ─────────

    def inorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder(node.left, result)
            result.append(node.key)
            self.inorder(node.right, result)
        return result


# ── Использование ───────────────────────────────────────
tree = AVLTree()
root = None

for key in [30, 20, 10, 25, 40]:
    root = tree.insert(root, key)

print(tree.inorder(root))     # [10, 20, 25, 30, 40]
print(tree.search(root, 25))  # <Node object>

AVL против других сбалансированных деревьев

Характеристика AVL-дерево Красно-чёрное дерево B-дерево
Гарантия баланса Строгая (BF ≤ 1) Ослабленная Ослабленная
Скорость поиска ✅ Быстрее Немного медленнее Хорошо для диска
Скорость вставки/удаления Немного медленнее ✅ Быстрее Хорошо для диска
Вращений на вставку ≤ 2 ≤ 2 —
Лучше подходит для Нагрузок с частым чтением Нагрузок с частой записью Базы данных / файловые системы

Ключевые выводы