Vad är ett binärt sökträd (BST) och vad är komplexiteten för dess operationer?

Question

Accepted Answer

Ett **binärt sökträd** är ett binärt träd med en ordningsinvariant: för varje nod är **alla nycklar i dess vänstra underträd mindre**, och **alla nycklar i dess högra underträd större**. Detta låter dig söka genom att halvera problemet vid varje steg.

## Invarianten

```text
        8
       / \
      3    10
     / \     \
    1   6     14     left < node < right at every node
```

## Sökning och insättning

```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
```

## Komplexitet

| Operation | Balanserat | Värsta fall (degenererat) |
|---|---|---|
| sökning | O(log n) | O(n) |
| insättning | O(log n) | O(n) |
| radering | O(log n) | O(n) |

**Värsta fall** inträffar när nycklar sätts in i sorterad ordning — trädet degenererar till en länkad lista med höjd `n`.

## Avvägningar

- **Styrkor:** ordnad traversering i O(n); stöder intervallförfrågningar och efterföljare/föregångare.
- **Svagheter:** ingen balanseringsgaranti på egen hand — behöver en AVL eller red-black-variant för att stanna på O(log n).

## Varför det spelar roll

BST:er ger dig sorterad, dynamisk data med logaritmiska operationer — den konceptuella förfadern till databasindex och ordnade kartor.

Degeneringsproblemet motiverar **själv-balanserande träd**, ett viktigt följdämne i intervjuer.

Operation	Balanserat	Värsta fall (degenererat)
sökning	O(log n)	O(n)
insättning	O(log n)	O(n)
radering	O(log n)	O(n)