Ce este un trie (arbore de prefixe) și când este util?

Question

Accepted Answer

Un **trie** (arbore de prefixe) este un arbore unde fiecare **muchie** reprezintă un caracter și fiecare **cale de la rădăcină** formează un prefix. Cuvintele care împart un prefix împart aceeași cale, ceea ce face căutările de prefixe extrem de rapide.

## Structură

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

## Cod

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

## Complexitate

| Operație | Timp |
|---|---|
| inserare | O(L) |
| căutare | O(L) |
| interogare prefix | O(L) |

Crucial, costul depinde de **lungimea cuvântului L**, *nu* de numărul de cuvinte stocate.

## Compromisuri

- **Avantaje:** căutare rapidă de prefixe; completare automată; prefixele partajate economisesc spațiu pentru cuvinte similare.
- **Dezavantaje:** overhead mare de memorie per nod (o hartă de copii pentru fiecare); poate folosi mai mult spațiu decât un hash set pentru chei neînrudite.

## De ce contează

Trie-urile alimentează completarea automată, verificatoarele ortografice, tabelele de rutare IP și căutările pe bază de dicționar unde **potrivirea prefixelor** contează.

Când un hash set răspunde doar la "potrivire exactă", un trie răspunde în plus la "ce cuvinte încep cu X?" eficient.