АВЛ-дерево: как работает балансировка и зачем она нужна

Коротко

АВЛ-дерево — двоичное дерево поиска, которое само себя балансирует после каждой вставки и удаления.

Проблема обычного дерева поиска

Двоичное дерево поиска обещает O(log n). Но обещание держится только пока дерево сбалансировано.

Вставим числа по возрастанию: 1, 2, 3, 4, 5.

1
 \
  2
   \
    3
     \
      4
       \
        5

Получился связный список. Поиск деградировал до O(n), и все преимущества дерева исчезли. А отсортированные данные на входе — не редкость, а типичный случай.

АВЛ-дерево (Адельсон-Вельский и Ландис, 1962) решает это: после каждой операции оно проверяет баланс и восстанавливает его поворотами.

Условие баланса

Для каждого узла вводится баланс-фактор — разница высот левого и правого поддеревьев:

balance = высота(левое) − высота(правое)

Дерево считается АВЛ-сбалансированным, если у каждого узла баланс-фактор равен −1, 0 или 1.

      10  (balance = 0)
     /  \
    5    15
   / \
  3   7

У корня левое поддерево высотой 2, правое высотой 1, разница 1 — допустимо.

Это условие гарантирует, что высота дерева не превысит примерно 1.44·log₂n. То есть дерево может быть чуть выше идеального, но не больше чем в полтора раза.

Повороты: как чинится баланс

Когда после вставки баланс нарушился (стал ±2), дерево перестраивается поворотом. Есть четыре случая, но по сути два — остальные симметричны.

Левый-левый: правый поворот

Перевес влево, и вставка была в левое поддерево левого ребёнка.

      z                              y
     / \                           /   \
    y   T4    правый поворот      x     z
   / \        ───────────────►   / \   / \
  x   T3                        T1 T2 T3 T4
 / \
T1  T2

Узел y поднимается на место z, а z становится его правым ребёнком. Поддерево T3 меняет владельца — переходит от y к z.

Левый-правый: двойной поворот

Перевес влево, но вставка была в правое поддерево левого ребёнка. Один поворот здесь не поможет — сначала нужно свести ситуацию к предыдущему случаю.

    z              z                x
   / \            / \             /   \
  y   T4         x   T4          y     z
 / \      ──►   / \       ──►   / \   / \
T1  x          y   T3          T1 T2 T3 T4
   / \        / \
  T2 T3      T1 T2

  левый поворот      правый поворот
  вокруг y           вокруг z

Правый-правый и правый-левый — зеркальные отражения этих двух.

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

class Node:
    __slots__ = ('key', 'left', 'right', 'height')

    def __init__(self, key) -> None:
        self.key = key
        self.left: 'Node | None' = None
        self.right: 'Node | None' = None
        self.height = 1        # высота листа равна 1


def height(node: 'Node | None') -> int:
    return node.height if node else 0


def balance_factor(node: Node) -> int:
    return height(node.left) - height(node.right)


def update_height(node: Node) -> None:
    node.height = 1 + max(height(node.left), height(node.right))


def rotate_right(z: Node) -> Node:
    y = z.left
    z.left = y.right       # T3 переходит к z
    y.right = z

    update_height(z)       # сначала нижний узел
    update_height(y)
    return y               # новый корень поддерева


def rotate_left(z: Node) -> Node:
    y = z.right
    z.right = y.left
    y.left = z

    update_height(z)
    update_height(y)
    return y


def insert(node: 'Node | None', key) -> Node:
    # 1. обычная вставка в дерево поиска
    if node is None:
        return Node(key)

    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node        # дубликаты не храним

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

    # 3. проверяем баланс и чиним
    balance = balance_factor(node)

    if balance > 1:                       # перевес влево
        if key > node.left.key:           # левый-правый
            node.left = rotate_left(node.left)
        return rotate_right(node)         # левый-левый

    if balance < -1:                      # перевес вправо
        if key < node.right.key:          # правый-левый
            node.right = rotate_right(node.right)
        return rotate_left(node)          # правый-правый

    return node


def inorder(node: 'Node | None') -> list:
    if node is None:
        return []
    return inorder(node.left) + [node.key] + inorder(node.right)


root = None
for key in [1, 2, 3, 4, 5]:
    root = insert(root, key)

print(inorder(root))      # [1, 2, 3, 4, 5]
print(root.key)           # 2 — дерево сбалансировалось, а не выродилось
print(height(root))       # 3 вместо 5

Проверьте последнюю строку: те же пять чисел по возрастанию дали высоту 3 вместо 5. Дерево не выродилось.

Порядок обновления высот в поворотах критичен. Сначала z (он ушёл вниз), потом y — иначе высота y посчитается по устаревшим данным.

АВЛ против красно-чёрного дерева

Оба дерева самобалансирующиеся, но с разными приоритетами.

Практическое правило: читаете чаще, чем пишете — АВЛ; пишете часто — красно-чёрное.

Именно поэтому красно-чёрные деревья стоят в стандартных библиотеках (std::map в C++, TreeMap в Java, внутренности HashMap при коллизиях), а АВЛ применяют в базах данных и индексах, где чтение доминирует.

Стоит ли писать его руками

В прикладном коде — почти никогда. В Python есть словари и sortedcontainers, в других языках — готовые сбалансированные деревья.

Но понимать устройство полезно по двум причинам. Во-первых, это стандартный вопрос на собеседовании: «что будет, если вставлять в дерево поиска отсортированные данные». Во-вторых, поворот — это базовая операция над деревьями, которая встречается в декартовых деревьях, splay-деревьях и B-деревьях.

Частые ошибки

Высота листа равна 0. Тогда height(None) придётся считать как −1, и легко запутаться. Проще считать высоту листа единицей, а None — нулём.

Обновление высоты после проверки баланса. Порядок обязателен: сначала высота, потом баланс. Иначе баланс считается по старым данным.

Определение типа поворота по баланс-фактору ребёнка вместо ключа. Оба способа работают, но смешивать их нельзя — получится неверный выбор поворота в граничных случаях.

Забытый возврат нового корня. Функции поворота возвращают новый корень поддерева, и результат обязательно нужно присвоить: node.left = rotate_left(node.left).

Что запомнить

• Обычное дерево поиска вырождается в список на отсортированных данных.
• АВЛ поддерживает разницу высот поддеревьев не больше единицы у каждого узла.
• Баланс восстанавливается четырьмя видами поворотов, два из которых зеркальны.
• Гарантия O(log n) на поиск, вставку и удаление.
• Строже красно-чёрного дерева: быстрее читает, медленнее пишет.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→