Što je binarno stablo pretraživanja (BST) i koja su njegova operacijska složenost ?

Question

IT Interview Practice · Accepted Answer

**Binarno stablo pretraživanja** je binarno stablo s invarijantom uređenja : za svaki čvor, **svi ključevi u njegovom lijevom podstablu su manji**, a **svi ključevi u njegovom desnom podstablu su veći**. To vam omogućava pretraživanje tako što prepolovite problem na svakom koraku.

## Invarijanta

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

## Pretraživanje i umetanje

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

## Složenost

| Operacija | Uravnoteženo | Najgore (izrojeno) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

**Najgori slučaj** nastaje kada su ključevi umetnuti sortiranim redoslijedom — stablo degenerira u povezanu listu visine `n`.

## Kompromisi

- **Prednosti :** sortirani prolazak u O(n) ; podrška za upit raspona i nasljeđivač/prethodnik.
- **Nedostaci :** nema vlastitog jamstva uravnoteženosti — trebat će AVL ili red-black varijanta za zadržavanje O(log n).

## Zašto je to važno

BST vam daju sortirane, dinamičke podatke s logaritamskim operacijama — konceptualni prethodnik indeksa baze podataka i sortiranih mapa.

Problem degeneracije motivira **samobalansirajuća stabla**, ključna tema za nastavak u intervjuima.

Invarijanta

Pretraživanje i umetanje

Složenost

Kompromisi

Zašto je to važno

Povezana pitanja