Hva er et binært søketre (BST) og hva er kompleksiteten for dets operasjoner?

Question

Accepted Answer

Et **binært søketre** er et binært tre med en ordningsinvariant: for hver node er **alle nøkler i venstre undertre mindre**, og **alle nøkler i høyre undertre større**. Dette lar deg søke ved å halvere problemet ved hvert trinn.

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

Det **verste tilfellet** oppstår når nøkler settes inn i sortert rekkefølge — treet degenererer til en lenket liste med høyde `n`.

## Trade-offs

- **Styrker:** ordnet traversering i O(n); støtter områdespørringer og etterfølger/forgjenger.
- **Svakheter:** ingen balansgaranti på egen hånd — trenger en AVL eller red-black variant for å forbli O(log n).

## Hvorfor det er viktig

BST-er gir deg sortert, dynamisk data med logaritmiske operasjoner — den konseptuelle stamfaren til databaseindekser og ordnede kart.

Degenerasjonsproblemet motiverer **self-balancing trees**, et sentralt oppfølgingsemne i intervjuer.