Бинарное дерево С++

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

Бинарное дерево поиска (binary search tree, BST) — бинарное дерево с дополнительным правилом: в левом поддереве любого узла лежат только ключи меньше ключа узла, в правом — только больше. Именно благодаря этому правилу поиск не перебирает все элементы: на каждом шаге отбрасывается половина оставшегося дерева, и число шагов не превышает высоты дерева. Когда говорят «бинарное дерево» в контексте поиска и сортировки, обычно имеют в виду именно BST.

Бинарное дерево — рекурсивная структура: каждое поддерево само является бинарным деревом, поэтому большинство операций естественно записываются рекурсивными функциями.
  • Корень — верхний узел, у которого нет родителя.
  • Лист — узел без потомков.
  • Левый и правый потомок — дочерние узлы слева и справа от текущего.
  • Высота дерева — число уровней от корня до самого дальнего листа.
  • Узел хранит ключ (и при необходимости значение) и указатели на левого и правого потомка; указатель на родителя добавляют, только если он нужен алгоритму.
Операция В среднем В худшем случае
Поиск O(log n) O(n)
Вставка O(log n) O(n)
Удаление O(log n) O(n)
Обход всех узлов O(n) O(n)

Худший случай — вырожденное дерево: если вставлять уже отсортированные ключи (1, 2, 3, …), каждый новый узел становится правым потомком предыдущего, и дерево превращается в связный список. От этого защищают сбалансированные деревья (см. ниже).

Дерево поиска на современном C++ (C++17): вставка, поиск, удаление и вывод ключей по возрастанию. Память освобождается автоматически благодаря std::unique_ptr.

#include <iostream>
#include <memory>
 
struct Node {
    int key;
    std::unique_ptr<Node> left, right;
    explicit Node(int k) : key(k) {}
};
 
class BST {
public:
    void insert(int key) { insert(root, key); }
    void erase(int key)  { erase(root, key); }
    void print() const   { inorder(root.get()); std::cout << '\n'; }
 
    bool contains(int key) const {
        const Node* cur = root.get();
        while (cur) {
            if (key == cur->key) return true;
            cur = key < cur->key ? cur->left.get() : cur->right.get();
        }
        return false;
    }
 
private:
    std::unique_ptr<Node> root;
 
    static void insert(std::unique_ptr<Node>& node, int key) {
        if (!node) { node = std::make_unique<Node>(key); return; }
        if (key < node->key)      insert(node->left, key);
        else if (key > node->key) insert(node->right, key);
        // такой ключ уже есть — ничего не делаем
    }
 
    static void erase(std::unique_ptr<Node>& node, int key) {
        if (!node) return;
        if (key < node->key) { erase(node->left, key);  return; }
        if (key > node->key) { erase(node->right, key); return; }
        if (!node->left)  { node = std::move(node->right); return; }  // 0 или 1 потомок
        if (!node->right) { node = std::move(node->left);  return; }
        // два потомка: ставим на место узла минимальный ключ правого поддерева
        const Node* min = node->right.get();
        while (min->left) min = min->left.get();
        node->key = min->key;
        erase(node->right, min->key);
    }
 
    static void inorder(const Node* node) {
        if (!node) return;
        inorder(node->left.get());
        std::cout << node->key << ' ';
        inorder(node->right.get());
    }
};
 
int main() {
    BST tree;
    for (int k : {50, 30, 70, 20, 40, 60, 80}) tree.insert(k);
    tree.print();                            // 20 30 40 50 60 70 80
    std::cout << tree.contains(60) << '\n';  // 1
    tree.erase(30);                          // узел с двумя потомками
    tree.erase(50);                          // корень
    tree.print();                            // 20 40 60 70 80
}

Самое интересное — удаление узла, у него три случая:

  1. у узла нет потомков — узел просто удаляется;
  2. один потомок — потомок занимает место удаляемого узла;
  3. два потомка — в узел копируется минимальный ключ правого поддерева (следующий по порядку), а затем этот минимальный узел удаляется из правого поддерева (у него не больше одного потомка, поэтому это сводится к первым двум случаям).
  • Симметричный (in-order): левое поддерево → узел → правое поддерево. Для дерева поиска выдаёт ключи по возрастанию — функция inorder в примере.
  • Прямой (pre-order): узел → левое → правое. Удобен для копирования и сохранения структуры дерева.
  • Обратный (post-order): левое → правое → узел. Используется при удалении всего дерева: потомки удаляются раньше родителя.
  • В ширину (по уровням): узлы обходятся уровень за уровнем с помощью очереди (std::queue).

Чтобы операции всегда работали за O(log n), дерево поддерживают сбалансированным — после вставки и удаления выполняются повороты узлов:

  • AVL-дерево — высоты левого и правого поддерева любого узла отличаются не больше чем на 1; поиск чуть быстрее;
  • Красно-чёрное дерево — более мягкое правило, меньше поворотов при изменениях.

В реальных программах на C++ своё дерево писать не нужно: std::set и std::map — упорядоченные контейнеры с гарантией O(log n), в распространённых реализациях (GCC, Clang, MSVC) это красно-чёрное дерево. Если порядок ключей не важен, обычно быстрее std::unordered_map (хеш-таблица, в среднем O(1)).

Да. Писать BST вручную в рабочем коде приходится редко, но сама идея лежит в основе многих инструментов:

  • std::map, std::set и упорядоченные коллекции в других языках (например TreeMap в Java);
  • B-деревья и B+-деревья — индексы баз данных (InnoDB в MySQL, PostgreSQL) и файловых систем; это обобщение дерева поиска, где у узла много потомков;
  • задачи на деревья — классика собеседований и олимпиад по программированию.

Поэтому реализация дерева поиска с нуля — хорошее упражнение на указатели, рекурсию и оценку сложности алгоритмов.

Читайте также:

Рекомендуемые обзоры инструментов

Обзор и отзывы об антидетект браузере Aurorium AI.
Aurorium AI: Обзор и отзывы

Инновационный браузер с поддержкой ИИ

Обзор и отзывы об антидетект браузере Undetectable.
Undetectable Browser: Честный обзор

Бесконечные профили для арбитража

Антидетект браузер Vision: обзор и реальные отзывы.
Браузер Vision: Реальные отзывы

Надежное решение для мультиаккаунтинга

Обзор и отзывы об антидектет браузере Dolphin.
Dolphin {anty}: Обзор функционала

Лидер рынка для арбитражников

📌 Умный подбор сервера: Официальный инструмент проекта DIEG — агрегатор DIEG Finder. Это часть единой экосистемы, созданной для того, чтобы помочь быстро найти и сравнить по параметрам подходящий VPS/VDS сервер для любых задач хостинга.
📌 Инфраструктура для разработчиков: Для тестирования скриптов, установщиков VPN и Python-ботов рекомендуем использовать надежные VPS на короткий срок. Подробнее о быстрой аренде VPS для экспериментов читайте здесь.