Mikä on binäärihakupuu (BST) ja mitkä ovat sen operaatioiden monimutkaisuudet?

Question

Accepted Answer

**Binäärihakupuu** on binääripuu, jolla on järjestyksen invariantti: jokaiselle solmulle **kaikki avaimet sen vasemmassa alipuussa ovat pienempiä** ja **kaikki avaimet sen oikeassa alipuussa ovat suurempia**. Tämä antaa sinulle mahdollisuuden hakea puolittamalla ongelman jokaisessa vaiheessa.

## Invariantti

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

## Haku ja lisäys

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

## Monimutkaisuus

| Operaatio | Tasapainotettu | Pahin tapaus (degeneraatio) |
|---|---|---|
| haku | O(log n) | O(n) |
| lisäys | O(log n) | O(n) |
| poisto | O(log n) | O(n) |

**Pahin tapaus** tapahtuu, kun avaimet lisätään lajitellun järjestyksen mukaan — puu degeneroi linkitetyksi listaksi, jonka korkeus on `n`.

## Kompromissit

- **Vahvuudet:** lajiteltu läpikäynti O(n) ajassa; tukee aluehakuja ja seuraaja/edeltäjä -operaatioita.
- **Heikkoudet:** ei omaa tasapainotakuuta — tarvitsee AVL- tai red-black -variantin pysyäkseen O(log n) ajassa.

## Miksi se on tärkeää

BST:t antavat sinulle lajiteltuja, dynaamisia tietoja logaritmisilla operaatioilla — käsitteellinen esi-isä tietokannan indekseille ja järjestetyille kartoille.

Degeneraatioongelma motivoi **itse tasapainottuvia puita**, tärkeää jatkokysymystä haastatteluissa.