Hvad er et trie (præfikstræ) og hvornår er det nyttigt?

Question

Accepted Answer

Et **trie** (præfikstræ) er et træ, hvor hver **kant** repræsenterer et tegn, og hver **vej fra roden** danner et præfiks. Ord, der deler et præfiks, deler samme sti, hvilket gør præfikssøgning ekstremt hurtig.

## Struktur

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

## Kode

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

## Kompleksitet

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

Krucielt afhænger omkostningen af **ordlængden L**, ikke af antallet af lagrede ord.

## Afvejninger

- **Styrker:** hurtig præfikssøgning; autofuldførelse; delte præfikser sparer plads for lignende ord.
- **Svagheder:** høj hukommelsesomkostning pr. knude (et børnekort for hver); kan bruge mere plads end et hash set for ikke-relaterede nøgler.

## Hvorfor det betyder noget

Tries driver autofuldførelse, stavekontrol, IP-routingtabeller og ordbog-baseret søgning, hvor **præfiks**-matching betyder noget.

Mens et hash set kun besvarer "præcis match?", besvarer et trie effektivt "hvilke ord starter med X?".