Бинарные деревья поиска

Дерево — одна из наиболее распространённых структур данных в программировании.

Деревья состоят из набора вершин (узлов, нод) и ориентированных рёбер (ссылок) между ними. Вершины связаны таким образом, что от какой-то одной вершины, называемой корневой, можно дойти до всех остальных единственным способом.

Связанные определения:

• Родитель вершины \(v\) — вершина, из которой есть прямая ссылка в \(v\).

• Дети (дочерние элементы) вершины \(v\) — вершины, в которые из \(v\) есть прямая ссылка.

• Предки — родители родителей, их родители, и так далее.

• Потомки — дети детей, их дети, и так далее.

• Лист (терминальная вершина) — вершина, не имеющая детей.

• Поддерево — вершина дерева вместе со всеми её потомками.

• Степень вершины — количество её детей.

• Глубина вершины — расстояние от корня до неё.

• Высота дерева — максимальная из глубин всех вершин.

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

Бинарные деревья поиска

Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:

• У каждой вершины не более двух детей.

• Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).

• У всех вершин левого поддерева вершины \(v\) ключи не больше, чем ключ \(v\).

• У всех вершин правого поддерева вершины \(v\) ключи больше, чем ключ \(v\).

• Оба поддерева — левое и правое — являются двоичными деревьями поиска.

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

Представление в памяти

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

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

Пустое дерево (или отсутствие поддерева) представляется нулевым указателем nullptr.

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

Поиск элемента с ключом \(x\) начинается с корня. На каждом шаге мы сравниваем \(x\) с ключом текущей вершины:

• если \(x\) равен ключу — элемент найден;
• если \(x\) меньше — переходим в левое поддерево;
• если \(x\) больше — переходим в правое поддерево.

Если мы дошли до пустого указателя, значит, элемента в дереве нет.

Node* Find(int key, Node* root) {
    if (root == nullptr) {
        return nullptr;
    }
    if (key < root->key) {
        return Find(key, root->left);
    }
    if (key > root->key) {
        return Find(key, root->right);
    }
    return root;
}

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

Поиск минимума и максимума

Минимальный элемент — это самая левая вершина дерева. Чтобы его найти, достаточно идти налево, пока возможно:

Node* FindMin(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}

Аналогично, максимальный элемент — самая правая вершина.

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

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

Node* Insert(int key, Node* root) {
    if (root == nullptr) {
        return new Node{key};
    }
    if (key < root->key) {
        root->left = Insert(key, root->left);
    } else if (key > root->key) {
        root->right = Insert(key, root->right);
    }
    return root;
}

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

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

Удаление — самая нетривиальная операция в BST. Сначала нужно найти вершину с заданным ключом. Дальше возможны три случая.

Случай 1: вершина — лист. Просто удаляем её.

Случай 2: у вершины один ребёнок. Удаляем вершину, а её единственного ребёнка подставляем на её место.

Случай 3: у вершины два ребёнка. Находим следующий по порядку элемент — минимум правого поддерева. Копируем его ключ в удаляемую вершину, а затем рекурсивно удаляем этот минимум из правого поддерева (он гарантированно имеет не более одного ребёнка, поэтому удаление будет простым).

Node* Remove(int key, Node* root) {
    if (root == nullptr) {
        return nullptr;
    }

    if (key < root->key) {
        root->left = Remove(key, root->left);
    } else if (key > root->key) {
        root->right = Remove(key, root->right);
    } else {
        if (root->left == nullptr) {
            Node* right_child = root->right;
            delete root;
            return right_child;
        }
        if (root->right == nullptr) {
            Node* left_child = root->left;
            delete root;
            return left_child;
        }

        Node* successor = FindMin(root->right);
        root->key = successor->key;
        root->right = Remove(successor->key, root->right);
    }
    return root;
}

Здесь первые два случая объединены: если одного из поддеревьев нет, мы просто возвращаем другое. Если отсутствуют оба — возвращается nullptr, что тоже корректно.

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

Обход дерева — это посещение всех его вершин в определённом порядке. Для бинарных деревьев есть три классических обхода, которые различаются моментом обработки текущей вершины:

• Inorder (симметричный): сначала левое поддерево, затем текущая вершина, затем правое поддерево.
• Preorder (прямой): сначала текущая вершина, затем левое поддерево, затем правое.
• Postorder (обратный): сначала левое поддерево, затем правое, затем текущая вершина.

Для дерева поиска inorder-обход обладает особым свойством: он перечисляет ключи в отсортированном порядке. Это прямое следствие определения BST.

void Inorder(Node* root, std::vector<int>& result) {
    if (root == nullptr) {
        return;
    }
    Inorder(root->left, result);
    result.push_back(root->key);
    Inorder(root->right, result);
}

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

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

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

Высота дерева зависит от порядка вставок. Если элементы вставляются в случайном порядке, средняя высота дерева составляет \(O(\log n)\). Однако в худшем случае, например при вставке уже отсортированной последовательности, дерево вырождается в «бамбук» — цепочку, где каждая вершина имеет только одного ребёнка. В этом случае \(h = n - 1\), и все операции деградируют до \(O(n)\).

Операция	Средний случай	Худший случай
Поиск	\(O(\log n)\)	\(O(n)\)
Вставка	\(O(\log n)\)	\(O(n)\)
Удаление	\(O(\log n)\)	\(O(n)\)
Минимум/Максимум	\(O(\log n)\)	\(O(n)\)
Inorder-обход	\(O(n)\)	\(O(n)\)

Сбалансированные деревья

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

Наиболее известные варианты:

• AVL-дерево — для любой вершины высоты левого и правого поддеревьев отличаются не более чем на 1. Балансировка производится вращениями.
• Красно-чёрное дерево — каждая вершина окрашена в красный или чёрный цвет, и набор правил на цвета гарантирует, что высота не превышает \(2 \log_2(n+1)\).

Во всех этих деревьях основные операции гарантированно работают за \(O(\log n)\).

BST в стандартной библиотеке

В C++ STL контейнеры std::set и std::map реализованы на основе сбалансированных деревьев поиска (как правило, красно-чёрных).

std::set

Хранит множество уникальных ключей в отсортированном порядке.

std::set<int> s;

s.insert(5);
s.insert(3);
s.insert(7);
s.insert(3); // дубликат, не добавится

s.count(5);  // 1 (элемент есть)
s.count(4);  // 0 (элемента нет)

s.erase(5);  // удалить элемент

auto it = s.begin();  // итератор на минимальный элемент
auto it2 = s.rbegin(); // итератор на максимальный

auto it3 = s.lower_bound(4); // первый элемент >= 4
auto it4 = s.upper_bound(4); // первый элемент > 4

Все операции — insert, erase, find, count, lower_bound, upper_bound — работают за \(O(\log n)\).

Если нужно хранить дубликаты, используется std::multiset.

std::map

Хранит пары «ключ — значение», упорядоченные по ключу. По сути это то же дерево поиска, но каждая вершина хранит ещё и ассоциированное значение.

std::map<std::string, int> m;

m["alice"] = 100;
m["bob"] = 200;

m["alice"]; // 100
m.count("charlie"); // 0

for (auto& [key, value] : m) {
    std::cout << key << ": " << value << "\n";
}

Обход std::map и std::set через итераторы (или range-based for) даёт элементы в отсортированном порядке — именно потому, что внутри используется дерево поиска.

Для интуиции полезно посмотреть визуализацию.