---
title: "Двоичное дерево поиска"
url: https://algopath.pro/ru/patterns/bst
language: ru
summary: "Дерево поиска держит все меньшие значения слева, а большие справа. Каждый поиск отбрасывает целиком одну сторону дерева."
updated: 2026-08-24
---

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

Дерево поиска держит все меньшие значения слева, а большие справа. Каждый поиск отбрасывает целиком одну сторону дерева.

## Двоичное дерево поиска: как это работает?

Каждый узел делит своё поддерево надвое. Слева всё меньше, справа всё больше.

Поиск сравнивает цель с текущим узлом. Сравнение выбирает одного потомка и отбрасывает другого.

Вставка идёт тем же путём вниз. Новый узел становится потомком последнего достигнутого.

Правило касается целых поддеревьев, а не только прямых потомков. Левый внук всё равно обязан быть меньше корня.

Симметричный обход читает значения по возрастанию. Именно на это свойство опирается большинство задач.

Отсортированный вход строит одну длинную цепочку. Тогда операция стоит n, и лечит это балансировка.

- `корень = 5` Вставляем 5, 3, 8 и 4. Первое значение становится корнем.
- `3 уходит влево` Тройка меньше пятёрки. Она становится левым потомком.
- `8 уходит вправо` Восьмёрка больше пятёрки. Она становится правым потомком.
- `4 идёт влево, потом вправо` Четвёрка меньше пятёрки, но больше тройки.
- `симметричный обход: 3, 4, 5, 8` Чтение по порядку даёт отсортированные значения.

## Двоичное дерево поиска: когда применять?

- двоичное дерево поиска: left < node < right в каждом узле
- вставка/удаление/поиск с сохранением порядка данных
- проверить BST / k-й наименьший / симметричный обход даёт отсортированную последовательность
- ближайшее значение или запрос по диапазону на множестве, которое меняется со временем
- массив заранее не дан, значения приходят по одному

## Двоичное дерево поиска: с чем путают?

- **Бинарный поиск (массив)** - Массив делится пополам по индексу, но вставка в него дорога. Дерево делится по указателю и вставку берёт.
- **Хеш-множество / словарь** - Словарь быстрее для точного поиска. Дерево ещё отвечает про диапазоны и даёт порядок.
- **Бинарная куча / очередь с приоритетом** - Куча обещает только минимум в корне. Дерево поиска упорядочивает каждую пару узлов.
- **Обход дерева** - Та страница про обход всего дерева. Эта про правило упорядочивания.

## Двоичное дерево поиска: сложность по времени и памяти

Сбалансированное дерево при n до 1e6 даёт O(log n) на операцию. Несбалансированное вырождается в O(n).

## Двоичное дерево поиска: разбор примера

### Проверить, что дерево является деревом поиска

Определите, соблюдает ли двоичное дерево правило дерева поиска.

Все значения слева обязаны быть меньше, а все значения справа больше.

Сравнения узла с двумя его потомками недостаточно.

Вместо этого несите вниз нижнюю и верхнюю границу. Каждый шаг ужимает одну из них.

```javascript
function isValidBST(root, low = -Infinity, high = Infinity) {
    if (!root) return true;

    // the bound comes from an ancestor, not from the parent alone
    if (root.val <= low || root.val >= high) return false;

    return isValidBST(root.left, low, root.val)
        && isValidBST(root.right, root.val, high);
}
```

## Двоичное дерево поиска: частые ошибки

- **Проверяют только прямых потомков** Глубокий узел может нарушить правило относительно дальнего предка. Передавайте границы вниз.
- **Считают дерево сбалансированным** Отсортированные вставки строят цепочку, а не дерево. Тогда log n на деле равно n.
- **Не решают, куда идут дубликаты** Условие обязано сказать, в какую сторону идёт повтор. Выберите сторону и держитесь её.
- **Небрежно удаляют узел с двумя потомками** Его заменяет следующий по порядку узел. Любой другой ломает упорядоченность.

## Двоичное дерево поиска: задачи с собеседований

- **Проверка дерева поиска** Несите вниз нижнюю и верхнюю границу.
- **Поиск в дереве поиска** Одно сравнение отбрасывает половину дерева.
- **Вставка в дерево поиска** Спуститесь вниз и подвесьте узел к последнему.
- **Удаление узла из дерева поиска** Заменяйте его следующим по порядку узлом.
- **K-е наименьшее в дереве поиска** Прервите симметричный обход после k узлов.
- **Наименьший общий предок в дереве поиска** Первый узел, оказавшийся между двумя значениями.
- **Дерево поиска из отсортированного массива** Средний элемент становится корнем, дальше рекурсия.

## JavaScript

```javascript
function insert(node, val) {
    if (!node) return { val, left: null, right: null };
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;
}
```

## Python

```python
def insert(node, val):
    if not node:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node
```

## PHP

```php
function insert(?TreeNode $node, int $val): TreeNode {
    if ($node === null) return new TreeNode($val);
    if ($val < $node->val) $node->left = insert($node->left, $val);
    elseif ($val > $node->val) $node->right = insert($node->right, $val);
    return $node;
}
```