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

Идея проста. Представьте, что вы расставляете книги на полке по алфавиту — но не в ряд, а в дерево. Каждая новая книга сравнивается с текущей: если название «меньше» — идём налево, «больше» — направо. И так до тех пор, пока не найдём пустое место. Хотите найти книгу? Тот же процесс: сравниваем на каждом узле и идём в нужную сторону, отбрасывая половину оставшихся вариантов.

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

Проверьте: у корня 8 слева — 3 (меньше), справа — 12 (больше). У узла 3 слева — 1, справа — 6. Правило выполняется для каждого узла. Это и есть BST-инвариант. Начнём с поиска — он самый простой. Ищем число 6 в дереве выше. Стоим на 8. Шесть меньше восьми — идём налево. Стоим на 3. Шесть больше трёх — идём направо. Стоим на 6. Нашли! Три сравнения вместо обхода всех узлов.

static bool Search(TreeNode? node, int target)
{
    if (node == null) return false;       // Не нашли
    if (target == node.Val) return true;  // Нашли!
    if (target < node.Val)
        return Search(node.Left, target); // Ищем слева
    else
        return Search(node.Right, target); // Ищем справа
}

Отличие от поиска в обычном дереве: мы идём только в одну сторону — влево или вправо. Не нужно проверять оба поддерева. На каждом шаге отбрасываем половину. Сложность — O(h), где h — высота дерева.

Вставка работает по тому же принципу — ищем место, куда «упал бы» новый элемент:

static TreeNode Insert(TreeNode? node, int val)
{
    if (node == null) return new TreeNode(val);  // Нашли пустое место
    if (val < node.Val)
        node.Left = Insert(node.Left, val);      // Вставляем слева
    else if (val > node.Val)
        node.Right = Insert(node.Right, val);    // Вставляем справа
    // Если val == node.Val — дубликат, игнорируем
    return node;
}

// Пример использования
TreeNode? root = null;
root = Insert(root, 8);
root = Insert(root, 3);
root = Insert(root, 12);
root = Insert(root, 1);
root = Insert(root, 6);

Рекурсия спускается по дереву, пока не найдёт null — и ставит туда новый узел. Обратите внимание: результат присваивается в node.Left или node.Right — так новый узел привязывается к дереву. При вставке первого элемента root = null, функция вернёт новый узел, и мы получим корень. А вот удаление — самая хитрая операция. Тут три случая.

Случай 1: лист (нет потомков). Просто убираем — ничего не ломается.

Случай 2: один потомок. Заменяем удаляемый узел его единственным ребёнком. Как если бы в цепочке начальников убрали среднее звено — подчинённый переходит напрямую к вышестоящему.

Случай 3: два потомка. Самый интересный. Нужно найти замену, которая сохранит инвариант BST. Берём минимальный элемент из правого поддерева (in-order successor) — он больше всех в левом, но меньше всех остальных в правом. Идеальный кандидат на замену.

static TreeNode? Delete(TreeNode? node, int val)
{
    if (node == null) return null;

    if (val < node.Val)
        node.Left = Delete(node.Left, val);
    else if (val > node.Val)
        node.Right = Delete(node.Right, val);
    else
    {
        // Нашли узел для удаления
        if (node.Left == null) return node.Right;   // Случаи 1 и 2
        if (node.Right == null) return node.Left;   // Случай 2

        // Случай 3: два потомка
        var successor = FindMin(node.Right);         // Минимум в правом поддереве
        node.Val = successor.Val;                    // Копируем значение
        node.Right = Delete(node.Right, successor.Val); // Удаляем дубликат
    }
    return node;
}

static TreeNode FindMin(TreeNode node)
{
    while (node.Left != null) node = node.Left;
    return node;
}

Функция FindMin идёт влево до упора — самый левый узел в поддереве и есть минимум. Обратите внимание, как случаи 1 и 2 обрабатываются одной строкой: если Left == null, возвращаем Right (который может быть и null — это как раз случай листа).

