Nini ni mti wa utaftaji wa jozi (BST) na ni nini usawa wa utendaji wake?

Question

Accepted Answer

**Mti wa utaftaji wa jozi** ni mti wa jozi wenye mali ya maadili: kwa kila nodi, **vitengo vyote katika upanzi wake wa kushoto ni ndogo**, na **vitengo vyote katika upanzi wake wa kulia ni kubwa**. Hii inakuruhusu kutafuta kwa kugawanya tatizo katika kila hatua.

## Mali ya maadili

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

## Utaftaji na kuingiza

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

## Usawa

| Utendaji | Sambamba | Kesi ya ajabu (iliyoharibika) |
|---|---|---|
| utaftaji | O(log n) | O(n) |
| kuingiza | O(log n) | O(n) |
| kufuta | O(log n) | O(n) |

Kesi ya **ajabu zaidi** hutokea wakati vitengo vimeingizwa kwa mpangilio uliofanywa — mti unaharibika kuwa orodha iliyounganishwa yenye urefu `n`.

## Kubadilishana

- **Nguvu:** upitaji uliofanywa vizuri katika O(n); inasaidia maswali ya eneo na mfuatano/umahuzi.
- **Uvimbe:** hakuna dhamana ya kusambamba yenyewe — inahitaji mbadala ya AVL au red-black ili kubaki O(log n).

## Kwa nini inahusu

BST zinakupatia data iliyofanywa vizuri, yenye nguvu na utendaji wa logarithmic — kiambilisho cha dhana cha faharasa za hifadhidata na ramani zilizofanywa vizuri.

Matatizo ya uharibifu yanamwesha **miti inayosambamba yenyewe**, mada muhimu inayofuata katika mahojiano.