Что такое двоичное дерево поиска (BST) и каковы сложности его операций?

Question

IT Interview Practice · Accepted Answer

**Двоичное дерево поиска** — это двоичное дерево с инвариантом упорядочения: для каждого узла **все ключи в левом поддереве меньше**, а **все ключи в правом поддереве больше**. Это позволяет выполнять поиск, разбивая задачу пополам на каждом шаге.

## 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** — ключевую дополнительную тему на собеседованиях.

The invariant

Search and insert

Complexity

Trade-offs

Почему это важно

Похожие вопросы