Czym jest binarne drzewo wyszukiwania (BST) i jakie są złożoności jego operacji?

Question

Accepted Answer

**Binarne drzewo wyszukiwania** to drzewo binarne z niezmiennikiem porządkowania: dla każdego węzła **wszystkie klucze w lewym poddrzewie są mniejsze**, a **wszystkie klucze w prawym poddrzewie są większe**. Pozwala to na wyszukiwanie poprzez zmniejszanie problemu o połowę na każdym etapie.

## 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) |

**Najgorszym przypadkiem** jest sytuacja, gdy klucze są wstawiane w posortowanej kolejności — drzewo degeneruje się w listę wiązaną o wysokości `n`.

## Trade-offs

- **Mocne strony:** przechodzenie w porządku O(n); obsługuje zapytania zakresu i operacje successor/predecessor.
- **Słabe strony:** brak gwarancji zbilansowania samodzielnie — wymaga wariantu AVL lub red-black, aby utrzymać O(log n).

## Dlaczego to ważne

BST zapewniają posortowane, dynamiczne dane z operacjami logarytmicznymi — konceptualny przodek indeksów baz danych i posortowanych map.

Problem degeneracji motywuje **self-balancing trees**, kluczowy temat uzupełniający na rozmowach kwalifikacyjnych.