Что такое самобалансирующееся дерево?

Самобалансирующееся дерево — это расширение концепции двоичного дерева поиска (BST), которое добавляет правила и алгоритмы для автоматического поддержания сбалансированности. Балансировка означает, что разница высот левого и правого поддеревьев для любого узла не превышает определённого предела (обычно 1 или 2). Это предотвращает вырождение дерева в линейный список, что может произойти при последовательной вставке отсортированных данных в обычное BST.

Зачем нужна балансировка?

Основная цель — гарантировать производительность. В сбалансированном дереве высота пропорциональна логарифму числа узлов (O(log n)). Поиск, вставка и удаление в таком дереве выполняются за логарифмическое время даже в худшем случае. В несбалансированном дереве эти операции могут деградировать до O(n), что неприемлемо для больших объёмов данных.

Как работает балансировка?

Балансировка достигается с помощью операций поворота узлов после вставки или удаления. Повороты бывают левые и правые, они локально перестраивают поддерево, уменьшая разницу высот. Дерево отслеживает "фактор баланса" для каждого узла (разница высот поддеревьев). Если после операции фактор выходит за допустимые пределы, запускается серия поворотов для восстановления баланса.

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

• AVL-дерево: строго сбалансировано (разница высот ≤ 1). Обеспечивает самый быстрый поиск, но требует частых поворотов при вставке/удалении.
• Красно-чёрное дерево: менее строгие правила (допускает разницу высот до 2 раз). Требует меньше перестроений при модификациях, поэтому часто используется в стандартных библиотеках (например, std::map в C++, TreeMap в Java).
• B-деревья: используются для хранения данных на диске (например, в файловых системах и базах данных), балансируются по количеству ключей в узле.

Пример кода: поворот в AVL-дереве

class AVLNode {
    int key, height;
    AVLNode left, right;
    AVLNode(int key) { this.key = key; height = 1; }
}

// Правый поворот для узла y
AVLNode rightRotate(AVLNode y) {
    AVLNode x = y.left;
    AVLNode T2 = x.right;
    // Выполняем поворот
    x.right = y;
    y.left = T2;
    // Обновляем высоты
    y.height = Math.max(height(y.left), height(y.right)) + 1;
    x.height = Math.max(height(x.left), height(x.right)) + 1;
    return x; // Новый корень поддерева
}

// Аналогично реализуется левый поворот.
// После вставки ключа вычисляется фактор баланса и,
// если нужно, применяются повороты.

Самобалансирующиеся деревья применяются везде, где нужны эффективные операции поиска и динамическое множество с упорядоченными ключами: базы данных (индексы), файловые системы, кэши, планировщики задач, реализации Set и Map в стандартных библиотеках языков.

Вывод: Самобалансирующиеся деревья стоит применять, когда требуется гарантированно быстрый поиск, вставка и удаление в упорядоченном наборе данных, особенно если данные динамически изменяются, и важна стабильная производительность в худшем случае.