Was ist ein Trie (Präfixbaum) und wann ist er nützlich?

Question

Accepted Answer

Ein **Trie** (Präfixbaum) ist ein Baum, in dem jede **Kante** ein Zeichen darstellt und jeder **Pfad von der Wurzel** ein Präfix bildet. Wörter, die ein Präfix teilen, teilen denselben Pfad, was die Präfixsuche extrem schnell macht.

## Struktur

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

## Komplexität

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

Entscheidend ist, dass die Kosten von der **Wortlänge L** abhängen, nicht von der Anzahl der gespeicherten Wörter.

## Abwägungen

- **Stärken:** schnelle Präfixsuche; Autovervollständigung; gemeinsame Präfixe sparen Platz für ähnliche Wörter.
- **Schwächen:** hoher Speicheraufwand pro Knoten (eine Kinder-Map für jeden); kann mehr Platz als ein Hash Set für nicht verwandte Schlüssel benötigen.

## Warum es wichtig ist

Tries treiben Autovervollständigung, Rechtschreibprüfung, IP-Routingtabellen und wörterbuchbasierte Suche an, bei denen **Präfix**-Matching wichtig ist.

Während ein Hash Set nur auf "genaue Übereinstimmung?" antwortet, beantwortet ein Trie zusätzlich effizient "welche Wörter beginnen mit X?".