X'inhu trie (prefix tree) u meta hu utli?

Question

Accepted Answer

A **trie** (prefix tree) huwa siġra fejn kull **edge** jirrapreżenta karattru u kull **path mir-root** jispelja prefiss. Kliem li jaqsmu prefiss jaqsmu l-istess path, u dan jagħmel il-lookup ta' prefissi ħafna veloċi.

## Struttura

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

## Kodiċi

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

## Kumplessità

| Operazzjoni | Ħin |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Kritikament, il-cost jiddipendi fuq **il-lungħezza tal-kelma L**, *mhux* in-numru ta' kliem maħżun.

## Trade-offs

- **Punti Qawwi:** tfittxija mhux ħerqan ta' prefiss; autocomplete; prefissi maqsuma jaħfru spazju għal kliem simili.
- **Punti Dgħajfa:** overhead ta' memorja għolja kull nodu (mappa ta' ulied għal kull wieħed); jista' juża aktar spazju minn hash set għal chiavi mhux relatati.

## Għaliex hu importanti

Tries jipprajajna autocomplete, spell-checkers, IP routing tables, u tfittxija bbażata fuq dizzjonarju fejn il-**prefiss** matching hu importanti.

Meta hash set agħti biss risposta "exact match," trie tagħti addizzjonalment risposta "x'kliem jibdew b'X?" b'mod effiċjenti.