Ein Trie (englisch trie, von re-trie-val) ist eine Baum-Datenstruktur, die Zeichenketten nicht als ganze Objekte, sondern Zeichen für Zeichen entlang gemeinsamer Präfixe speichert. Jeder Knoten steht für ein Präfix, jedes gespeicherte Wort für einen Pfad von der Wurzel bis zu einem markierten Endknoten. Der Name wird wie try ausgesprochen, um ihn von tree zu unterscheiden – Konzept und Begriff gehen auf Untersuchungen der 1960er-Jahre zurück.
So arbeitet ein Trie
Statt mit verstehe beginnt der Baum mit v, darunter hängt ein Knoten ve, dann ver, vers und so weiter. Wörter, die sich ein Präfix teilen, teilen sich im Trie tatsächlich den Weg:
- Einfügen: Zeichen für Zeichen absteigen, fehlende Knoten anlegen, Endmarkierung setzen.
- Suchen: Zeichen für Zeichen absteigen – existiert der Pfad bis ans Ende, ist das Wort enthalten.
- Präfixsuche: Zum Präfix absteigen und alle darunter hängenden Wörter einsammeln – die Grundlage jeder Autovervollständigung.
Jede Operation kostet O(l), wobei l die Länge des Schlüssels ist – unabhängig davon, ob der Trie zehn oder zehn Millionen Wörter enthält. Der Aufwand skaliert also mit der Wortlänge, nicht mit der Datenmenge, und der Algorithmus bleibt auch bei riesigen Wörterbüchern schnell.
Typische Anwendungen
- Autovervollständigung in Suchfeldern, Editoren und Eingabemethoden.
- Rechtschreibprüfung und Wörterbücher – der Trie liefert alle Wörter zu einem Präfix in sortierter Reihenfolge.
- IP-Routing: Router wählen den längsten passenden Präfix (Longest Prefix Match) – eine direkte Trie-Anwendung.
- Textverarbeitung: Häufigkeitsanalyse, Mehrfach-Abgleich und Suchen über große Textmengen.
Abgrenzung und Varianten
- Hash-Tabelle: Liefert exakte Treffer in O(1), kann aber keine Präfixsuche und keine sortierte Reihenfolge – der Trie ist hier überlegen.
- String-Vergleich: Unsere Suchen laufen über Zeichenketten; der Array- oder Verkettete Liste-Ansatz bräuchte dagegen viele Vergleichsoperationen.
- Binärbaum: Der Trie ist ein Baum, aber kein Binärbaum – Wortschatz und Alphabet bestimmen seine Verzweigung.
- B-Baum: Für massenspeicherorientierte Indizes, etwa in Datenbanken, ist der B-Baum die bessere Wahl; für reine Wortpräfixe liegt der Trie vorn.
Als komprimierte Varianten verkürzen Radix-Baum (Patricia-Trie) und Suffix-Trie lange einsträngige Pfade und sparen so Speicher. Wer schnell nach Präfixen suchen will – vom ersten Buchstaben bis zur fertigen Vervollständigung – findet im Trie die passende Struktur.