DEV//UNIT
← Алгоритмыdata-structures

Двоичное дерево поиска

Слева меньше, справа больше: поиск как в отсортированном массиве, вставка — как в списке.

время O(h); O(log n) если сбалансированопамять O(n)уровень: начальный
Что происходит сейчас0/0
Нажмите Play, чтобы запустить сценарий
TypeScript — активная строка подсвечена шагом
1class BSTNode {
2  value: number
3  left: BSTNode | null = null
4  right: BSTNode | null = null
5  constructor(value: number) { this.value = value }
6}
7 
8function insert(root: BSTNode | null, value: number): BSTNode {
9  if (root === null) return new BSTNode(value)
10  if (value < root.value) root.left = insert(root.left, value)
11  else root.right = insert(root.right, value)
12  return root
13}
14 
15function search(root: BSTNode | null, value: number): BSTNode | null {
16  let cur = root
17  while (cur !== null) {
18    if (value === cur.value) return cur
19    cur = value < cur.value ? cur.left : cur.right
20  }
21  return null
22}

Проблема

Хотим и быстрый поиск, и дешёвые вставки. Массив даёт поиск, но вставка дорогая; список — наоборот. Дерево ищет по следу сравнений и вставляет листом.

Что вы видите

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

Как это работает

Инвариант BST: для каждого узла всё левое поддерево меньше, правое больше. Поиск/вставка/удаление — O(h). Если вставлять отсортированные данные — дерево вырождается в список (O(n)); сбалансированные деревья (AVL, красно-чёрные) держат h = O(log n).

Пошаговый разбор

  1. 01

    Спуск

    Сравнение с узлом: влево или вправо.

  2. 02

    Вставка

    Новый лист на конце пути.

  3. 03

    Поиск

    Тот же спуск до значения.

  4. 04

    Баланс

    Вырождение в список лечится поворотами.

Complexity и ограничения

time
O(h); O(log n) если сбалансировано
space
O(n)

O(h) на операции; O(log n) если сбалансировано, O(n) в вырожденном.

Edge cases

  • Отсортированная вставка

    Дерево-цепочка — худший случай.

  • Удаление с двумя детьми

    Замена на минимум правого поддерева.

  • Дубликаты

    Политика: направо или счётчиком.

Где встречается в реальности

Индексы БД

B-деревья — многопутевые наследники BST.

std::map

Красно-чёрные деревья в STL.

Интервалы

Деревья отрезков и диапазонные запросы.

Связанные алгоритмы

Бинарный поискПирамидальная сортировка
Shorts

«Массив или список? Дерево. Смотри, как оно растёт»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Массив или список? Дерево. Смотри, как оно растёт
Нажмите Play
Бит 1/6 · 0–2 с
Hook
script-setup.ru/algorithms/bst