Wat is een trie (prefix tree) en wanneer is het nuttig?

Question

Accepted Answer

Een **trie** (prefix tree) is een boom waarin elke **edge** een karakter voorstelt en elk **pad vanaf de root** een prefix spelt. Woorden die een prefix delen, delen hetzelfde pad, wat prefix-lookups uiterst snel maakt.

## Structuur

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

## Code

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

## Complexiteit

| Operatie | Tijd |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Beslissend is dat de kosten afhangen van de **woordlengte L**, *niet* van het aantal opgeslagen woorden.

## Trade-offs

- **Sterke punten:** snelle prefix-zoeking; autocomplete; gedeelde prefixes besparen ruimte voor vergelijkbare woorden.
- **Zwakke punten:** grote geheugenoverhead per node (een child-map voor elke); kan meer ruimte gebruiken dan een hash set voor niet-gerelateerde sleutels.

## Waarom het belangrijk is

Tries voorzien autocomplete, spellcheckers, IP-routeringstabellen en woordenboekgebaseerde zoekopdrachten waarbij **prefix**-matching belangrijk is.

Where een hash set alleen "exact match" beantwoordt, beantwoordt een trie bovendien efficiënt "welke woorden beginnen met X?".