Cos'è un trie (prefix tree) e quando è utile?

Question

Accepted Answer

Un **trie** (prefix tree) è un albero dove ogni **arco** rappresenta un carattere e ogni **percorso dalla radice** forma un prefisso. Le parole che condividono un prefisso condividono lo stesso percorso, rendendo le ricerche di prefissi estremamente veloci.

## Struttura

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

## Codice

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

## Complessità

| Operazione | Tempo |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Crucialmente, il costo dipende dalla **lunghezza della parola L**, *non* dal numero di parole memorizzate.

## Trade-off

- **Vantaggi:** ricerca di prefissi veloce; autocomplete; prefissi condivisi risparmiano spazio per parole simili.
- **Svantaggi:** overhead di memoria elevato per nodo (una mappa di figli per ogni nodo); può usare più spazio di un hash set per chiavi non correlate.

## Perché è importante

I trie alimentano l'autocomplete, i correttori ortografici, le tabelle di routing IP e la ricerca basata su dizionari dove il **matching di prefissi** è importante.

Quando un hash set risponde solo a "corrispondenza esatta", un trie risponde inoltre a "quali parole iniziano con X?" in modo efficiente.