Что такое BST?
Бинарное дерево поиска (Binary Search Tree) — это дерево, где для каждого узла выполняется правило: все элементы в левом поддереве меньше, а в правом — больше.
Пример кода на C++
#include <iostream>
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
Node* insert(Node* root, int val) {
if (!root) return new Node(val);
if (val < root->data)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
return root;
}
bool search(Node* root, int val) {
if (!root) return false;
if (root->data == val) return true;
if (val < root->data)
return search(root->left, val);
return search(root->right, val);
}Сложность
- Сбалансированное дерево: O(log n) для поиска, вставки, удаления
- Дегенерированное (как связный список): O(n)
std::set и std::map в C++ STL используют сбалансированные BST (красно-чёрные деревья)
Добавить комментарий