Apa itu pohon pencarian biner (BST) dan apa saja kompleksitas operasinya ?

Question

Accepted Answer

**Pohon pencarian biner** adalah pohon biner dengan invarian pemesanan : untuk setiap simpul, **semua kunci di subpohon kirinya lebih kecil**, dan **semua kunci di subpohon kanannya lebih besar**. Ini memungkinkan Anda mencari dengan membelah masalah di setiap langkah.

## Invarian

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

## Pencarian dan penyisipan

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

## Kompleksitas

| Operasi | Seimbang | Terburuk (merosot) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

**Kasus terburuk** terjadi ketika kunci disisipkan dalam urutan terurut — pohon merosot menjadi daftar tertaut dengan tinggi `n`.

## Pertukaran

- **Kekuatan :** traversal terurut dalam O(n) ; mendukung kueri rentang dan penerus/pendahulu.
- **Kelemahan :** tidak ada jaminan keseimbangan pada dirinya sendiri — memerlukan varian AVL atau red-black untuk tetap O(log n).

## Mengapa ini penting

BST memberi Anda data dinamis terurut dengan operasi logaritmik — leluhur konseptual indeks basis data dan peta terurut.

Masalah perosotan memotivasi **pohon penyeimbang diri**, topik tindak lanjut utama dalam wawancara.