Двоичное дерево поиска (BST)
Последнее обновление
Двоичное дерево поиска хранит значения в отсортированном порядке: для каждого узла все значения в его левом поддереве меньше, а все в правом поддереве больше. Чтобы вставить или найти значение, вы начинаете с корня и многократно идёте влево или вправо в зависимости от сравнения, так что каждый шаг вдвое сокращает область поиска. Нажмите воспроизведение выше, чтобы увидеть, как значения размещаются по сравнению и как поиск спускается по дереву.
На сбалансированном дереве эти операции выполняются за время O(log n). Подвох: вставка уже отсортированных данных превращает дерево в связный список с операциями O(n) - именно поэтому существуют самобалансирующиеся варианты, такие как AVL- и красно-чёрные деревья.
Временная и пространственная сложность
| Операция | Сбалансированное | Худший случай (вырожденное) |
|---|---|---|
| Поиск | O(log n) | O(n) |
| Вставка | O(log n) | O(n) |
| Удаление | O(log n) | O(n) |
| Память | O(n) | O(n) |
Пошагово (вставка)
| Шаг | Что происходит |
|---|---|
| 1 | Если дерево пустое, новое значение становится корнем. |
| 2 | Иначе начните с корня. |
| 3 | Если значение меньше, идите к левому потомку; если больше - вправо. |
| 4 | Повторяйте, пока не достигнете пустого места. |
| 5 | Прикрепите там новое значение как лист. |
Разобранный пример
Вставка [5, 3, 8, 1, 4] в пустое дерево, по одному значению за раз:
| Вставка | Пройденный путь | Действие |
|---|---|---|
5 | - | Дерево пустое, поэтому 5 становится корнем. |
3 | 5 | 3 < 5, идём влево; место пустое, прикрепляем 3 как левого потомка 5. |
8 | 5 | 8 > 5, идём вправо; место пустое, прикрепляем 8 как правого потомка 5. |
1 | 5 -> 3 | 1 < 5 идём влево, затем 1 < 3 идём влево; прикрепляем 1 как левого потомка 3. |
4 | 5 -> 3 | 4 < 5 идём влево, затем 4 > 3 идём вправо; прикрепляем 4 как правого потомка 3. |
Когда использовать двоичное дерево поиска
| Используйте, когда | Избегайте, когда |
|---|---|
| Нужен отсортированный порядок и быстрый поиск, а вставки поступают в случайном порядке. | Ваши данные поступают уже отсортированными: несбалансированный BST деградирует до O(n) на операцию. |
| Вы хотите, чтобы симметричный обход бесплатно выдавал значения в отсортированной последовательности. | Нужны только проверки принадлежности без порядка: хеш-таблица даёт в среднем O(1) при поиске. |
| Нужны запросы по диапазону или преемник/предшественник ключа. | Нужны гарантированные границы O(log n): используйте самобалансирующееся AVL- или красно-чёрное дерево. |
| Набор данных часто меняется, а обновление статического отсортированного массива было бы дорогим. | Набор данных фиксирован и только для чтения: отсортированный массив с двоичным поиском проще и дружелюбнее к кешу. |
Код Binary Search Tree
Чистая, готовая к запуску реализация Binary Search Tree на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Binary Search Tree на Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))Код Binary Search Tree на JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));Код Binary Search Tree на Java
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}Код Binary Search Tree на C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}Код Binary Search Tree на C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}Вопросы и ответы о двоичном дереве поиска
Какова временная сложность двоичного дерева поиска?
Поиск, вставка и удаление стоят
O(log n) на сбалансированном дереве, потому что каждое сравнение отбрасывает половину оставшихся узлов. В худшем случае (дерево, вырожденное в цепочку из-за отсортированных вставок) они деградируют до O(n).В чём разница между двоичным деревом и двоичным деревом поиска?
Двоичное дерево - это любое дерево, где у каждого узла не более двух потомков, без правила упорядочивания. Двоичное дерево поиска добавляет инвариант: значения левого поддерева меньше, а правого больше значения узла, что и обеспечивает быстрый поиск.
Почему двоичное дерево поиска может стать медленным?
Если значения вставляются в отсортированном (или обратно отсортированном) порядке, каждый новый узел идёт в одну и ту же сторону, образуя высокое вырожденное дерево, ведущее себя как связный список, то есть
O(n) на операцию. Самобалансирующиеся деревья (AVL, красно-чёрные) вращают узлы, чтобы предотвратить это.В чём разница между двоичным деревом поиска и хеш-таблицей?
Хеш-таблица даёт в среднем
O(1) при поиске, но хранит ключи без определённого порядка, поэтому не может отвечать на запросы по диапазону или преемнику. Двоичное дерево поиска немного медленнее с O(log n), но хранит ключи упорядоченными, позволяя обходить их по порядку и находить ближайшие значения. Выбирайте BST, когда важен порядок, и хеш-таблицу, когда нужны только проверки принадлежности.Когда следует использовать самобалансирующееся дерево вместо простого BST?
Используйте самобалансирующееся дерево (AVL, красно-чёрное) всякий раз, когда не можете контролировать порядок вставки и нуждаетесь в гарантированной производительности
O(log n). Простой BST подходит для обучения, для небольших наборов данных или когда ключи поступают в случайном порядке, но он не защищает от вырожденного худшего случая.Возвращает ли симметричный обход BST отсортированные значения?
Да. Посещение левого поддерева, затем узла, затем правого поддерева выдаёт ключи по возрастанию, что напрямую следует из инварианта BST. Распространённая ошибка состоит в том, чтобы ожидать того же от простого двоичного дерева: без правила упорядочивания симметричный обход не даёт никакой осмысленной последовательности.
Связанные ресурсы
Больше визуализаций
