Что такое бинарное дерево поиска (BST) и как в нём искать?
Изучаю деревья и дошёл до BST. Понял, что слева меньше, справа больше, но как это помогает искать быстрее? И почему в одних статьях пишут про O(log n), а в других про O(n)? От чего это зависит? Покажите, пожалуйста, код поиска, а то по тексту в голове не складывается.
2 ответа
Давай разберём, и заодно поймёшь, откуда берутся два разных O.
Бинарное дерево поиска (BST) — это дерево, где для каждого узла выполняется правило:
- все значения в левом поддереве < значения узла;
- все значения в правом поддереве > значения узла.
Именно это правило ускоряет поиск. Когда ищешь число, ты на каждом шаге сравниваешь его с текущим узлом и идёшь только в одну сторону, отбрасывая половину дерева. Это бинарный поиск, но по дереву.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def search(node, target):
while node is not None:
if target == node.value:
return node # нашли
elif target < node.value:
node = node.left # идём влево
else:
node = node.right # идём вправо
return None # не нашли
Теперь про O(log n) vs O(n). Сложность поиска = высота дерева.
- Если дерево сбалансировано (ветви примерно равной высоты), высота ≈ log₂(n), и поиск/вставка — O(log n).
- Если дерево вырожденное — например, ты вставлял уже отсортированные числа 1, 2, 3, 4, 5 — оно превращается в «бамбук», цепочку, по сути связный список. Высота = n, и поиск деградирует до O(n).
Именно поэтому существуют самобалансирующиеся деревья (AVL, красно-чёрные) — они держат высоту log n принудительно.
Бонус-факт: обход BST методом in-order (левое → узел → правое) выдаёт элементы в отсортированном порядке. Это бесплатная сортировка как побочный эффект структуры:
def in_order(node):
if node:
in_order(node.left)
print(node.value)
in_order(node.right)
Итог: BST быстр, пока сбалансирован. Без балансировки гарантий нет.
К ответу выше добавлю важную практическую мысль. В реальном коде на Python для «множества с быстрым поиском» обычно берут не самописный BST, а dict/set — они на хеш-таблице и дают O(1) в среднем.
BST выигрывает там, где нужен порядок: найти все элементы в диапазоне [a, b], найти ближайший меньший/больший, перебрать по возрастанию. Хеш-таблица так не умеет. Поэтому в БД и индексах деревья живут, а для простого «есть/нет» — хватает set.
