Kaj je binarno iskalno drevo (BST) in kakšne so kompleksnosti njegovih operacij?

Question

Accepted Answer

**Binarno iskalno drevo** je binarno drevo s pravilom urejenosti: za vsako vozlišče so **vsi ključi v levem podrevu manjši**, in **vsi ključi v desnem podrevu večji**. To vam omogoča iskanje z razpolovljanjem problema pri vsakem koraku.

## Pravilo urejenosti

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

## Iskanje in vstavljanje

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

## Kompleksnost

| Operacija | Uravnoteženo | Najslabši primer (degeneravano) |
|---|---|---|
| iskanje | O(log n) | O(n) |
| vstavljanje | O(log n) | O(n) |
| brisanje | O(log n) | O(n) |

**Najslabši primer** se pojavi, ko so ključi vstavljeni v sortiranem vrstnem redu — drevo se degenerira v povezan seznam višine `n`.

## Kompromisi

- **Prednosti:** urejena prečka v O(n); podpora poizvedbam obsegov in naslednika/predhodnika.
- **Slabosti:** ni garancije za uravnoteženost — potrebuje AVL ali red-black varianto za ohranitev O(log n).

## Zakaj je to važno

BST vam dajo sortirane, dinamične podatke z logaritemskimi operacijami — konceptualni predhodnik indeksov baz podatkov in urejenega mapiranja.

Problem degeneracije motivira **samoumesnjujoča se drevesa**, ključna nadaljnja tema pri intervjujih.

Operacija	Uravnoteženo	Najslabši primer (degeneravano)
iskanje	O(log n)	O(n)
vstavljanje	O(log n)	O(n)
brisanje	O(log n)	O(n)