Trie

Trie
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

Literatur

  • Rene de la Briandais: File Searching Using Variable Length Keys. Proceedings of the Western Joint Computer Conference, 1959, S. 295–298
  • Edward 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.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • trie — trie …   Dictionnaire des rimes

  • trié — trié …   Dictionnaire des rimes

  • trie — 1. (trie) s. f. Sorte de morue verte. ÉTYMOLOGIE    C est l anc. franç. trie, signifiant triage (voy. tri). SUPPLÉMENT AU DICTIONNAIRE 1. TRIE. Ajoutez : 2°   Action de trier le poisson, pour le vendre. Aucun trieur ni écoreur de service pour la… …   Dictionnaire de la Langue Française d'Émile Littré

  • trié — trié, ée (tri é, ée) part. passé de trier. •   La délicatesse est trop grande de ne pouvoir souffrir que des gens triés, MOL. Critique, I. •   Une partie de ces papiers déjà triés furent mis à part, J. J. ROUSS. Conf. XI. •   Cent quarante quatre …   Dictionnaire de la Langue Française d'Émile Littré

  • trie — [tʀi] n. f. ÉTYM. XVe, « élite, choix »; déverbal de trier. ❖ ♦ Rare. I (1776; « choix », av. 1589). Action de trier. ⇒ Tri. || La trie des poissons …   Encyclopédie Universelle

  • Trie — Trie, s. Trick …   Pierer's Universal-Lexikon

  • trié — Trié, [tri]ée. part …   Dictionnaire de l'Académie française

  • Trie — A trie for keys A , to , tea , ted , ten , i , in , and inn . In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search… …   Wikipedia

  • Trie — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sommaire 1 Toponyme 2 Hydronyme 3 Patronym …   Wikipédia en Français

  • Trie — Un trie es un caso especial de autómata finito determinista (S, Σ, T, s, A), que sirve para almacenar un conjunto de cadenas E en el que: Σ es el alfabeto sobre el que están definidas las cadenas; S, el conjunto de estados, cada uno de los cuales …   Wikipedia Español

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”