Бинарное Дерево ПоискаBinary Search Tree

Инвариант BST: для любого узла x, все ключи в его левом поддереве строго меньше x.key, все ключи в правом поддереве строго больше x.key — рекурсивно, на любом уровне. Поиск ключа k начинается в корне: если k равен ключу узла — найдено; если меньше — уходим влево; если больше — уходим вправо; если дошли до nullptr — ключа нет. Вставка идёт тем же путём поиска до первого несуществующего места и создаёт там новый узел. Удаление — самый сложный случай из трёх: у узла с двумя детьми нет естественной замены на его месте, поэтому его значение заменяется на "преемника" (минимальный узел правого поддерева, гарантированно не имеющий левого ребёнка), а сам преемник удаляется рекурсивно по более простому случаю.The BST invariant: for any node x, every key in its left subtree is strictly less than x.key, every key in its right subtree is strictly greater than x.key — recursively, at every level. Searching for key k starts at the root: if k equals the node's key — found; if smaller — go left; if larger — go right; if a nullptr is reached — the key is absent. Insertion follows that same search path to the first nonexistent spot and creates a new node there. Deletion is the trickiest of the three: a node with two children has no natural replacement in its place, so its value is replaced with its "successor" (the minimum node of the right subtree, guaranteed to have no left child), and the successor itself is deleted recursively via the simpler case.

struct Node {
    int key;
    Node* left = nullptr;
    Node* right = nullptr;
};

Node* insert(Node* root, int key) {
    if (!root) return new Node{key};
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                     // дубликаты игнорируются// duplicates ignored
}

Node* find_min(Node* root) {              // самый левый узел// the leftmost node
    while (root->left) root = root->left;
    return root;
}

Node* remove(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->key) root->left = remove(root->left, key);
    else if (key > root->key) root->right = remove(root->right, key);
    else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        Node* succ = find_min(root->right);   // два ребёнка: заменить преемником// two children: replace with successor
        root->key = succ->key;
        root->right = remove(root->right, succ->key);
    }
    return root;
}

insert/search/delete запускают спуск по дереву шаг за шагом автоматически — оранжевая рамка отмечает узел, который сравнивается прямо сейчас. Кнопка "вставить по порядку 1..7" специально показывает вырождение в цепочку.insert/search/delete auto-play the descent through the tree step by step — the orange outline marks the node being compared right now. The "insert in order 1..7" button deliberately demonstrates degeneration into a chain.

Средний случай O(log n) справедлив только при случайном порядке вставки — тогда дерево, построенное на n случайных ключах, имеет ожидаемую высоту O(log n) (тот же результат, что и ожидаемое число сравнений в быстрой сортировке, не случайно: оба процесса — это, по сути, одно и то же рекурсивное разбиение). Но входные данные редко случайны в реальных системах: отсортированные логи, последовательные ID, данные, уже прошедшие через другую сортировку, — всё это адверсариальные случаи для наивного BST, превращающие его в O(n) на операцию.The average-case O(log n) only holds under random insertion order — then a tree built from n random keys has expected height O(log n) (the same result as the expected comparison count in quicksort, not by coincidence: both processes are, at bottom, the same recursive partitioning). But real-world input is rarely random: sorted logs, sequential IDs, data that has already gone through another sort — all of these are adversarial cases for a naive BST, turning it into O(n) per operation.

AVL-деревья (2.3.2.2), красно-чёрные деревья (2.3.2.3) и splay-деревья (2.3.2.4) — три разных ответа на этот риск: первые два поддерживают явный инвариант баланса и перестраивают часть дерева (ротациями) после каждой вставки/удаления, которая его нарушает; splay-дерево не поддерживает инвариант вовсе, но гарантирует амортизированную O(log n) через собственную дисциплину доступа. Ни один из них не меняет саму идею "сравнение → влево/вправо" — они лишь добавляют механизм, который не даёт высоте выйти из-под контроля.AVL trees (2.3.2.2), red-black trees (2.3.2.3), and splay trees (2.3.2.4) are three different answers to this risk: the first two maintain an explicit balance invariant and restructure part of the tree (via rotations) after any insertion/deletion that violates it; a splay tree maintains no invariant at all, but guarantees amortized O(log n) through its own access discipline. None of them changes the core idea of "compare → left/right" — they just add a mechanism that keeps the height from spiraling out of control.