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

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

Зачем это нужно? Обычное БДН может стать несбалансированным (например, при вставке отсортированных данных), что приведёт к деградации операций до O(n). Балансировка предотвращает это.

Основные типы сбалансированных деревьев:

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

Упрощённая структура узла AVL-дерева на C#:

public class AvlNode<T> where T : IComparable<T>
{
    public T Key;
    public AvlNode<T> Left;
    public AvlNode<T> Right;
    public int Height; // Высота поддерева с корнем в этом узле

    public AvlNode(T key)
    {
        Key = key;
        Height = 1; // Новый узел — лист, высота = 1
    }
}

// Вспомогательный метод для получения высоты (обрабатывает null)
public static int GetHeight(AvlNode<T> node) => node?.Height ?? 0;

// Метод для пересчёта высоты узла после изменений
public static void UpdateHeight(AvlNode<T> node)
{
    if (node == null) return;
    node.Height = 1 + Math.Max(GetHeight(node.Left), GetHeight(node.Right));
}

// Коэффициент балансировки (balance factor)
public static int GetBalanceFactor(AvlNode<T> node)
{
    if (node == null) return 0;
    return GetHeight(node.Left) - GetHeight(node.Right);
}

Балансировка достигается с помощью поворотов (малого левого/правого, большого левого/правого), которые выполняются при нарушении условия сбалансированности (|balanceFactor| > 1).