Бинарное дерево С++
Бинарное дерево (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++ (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 }
Самое интересное — удаление узла, у него три случая:
- у узла нет потомков — узел просто удаляется;
- один потомок — потомок занимает место удаляемого узла;
- два потомка — в узел копируется минимальный ключ правого поддерева (следующий по порядку), а затем этот минимальный узел удаляется из правого поддерева (у него не больше одного потомка, поэтому это сводится к первым двум случаям).
Обходы дерева
- Симметричный (in-order): левое поддерево → узел → правое поддерево. Для дерева поиска выдаёт ключи по возрастанию — функция
inorderв примере. - Прямой (pre-order): узел → левое → правое. Удобен для копирования и сохранения структуры дерева.
- Обратный (post-order): левое → правое → узел. Используется при удалении всего дерева: потомки удаляются раньше родителя.
- В ширину (по уровням): узлы обходятся уровень за уровнем с помощью очереди (
std::queue).
Сбалансированные деревья и STL
Чтобы операции всегда работали за O(log n), дерево поддерживают сбалансированным — после вставки и удаления выполняются повороты узлов:
- AVL-дерево — высоты левого и правого поддерева любого узла отличаются не больше чем на 1; поиск чуть быстрее;
- Красно-чёрное дерево — более мягкое правило, меньше поворотов при изменениях.
В реальных программах на C++ своё дерево писать не нужно: std::set и std::map — упорядоченные контейнеры с гарантией O(log n), в распространённых реализациях (GCC, Clang, MSVC) это красно-чёрное дерево. Если порядок ключей не важен, обычно быстрее std::unordered_map (хеш-таблица, в среднем O(1)).
Актуально ли это в 2026 году
Да. Писать BST вручную в рабочем коде приходится редко, но сама идея лежит в основе многих инструментов:
std::map,std::setи упорядоченные коллекции в других языках (напримерTreeMapв Java);- B-деревья и B+-деревья — индексы баз данных (InnoDB в MySQL, PostgreSQL) и файловых систем; это обобщение дерева поиска, где у узла много потомков;
- задачи на деревья — классика собеседований и олимпиад по программированию.
Поэтому реализация дерева поиска с нуля — хорошее упражнение на указатели, рекурсию и оценку сложности алгоритмов.
Читайте также:
Рекомендуемые обзоры инструментов
Инновационный браузер с поддержкой ИИ
Бесконечные профили для арбитража
Надежное решение для мультиаккаунтинга
Лидер рынка для арбитражников