Дерево поиска (BST)

Интуиция: словарь, который открываешь посередине

Как ты ищешь слово в бумажном словаре? Открываешь примерно посередине. Если нужное слово дальше по алфавиту, листаешь вправо, если раньше — влево. На каждом шаге половина книги отпадает.

Дерево поиска (Binary Search Tree, BST) устроено по тому же принципу. Можно сказать, что это бинарный поиск, «застывший» в форме дерева.

Свойство BST

Для каждого узла выполняются два условия:

• все значения в левом поддереве меньше значения узла;
• все значения в правом поддереве больше значения узла.

Слово «все» здесь главное. Мало, чтобы левый ребёнок был меньше родителя: меньше узла должно быть всё его левое поддерево целиком.

Обычно считают, что дубликатов в BST нет. Если они возможны, на собесе договорись с интервьюером, куда их класть: влево или вправо.

Поиск: идём одной тропинкой

Ищем 6 в дереве выше:

1. В корне 8. Шестёрка меньше, значит, идём влево.
2. Здесь 3. Шестёрка больше, идём вправо.
3. Здесь 6. Нашли!

На каждом шаге мы спускаемся на один уровень и отбрасываем целое поддерево. Поэтому поиск стоит O(h), где h — высота дерева.

Вставка: ищем место, где «должно было быть»

Вставка почти не отличается от поиска. Идём так же влево или вправо, пока не упрёмся в пустое место (null). Туда и подвешиваем новый узел. Новый элемент всегда становится листом, и перестраивать остальное дерево не нужно.

Например, при вставке 7 путь будет 8 → 3 → 6. Правый ребёнок у 6 пустой, туда 7 и встанет.

class Node:
    def __init__(self, val):
        self.val, self.left, self.right = val, None, None

def search(root, x):
    # спускаемся, пока не найдём или не упрёмся в пустоту
    while root and root.val != x:
        root = root.left if x < root.val else root.right
    return root

def insert(root, x):
    if root is None:
        return Node(x)          # нашли пустое место — вешаем лист
    if x < root.val:
        root.left = insert(root.left, x)
    elif x > root.val:
        root.right = insert(root.right, x)
    return root                 # дубликаты игнорируем

Симметричный обход даёт отсортированный порядок

Вспомни inorder: левое поддерево → узел → правое поддерево. В BST всё левое меньше узла, а всё правое больше. Поэтому такой обход выдаёт значения по возрастанию: 1, 3, 6, 8, 9, 10, 14.

Это очень полезный факт, держи его в голове:

• нужен k-й по величине элемент — делай inorder и считай шаги;
• нужно отсортированное содержимое — делай inorder, сортировка не понадобится.

Как проверить, что дерево — BST

Вот классическая ловушка. Посмотри на дерево:

Проверка «левый ребёнок меньше, правый больше» здесь пройдёт, а дерево всё равно неправильное. Сравнивать только с родителем недостаточно.

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

• у корня диапазон (−∞, +∞);
• уходя влево, ты сужаешь верхнюю границу до значения текущего узла;
• уходя вправо, сужаешь нижнюю границу.

В примере узел 6 получает диапазон (3, 5), а 6 в него не входит. Значит, дерево не BST.

Есть и альтернатива: сделать inorder и проверить, что последовательность строго возрастает. Оба подхода работают за O(n). Саму задачу ты решишь в практике главы.

Сбалансированность: почему h может быть n

Мы везде писали O(h), а не O(log n). Причина вот в чём. Попробуй вставить числа 3, 2, 1 по порядку:

Получился, по сути, связный список. Высота h = n, и поиск стал O(n).

Форма дерева	Высота h	Поиск / вставка
Сбалансированное	≈ log n	O(log n)
Вырожденное («палка»)	n	O(n)

Чтобы высота всегда оставалась логарифмической, существуют самобалансирующиеся деревья: AVL и красно-чёрные. На них построены TreeMap в Java и std::map в C++. Писать их на собесе почти никогда не просят, но знать, что они есть, полезно.

Как это звучит на собесе

«Это BST, поэтому поиск идёт за O(h): на каждом шаге отбрасываю одно поддерево. В сбалансированном дереве это O(log n), в худшем случае, если дерево выродилось, O(n). Inorder обход даст отсортированный порядок, этим и воспользуюсь».

Частые ошибки

• Сравнивать узел только с детьми при проверке BST. Нужны границы, которые передаются вниз по всей глубине.
• Говорить «поиск в BST — O(log n)» без оговорки. Правильно так: O(h), а log n только для сбалансированного дерева.
• Использовать int как ±∞ для границ. Если в дереве встретится Integer.MIN_VALUE, проверка сломается. Используй null или long.
• Забыть return root в рекурсивной вставке. Тогда новый узел потеряется и не прицепится к дереву.

Свойство BST, поиск и вставку ты теперь знаешь, и все задачи главы опираются именно на них.