Деревья поиска

1. Бинарное дерево поиска

Бинарное дерево поиска (англ. binary search tree, BST) — дерево, в котором:

у каждой вершины не более двух детей;
все вершины обладают ключами, на которых определено сравнение (числа, строки и т.д.);
у всех вершин левого поддерева вершины v ключи не больше, чем ключ v;
у всех вершин правого поддерева вершины v ключи больше, чем ключ v;
оба поддерева — левое и правое — сами являются бинарными деревьями поиска (свойство рекурсивно).

Бывают и небинарные деревья поиска, где у вершины может быть больше двух детей — тогда ключи в «более левых» поддеревьях должны быть меньше ключей в «более правых». Далее речь пойдет только о бинарном случае.

Стандартное представление вершины:

cpp

struct Node {
    T key;
    Node* left;
    Node* right;
    Node* parent;
};

Из свойства BST следует главное удобство этой структуры: симметричный обход дерева (см. раздел 5) выдает все ключи в отсортированном порядке.

2. Поиск элемента

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

cpp

Node* search(Node* x, T k) {
    if (x == nullptr || k == x->key)
        return x;
    if (k < x->key)
        return search(x->left, k);
    else
        return search(x->right, k);
}

Сложность в худшем случае — O(h), где h — высота дерева, так как посещенные вершины образуют путь от корня вниз. В худшем случае это путь через все дерево целиком (см. раздел 6).

3. Вставка элемента

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

cpp

Node* insert(Node* x, T z) {          // x — корень поддерева, z — вставляемый ключ
    if (x == nullptr)
        return new Node(z);           // создаем лист с ключом z
    else if (z < x->key)
        x->left = insert(x->left, z);
    else if (z > x->key)
        x->right = insert(x->right, z);
    return x;
}

Новый узел всегда становится листом — структура дерева выше точки вставки не меняется, поэтому вставка, как и поиск, работает за O(h).

4. Удаление элемента

Удаление сложнее, потому что удаляемая вершина может иметь детей, которых некуда «выбросить» вместе с ней. Распадается на три случая:

Удаляемый ключ меньше текущего — рекурсивно удаляем его из левого поддерева.
Удаляемый ключ больше текущего — рекурсивно удаляем его из правого поддерева.
Нашли вершину с искомым ключом (она в корне текущего поддерева) — тут два пути:
- у вершины два потомка — нельзя просто вырезать ее из середины дерева, не нарушив порядок. Вместо этого находим минимальный элемент ее правого поддерева (это следующий по величине ключ после удаляемого), копируем его значение в удаляемую вершину, а затем рекурсивно удаляем этот минимальный элемент из правого поддерева (он гарантированно имеет не больше одного потомка, так как он минимальный, то есть удаление сводится к следующему подслучаю);
- у вершины не больше одного потомка — просто заменяем вершину этим ее ребенком (или null, если детей нет).

cpp

Node* remove(Node* root, T z) {
    if (root == nullptr)
        return root;
    if (z < root->key)
        root->left = remove(root->left, z);
    else if (z > root->key)
        root->right = remove(root->right, z);
    else if (root->left != nullptr && root->right != nullptr) {
        root->key = minimum(root->right)->key;
        root->right = remove(root->right, root->key);
    } else {
        root = (root->left != nullptr) ? root->left : root->right;
    }
    return root;
}

Как и поиск со вставкой, удаление работает за O(h) — на вычисление минимума в худшем случае тоже уходит O(h)

5. Обходы дерева

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

5.1. Симметричный обход (in-order)

Порядок: левое поддерево → корень → правое поддерево.

cpp

void inorder(Node* x) {
    if (x == nullptr) return;
    inorder(x->left);
    visit(x);
    inorder(x->right);
}

Благодаря свойству упорядоченности мы посещаем все ключи по возрастанию. Таким обходом можно вывести дерево отсортированным списком за O(n)

5.2. Прямой обход (pre-order)

Порядок: корень → левое поддерево → правое поддерево.

cpp

void preorder(Node* x) {
    if (x == nullptr) return;
    visit(x);
    preorder(x->left);
    preorder(x->right);
}

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

5.3. Обратный обход (post-order)

Порядок: левое поддерево → правое поддерево → корень.

cpp

void postorder(Node* x) {
    if (x == nullptr) return;
    postorder(x->left);
    postorder(x->right);
    visit(x);
}

