Trie

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Der Titel dieses Artikels ist mehrdeutig. Weitere Bedeutungen sind unter Trie (Begriffsklärung) aufgeführt.
Trie, der die Zeichenketten Java, Rad, Rand, Rau, Raum und Rose speichert

Ein Trie oder Präfixbaum ist eine Datenstruktur, die in der Informatik zum Suchen nach Zeichenketten verwendet wird. Es handelt sich dabei um einen speziellen Suchbaum zur gleichzeitigen Speicherung mehrerer Zeichenketten.

Das Wort Trie wurde von Edward Fredkin empfohlen und leitete sich aus dem englischen Ausdruck Information Retrieval ab.

In einem Trie repräsentiert jede Kante des Baums einen zusätzlichen Buchstaben. Jeder Knoten entspricht der Zeichenkette, die aus der Verkettung aller Kantenbuchstaben entsteht. Der Wurzelknoten eines Trie entspricht einer leeren Zeichenkette.

Um Daten in komprimierter Form in einem Trie abzulegen, werden Patricia-Tries benutzt.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

 Commons: Trie – Sammlung von Bildern, Videos und Audiodateien