Wat is een binary search tree (BST) en wat zijn de complexiteiten van de bewerkingen?

Question

Accepted Answer

Een **binary search tree** is een binaire boom met een ordening-invariant: voor elk knooppunt zijn **alle sleutels in de linker substructuur kleiner**, en **alle sleutels in de rechter substructuur groter**. Dit stelt je in staat om te zoeken door het probleem op elke stap te halveren.

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

Het **ergste geval** treedt op wanneer sleutels in gesorteerde volgorde worden ingevoegd — de boom ontaardt in een gekoppelde lijst van hoogte `n`.

## Trade-offs

- **Sterke punten:** gesorteerde traversal in O(n); ondersteunt bereikquery's en successor/predecessor.
- **Zwakke punten:** geen balansgarantie op zichzelf — heeft een AVL of red-black variant nodig om O(log n) te blijven.

## Waarom het belangrijk is

BST's geven je gesorteerde, dynamische gegevens met logaritmische bewerkingen — de conceptuele voorloper van database-indexen en geordende kaarten.

Het degeneratie-probleem motiveert **self-balancing trees**, een belangrijk vervolgonderwerp in interviews.