Vad är en trie (prefixträd) och när är det användbart?

Question

Accepted Answer

En **trie** (prefixträd) är ett träd där varje **kant** representerar ett tecken och varje **väg från roten** bildar ett prefix. Ord som delar ett prefix delar samma väg, vilket gör prefixökning extremt snabb.

## Struktur

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

## Kod

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

## Komplexitet

| Operation | Tid |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Avslagsvis beror kostnaden på **ordens längd L**, *inte* på antalet lagrade ord.

## Avvägningar

- **Styrkor:** snabb prefixökning; autocompletion; delade prefix sparar utrymme för liknande ord.
- **Svagheter:** högt minneskostnader per nod (en barnkarta för varje nod); kan använda mer utrymme än en hash set för orelaterade nycklar.

## Varför det spelar roll

Tries driver autocompletion, stavningskontroller, IP-routingtabeller och ordlistbaserad sökning där **prefixmatchning** är viktigt.

Där en hash set bara svarar på "exakt matchning" kan en trie dessutom effektivt svara på "vilka ord börjar med X?".