Двоичное дерево поиска — это двоичное дерево с инвариантом упорядочения: для каждого узла все ключи в левом поддереве меньше, а все ключи в правом поддереве больше. Это позволяет выполнять поиск, разбивая задачу пополам на каждом шаге.
The invariant
text
8
/ \
3 10
/ \ \
1 6 14 left < node < right at every node
Search and insert
python
def search(node, key):
while node:
if key == node.val: return node
node = node.left if key < node.val else node.right # go one way
return None
def insert(node, key):
if node is None: return Node(key)
if key < node.val: node.left = insert(node.left, key)
else: node.right = insert(node.right, key)
return node
Complexity
| Operation | Balanced | Worst (degenerate) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
Наихудший случай возникает, когда ключи вставляются в отсортированном порядке — дерево вырождается в связный список высоты n.
Trade-offs
- Преимущества: обход в порядке за O(n); поддерживает запросы диапазона и операции successor/predecessor.
- Недостатки: без гарантии балансировки само по себе — требует варианта AVL или red-black, чтобы оставаться O(log n).
Почему это важно
ДСП обеспечивают отсортированные динамические данные с логарифмическими операциями — концептуального предка индексов баз данных и упорядоченных отображений.
Проблема вырождения мотивирует self-balancing trees — ключевую дополнительную тему на собеседованиях.