Apakah pokok carian binari (BST) dan apakah kompleksitas operasinya?

Question

Accepted Answer

**Pokok carian binari** ialah pokok binari dengan invarian penyusunan: untuk setiap nod, **semua kunci dalam subpokok kirinya lebih kecil**, dan **semua kunci dalam subpokok kanannya lebih besar**. Ini membolehkan anda mencari dengan mengurangkan separuh masalah pada setiap langkah.

## Mengapa ia penting

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

## Carian dan sisipan

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

## Kerumitan

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

**Kes terburuk** berlaku apabila kunci disisipkan dalam tertib terurut — pokok menjadi berubah kepada senarai terpaut dengan ketinggian `n`.

## Pertukaran

- **Kekuatan:** traversal terurut dalam O(n); menyokong pertanyaan julat dan pengganti/pendahulu.
- **Kelemahan:** tiada jaminan keseimbangan dengan sendiri — memerlukan varian AVL atau merah-hitam untuk kekal O(log n).

## Mengapa ia penting

BST memberikan anda data dinamis yang terurut dengan operasi logaritmik — nenek moyang konseptual indeks pangkalan data dan peta terurut.

Masalah berubah memotivasi **pokok yang menyeimbangkan diri**, topik susulan utama dalam temu duga.