Балансировка деревьев

Балансировка дерева (tree balancing) — поддержание высоты двоичного дерева поиска близкой к log n, чтобы операции поиска, вставки и удаления гарантированно выполнялись за O(log n).

Зачем нужно

Несбалансированное BST вырождается в связный список при последовательной вставке упорядоченных данных, и высота становится O(n). Сбалансированные деревья гарантируют O(log n) для всех операций вне зависимости от порядка вставки. Это критично для баз данных, файловых систем и любых структур, требующих быстрого поиска.

Где используется

  • СУБД: B-деревья и B+-деревья в индексах (PostgreSQL, MySQL)
  • Стандартные библиотеки: std::map/std::set в C++ (Red-Black Tree), TreeMap в Java
  • Операционные системы: управление памятью через красно-чёрные деревья (Linux CFS)
  • Файловые системы: NTFS, ext4 используют B-деревья

Основной контент

Почему деревья разбалансируются

Вставка [1, 2, 3, 4, 5] в обычное BST:

1
 \
  2
   \
    3       Высота = 5 = O(n) → поиск O(n)
     \
      4
       \
        5

Ротации — базовая операция балансировки

Правая ротация вокруг y:

    y                x
   / \              / \
  x   C    →      A   y
 / \                  / \
A   B                B   C

AVL-дерево

Баланс-фактор каждого узла: height(left) - height(right) ∈ {-1, 0, 1}.

function height(node) { return node ? node.height : 0; }

function rotateRight(y) {
  const x = y.left, T2 = x.right;
  x.right = y; y.left = T2;
  y.height = 1 + Math.max(height(y.left), height(y.right));
  x.height = 1 + Math.max(height(x.left), height(x.right));
  return x;
}

function rotateLeft(x) {
  const y = x.right, T2 = y.left;
  y.left = x; x.right = T2;
  x.height = 1 + Math.max(height(x.left), height(x.right));
  y.height = 1 + Math.max(height(y.left), height(y.right));
  return y;
}

function getBalance(node) {
  return node ? height(node.left) - height(node.right) : 0;
}

Типы дисбаланса и их исправление

Случай Условие Исправление
Left-Left balance > 1, новый узел слева-слева Правая ротация
Left-Right balance > 1, новый узел слева-справа Лев. + Прав. ротация
Right-Right balance < -1, справа-справа Левая ротация
Right-Left balance < -1, справа-слева Прав. + Лев. ротация

Красно-чёрное дерево vs AVL

Критерий AVL Red-Black
Строгость Строже Менее строго
Поиск Быстрее Немного медленнее
Вставка/удаление Больше ротаций Меньше ротаций
Применение Read-heavy Write-heavy

Красно-чёрное дерево используется в std::map (C++), TreeMap (Java), Linux kernel scheduler.

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

  • Забывать обновлять высоту узла после ротации — баланс-фактор будет вычислен неверно.
  • Путать четыре случая дисбаланса: Left-Right и Right-Left требуют двойной ротации.
  • Не обрабатывать удаление: при удалении узла также требуется проверка и ребалансировка.
  • Выбирать AVL там, где преобладают вставки — Red-Black даст лучшую производительность.

Связанные темы

Ресурсы