Поговорим о сложности честно. В теории все операции BST — O(log n). Но это только когда дерево сбалансировано — примерно одинаковая глубина слева и справа. Что будет, если вставлять элементы по порядку: 1, 2, 3, 4, 5?

TreeNode? root = null;
root = Insert(root, 1);
root = Insert(root, 2);
root = Insert(root, 3);
root = Insert(root, 4);
root = Insert(root, 5);

// Получим цепочку вправо:
// 1
//  //   2
//    //     3
//      //       4
//        //         5

Каждый новый элемент больше предыдущего — значит всегда идёт вправо. Дерево превращается в цепочку, неотличимую от связного списка. Высота — n, все операции — O(n). BST деградировал.

Это не теоретическая проблема — это реальная ловушка. Если данные приходят отсортированными (а такое бывает часто: автоинкрементные id из базы, временные метки событий), обычный BST превращается в бесполезную палку. Search находит элемент перебором, Insert всегда идёт в одну сторону.

Сложность операций BST:

Покажем, как инвариант BST нарушается и почему это критично. Допустим, кто-то случайно вставил в дерево число не туда:

// Корректный BST: 8 -> 3 (левее) -> 12 (правее)
// Представьте, что мы нечаянно поставили 20 в ЛЕВОЕ поддерево 8
// Это нарушает инвариант: 20 > 8, но стоит слева

// Поиск числа 20 вернёт false, хотя 20 есть в дереве!
// Search пойдёт вправо от 8 (так как 20 > 8),
// а 20 стоит слева — мы его никогда не найдём

// Вывод: BST-инвариант — это ответственность программиста.
// Нарушь его один раз — поиск молча начнёт давать неверные ответы.

На практике это означает: если вы пишете BST вручную, вставляйте элементы только через метод Insert, который соблюдает инвариант. Никогда не модифицируйте node.Left и node.Right напрямую извне — это верный путь к поломке структуры данных.

Ещё одна полезная операция — нахождение минимума и максимума. В BST это тривиально: минимум — самый левый узел, максимум — самый правый.

static TreeNode FindMin(TreeNode node)
{
    while (node.Left != null) node = node.Left;
    return node;
}

static TreeNode FindMax(TreeNode node)
{
    while (node.Right != null) node = node.Right;
    return node;
}

Console.WriteLine(FindMin(root).Val);  // 1
Console.WriteLine(FindMax(root).Val);  // 15

Оба метода работают за O(h) — глубину дерева. В сбалансированном дереве это O(log n), в вырожденном — O(n). Именно эти операции используются внутри SortedSet<T>.Min и SortedSet<T>.Max в .NET. Подведём итог. BST — бинарное дерево с инвариантом: левое < узел < правое. Поиск, вставка и удаление — O(log n) в среднем. Удаление: лист — просто убрать, один потомок — заменить потомком, два потомка — заменить in-order successor (минимум правого поддерева). Главный подвох: при вставке отсортированных данных BST деградирует до O(n). Решение — самобалансирующиеся деревья (AVL, красно-чёрное), которые используются в стандартных коллекциях C#.

Бинарное дерево поиска (BST) — бинарное дерево, в котором для каждого узла левое поддерево содержит только меньшие значения, а правое — только большие. Это инвариант BST.

Поиск — сравниваем с текущим узлом и идём влево или вправо. Сложность O(h), где h — высота дерева.

Вставка — спускаемся по дереву, как при поиске, и ставим новый узел на место первого встреченного null.

Удаление — три случая: лист (просто удаляем), один потомок (заменяем потомком), два потомка (заменяем in-order successor — минимумом из правого поддерева).

Сложность: O(log n) среднее, O(n) худший случай (вырожденное дерево при вставке отсортированных данных).

Деградация — при вставке отсортированных данных BST превращается в цепочку. Решение — самобалансирующиеся деревья (AVL, красно-чёрное). Именно они используются в SortedSet и SortedDictionary C#.