Trie
aus Wikipedia, der freien Enzyklopädie
In der Informatik ist ein Trie (abgeleitet aus dem engl. reTrieval, auch Prefix Tree genannt) eine Datenstruktur, genauer eine spezialisierte Art eines Suchbaumes zur gleichzeitigen Speicherung von mehreren Zeichenketten. Tries werden unter anderem verwendet, um effizient gleichzeitig nach mehreren Zeichenketten suchen zu können.
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.
[Bearbeiten] Siehe auch
[Bearbeiten] Literatur
- R. de la Briandais: File Searching Using Variable Length Keys. Proceedings of the Western Joint Computer Conference, 1959, S. 295–298
- E. Fredkin: Trie Memory. Communications of the ACM, 3(9):490-499, Sept. 1960
- Donald E. Knuth: The Art of Computer Programming. Vol. 3, 2nd ed. Boston 1998. S. 492–512.
