Что такое сбалансированное бинарное дерево поиска?

Сбалансированное бинарное дерево поиска (Balanced Binary Search Tree, BBST) — это бинарное дерево поиска, у которого высота поддеревьев любого узла отличается не более чем на заданную константу (часто 1). Это свойство гарантирует, что основные операции (поиск, вставка, удаление) выполняются за логарифмическое время O(log n) в худшем случае.

Проблема, которую решает балансировка: В несбалансированном БДП (например, при вставке элементов 1, 2, 3, 4, 5) дерево вырождается в линейный список, и операции выполняются за O(n).

Ключевые характеристики:

1. Свойство БДП: Для любого узла X все ключи в левом поддереве меньше ключа X, а в правом — больше.
2. Свойство баланса: Высота левого и правого поддеревьев для любого узла отличается незначительно (определяется конкретным алгоритмом балансировки).

Основные алгоритмы балансировки:

• Повороты (Rotations): Базовая операция для восстановления баланса без нарушения свойства БДП.
  • Левый поворот (Left Rotation)
  • Правый поворот (Right Rotation)

Пример псевдокода для правого поворота (как в AVL-дереве):

Node rightRotate(Node y) {
    Node x = y.left;
    Node T2 = x.right;

    // Выполняем поворот
    x.right = y;
    y.left = T2;

    // Обновляем высоты узлов (для AVL)
    y.updateHeight();
    x.updateHeight();

    // Новый корень поддерева
    return x;
}

Популярные реализации:

• AVL-деревья: Строгий баланс, быстрый поиск.
• Красно-чёрные деревья: Менее строгий баланс, эффективные вставка/удаление, используются в java.util.TreeMap.
• *B-деревья и их варианты (B+, B):** Используются для работы с диском (базы данных, файловые системы), имеют много потомков на узел.

Применение: Системы, где критически важна гарантированная логарифмическая производительность: индексы СУБД, реализация ассоциативных массивов, геометрические алгоритмы.