Двоичное дерево поиска: правило, операции за O(h) и две задачи с собеседований

Короткий ответ. Двоичное дерево поиска это дерево с одним правилом: слева меньше, справа больше. Правило действует для каждого узла и всего его поддерева. Поиск, вставка и удаление стоят O(h), где h это высота. В сбалансированном дереве это O(log n). Ниже правило, код на Python, разбор задач Validate BST и Kth Smallest, типичные ошибки.

Что такое двоичное дерево поиска?

Каждый узел хранит значение и двух детей. Всё левое поддерево меньше узла. Всё правое поддерево больше. Это условие должно выполняться для каждого узла, а не только для корня.

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

Симметричный обход такого дерева выдаёт значения по возрастанию. Это самое полезное свойство на собеседовании.

Как двоичное дерево поиска выполняет операции?

Операция	Как	Время
Поиск	Спуск по одной ветке	O(h)
Вставка	Спуск до пустого места, новый лист	O(h)
Минимум, максимум	До упора влево или вправо	O(h)
Удаление	Лист убираем, один ребёнок поднимаем, два ребёнка заменяем на минимум правого поддерева	O(h)
Обход по возрастанию	Симметричный обход	O(n)

Высота h в худшем случае равна n. Вставьте отсортированный массив по порядку, и дерево вытянется в цепочку. Поэтому в библиотеках дерево балансируют.

По каким словам в задаче узнать приём?

• «Дано двоичное дерево поиска» в условии.
• «Проверить, что дерево является деревом поиска».
• «k-й наименьший элемент», «ближайшее значение к x».
• «Наименьший общий предок двух узлов в дереве поиска».

Если в условии сказано «дерево поиска», а решение обходит все узлы, вы упустили правило. Почти всегда можно пройти одну ветку.

Как это выглядит на примере?

Вставляем по очереди 8, 3, 10, 1, 6, 14. Корень 8. 3 меньше, влево. 10 больше, вправо. 1 меньше 8 и меньше 3, лист слева от 3. 6 меньше 8, больше 3, справа от 3. 14 справа от 10.

Ищем 6. Сравниваем с 8, влево. Сравниваем с 3, вправо. Нашли за два шага. Симметричный обход даёт 1, 3, 6, 8, 10, 14.

Как написать двоичное дерево поиска на Python?

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

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def search(root, val):
    while root and root.val != val:
        root = root.left if val < root.val else root.right
    return root

def is_valid_bst(root, lo=float("-inf"), hi=float("inf")):
    if root is None:
        return True
    if not lo < root.val < hi:
        return False
    return is_valid_bst(root.left, lo, root.val) and \
           is_valid_bst(root.right, root.val, hi)

def kth_smallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:
            stack.append(node); node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

Функция is_valid_bst передаёт вниз границы. Каждый узел должен лежать строго между ними. Это единственный верный способ проверки.

Как решить Validate Binary Search Tree?

Частая ошибка: сравнивать узел только с детьми. Дерево с корнем 10, левым ребёнком 5 и его правым ребёнком 12 пройдёт такую проверку. Но 12 лежит в левом поддереве корня 10 и нарушает правило.

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

Как найти наименьшего общего предка в дереве поиска?

В обычном дереве это отдельный алгоритм. В дереве поиска достаточно одного спуска. Оба значения меньше узла, идём влево. Оба больше, идём вправо. Иначе узел и есть предок: значения разошлись по разным сторонам.

Время O(h), памяти O(1). Это хороший пример, где правило дерева экономит целый обход.

Как найти ближайшее значение к x?

Спускаемся от корня как при поиске. На каждом узле обновляем лучшего кандидата, если он ближе к x. x меньше узла, идём влево, больше, вправо. Дошли до пустоты, кандидат и есть ответ. Один спуск, O(h).

Обход всех узлов дал бы O(n). Разница видна на дереве в миллион узлов: двадцать шагов против миллиона.

На каких ошибках ломается решение?

• Проверка только с прямыми детьми вместо границ.
• Нестрогое сравнение при дубликатах, когда условие требует строгого.
• Рекурсивная вставка в вытянутое дерево на сто тысяч узлов.
• Обход всех узлов там, где хватило бы одной ветки.

Как объяснить приём на собеседовании?

Скажите правило: слева меньше, справа больше, для каждого узла и всего поддерева. Скажите, что операции стоят O(h) и что h может быть n. Упомяните балансировку одной фразой.

Потом покажите, как правило экономит работу в конкретной задаче. Это то, что проверяют.

Отработать узнавание приёма можно на странице двоичное дерево поиска. Обходы разобраны на странице обход дерева.

Вопросы и ответы

Чем двоичное дерево поиска отличается от кучи?

В куче родитель меньше обоих детей, и всё. Куча не умеет искать, зато даёт минимум за O(1). Дерево поиска умеет искать и обходить по порядку.

Что такое сбалансированное дерево?

Дерево, где высота держится около log n. AVL и красно-чёрное дерево делают это автоматически при вставке. На собеседовании их код не просят, только идею.

Как удалить узел с двумя детьми?

Найдите минимум правого поддерева. Скопируйте его значение в узел. Удалите тот минимум, у него не больше одного ребёнка.

Где двоичное дерево поиска встречается в реальных системах?

В упорядоченных словарях: TreeMap в Java, std::map в C++. В индексах баз данных, где используют его широкую версию, B-дерево. В планировщиках задач по времени.