TrieStrukturen

TrieStrukturen, auch Tries genannt, sind Datenstrukturen zur effizienten Speicherung und Abfrage von Symbolfolgen, insbesondere von Wörtern oder Strings. Ein Trie speichert Zeichen schichtweise in Knoten, wobei jeder Knoten einen möglichen Folgezustand repräsentiert. Der Wurzelknoten steht für die leere Zeichenkette; Pfade von der Wurzel zu einem Endknoten markieren gespeicherte Wörter. Vorteile sind schnelle exakte und Prefix-Suchen, deterministische Laufzeiten und gute Skalierbarkeit für Autovervollständigung.

Standard-Tries verwenden für jeden Knoten eine Menge von Kindknoten, typischerweise als Karte aus Zeichen zu Kindknoten. Die Such- oder Einfügeoperation arbeitet Zeichen für Zeichen, wodurch die Laufzeit proportional zur Länge des Such- bzw. Einzufügenden Strings L ist. Ein Endmarker oder eine Kennzeichnung signalisiert, dass der Pfad eine vollständige Wortmarke beendet. Speicheraufwand kann hoch sein, besonders bei großen Alphabeten; er lässt sich durch Variationen reduzieren.

Varianten umfassen komprimierte Tries (z. B. Patricia-Trie oder DLB-Trie), bei denen längere Pfade mit nur einem Kind zusammengefasst werden, sowie Suffix-Tries, die alle Endungen eines Strings speichern, und Radix- bzw. Double-Array-Tries, die speichereffiziente Darstellungen verwenden. Anwendungen finden sich in Wörterbüchern, Autovervollständigung, Rechtschreibprüfungen und Routing-Tabellen.

Historisch wurden Tries in den 1950er/1960er Jahren eingeführt; der Begriff Trie leitet sich vom Retrieval ab. Seitdem haben sich zahlreiche Varianten etabliert, um Speicherbedarf und Leistungskennzahlen an konkrete Anforderungen anzupassen.