Trie (mti wa kiambishi) ni nini na ni lini inapofaa?

Question

Accepted Answer

**Trie** (mti wa kiambishi) ni mti ambapo kila **makali** inawakilisha herufi na kila **njia kutoka kwenye mizizi** inaunda kiambishi. Maneno yanayoshiriki kiambishi yanashiriki njia ile ile, na hii inafanya utafutaji wa kiambishi kuwa haraka sana.

## Muundo

```text
Insert "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* marks end-of-word)
```

## Nambari

```python
class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):           # O(L), L = word length
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    def starts_with(self, prefix):    # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True
```

## Ugumu

| Operesheni | Wakati |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Muhimu, gharama inategemea **urefu wa neno L**, *si* idadi ya maneno yaliyohifadhiwa.

## Mapendeleo

- **Nguvu:** utafutaji wa kiambishi haraka; kujaza otomatiki; kiambishi kilichoshiriki huokoa nafasi kwa maneno yanayofanana.
- **Udhaifu:** matumizi makubwa ya kumbukumbu kwa kila nodi (ramani ya watoto kwa kila nodi); inaweza kutumia nafasi zaidi kuliko hash set kwa funguo zisizohusiana.

## Kwa nini inahitaji

Tries inaendesha kujaza otomatiki, wakaguzi wa hitilafu, jedwali la kusambaza IP, na utafutaji unaotegemea kamusi ambapo **kiambishi cha kulinganisha** kumbe.

Ambapo hash set inajibu tu "kulinganisha haswa," trie pia inajibu kwa haraka "ni maneno gani yanaanza na X?".