Вершина посещается только после обоих поддеревьев — удобно там, где перед обработкой узла нужно обработать (или, например, удалить/освободить память) обоих его детей.

5.4. Обход в ширину (BFS)

Этот миньон вам хорошо знаком, в представлении не нуждается

cpp

void bfs(Node* root) {
    queue<Node*> q;
    if (root != nullptr) q.push(root);
    while (!q.empty()) {
        Node* x = q.front(); q.pop();
        visit(x);
        if (x->left != nullptr) q.push(x->left);
        if (x->right != nullptr) q.push(x->right);
    }
}

6. Бамбук

Высота BST напрямую зависит от порядка вставки ключей, а не только от их набора.

Если вставлять ключи в уже отсортированном порядке — например, 1, 2, 3, 4, 5 — то каждый новый ключ больше всех предыдущих, а значит, всегда уходит в правое поддерево последней вставленной вершины:

Получается так называемый «бамбук» — вырожденное дерево, фактически представляющее собой обычный односвязный список. Высота такого дерева равна h = n, поэтому поиск, вставка и удаление в худшем случае работают не за O(log n), а за O(n), что сводит на нет все преимущество древовидной структуры перед списком.

Именно поэтому на практике голое BST без балансировки опасно использовать, когда входные данные могут поступать в отсортированном или почти отсортированном порядке — а cбалансированные деревья существуют именно для того, чтобы гарантировать O(log n) высоту независимо от порядка вставки.

7. Splay-дерево

Splay-дерево — это BST, которое после каждой операции (поиска, вставки или удаления) поднимает затронутую вершину в корень серией поворотов — эта операция называется splay («расплющивание», «вытягивание наверх»).

Поднятие вершины x к корню делается не одним поворотом, а парами поворотов, в зависимости от взаимного расположения x, ее родителя p и предка (родитель родителя) g:

zig — x уже ребенок корня: один обычный поворот вокруг p;
zig-zig — x и p оба левые (или оба правые) дети: сначала поворот вокруг g, затем вокруг p;
zig-zag — x и p — дети разной «стороны» (один левый, другой правый): поворот вокруг p, затем вокруг g (аналог LR/RL-поворотов в AVL-дереве).

Splay продолжается такими парами шагов, пока x не окажется в корне.

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

Сложность. Отдельная операция может стоить O(n) (если дерево временно вырождено), но суммарно на любую последовательность из m операций уходит O(m log n), то есть амортизированная сложность одной операции — O(log n).

8. Красно-черное дерево

Красно-черное дерево — это BST, в котором каждая вершина дополнительно раскрашена в красный или черный цвет, а раскраска подчиняется правилам:

корень — всегда черный;
у красной вершины оба ребенка — черные (то есть два красных узла не могут идти подряд);
null-листья (отсутствующие дети) считаются черными;
на любом пути от вершины до любого ее null-потомка встречается одинаковое число черных вершин (это число называется черной высотой).

Отсюда следует ключевое свойство: самый длинный путь от корня до листа не может быть больше чем в 2 раза длиннее самого короткого (иначе на длинном пути пришлось бы нарушить правило про два красных узла подряд, чтобы уравнять число черных вершин). Это гарантирует высоту дерева не более $2 \log (n + 1)$ , то есть O(log n) в худшем случае.

Балансировка. После обычной BST-вставки (новый узел красится в красный) или удаления могут нарушиться условие 2 или 4 — тогда происходит перекраска соседних вершин и, если перекраски недостаточно, повороты (те же left/right-повороты, что и в AVL-дереве), которые восстанавливают инварианты, поднимаясь не выше чем на несколько уровней вверх по дереву.

Сложность. Поиск, вставка и удаление — гарантированно O(log n) в худшем случае. Красно-черные деревья на практике требуют меньше поворотов при вставке/удалении, чем AVL-деревья (за счет менее строгого баланса), поэтому именно они лежат в основе std::map/std::set в C++ и TreeMap в Java.

Деревья поиска ​

1. Бинарное дерево поиска ​

2. Поиск элемента ​

3. Вставка элемента ​

4. Удаление элемента ​

5. Обходы дерева ​

5.1. Симметричный обход (in-order) ​

5.2. Прямой обход (pre-order) ​

5.3. Обратный обход (post-order) ​

5.4. Обход в ширину (BFS) ​

6. Бамбук ​

7. Splay-дерево ​

8. Красно-черное дерево ​