Trie (informatique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un tri pour les clés "A", "to", "tea", "ten", "ted", "i", "in", et "inn".

En informatique, un ou une tri[n 1] (prononcé [ˈtriː] ou [ˈtraɪ][n 2]) ou arbre préfixe est un arbre numérique ordonné qui est utilisé pour stocker une table associative où les clés sont généralement des chaînes de caractères. Contrairement à un arbre binaire de recherche, aucun nœud dans le tri ne stocke la chaîne à laquelle il est associé. C'est la position du nœud dans l'arbre qui détermine la chaîne correspondante.

Pour tout nœud, ses descendants ont en commun le même préfixe. La racine est associée à la chaîne vide. Des valeurs ne sont pas attribuées à chaque nœud, mais uniquement aux feuilles et à certains nœuds internes se trouvant à une position qui désigne l'intégralité d'une chaîne correspondant à une clé.

Le terme de tri vient de l'anglais retrieval[1].

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Le terme vient de retrievable memory, mais l'usage dans la littérature francophone est d'utiliser le masculin
  2. À l'origine [ˈtriː] comme dans retrievable, mais la plupart du temps [ˈtraɪ][1]

Références[modifier | modifier le code]

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Trie » (voir la liste des auteurs)
  • (en) Edward Fredkin (en), « Trie Memory », dans Communications of the ACM, vol. 3, n° 9, septembre 1960, p. 490-499
  1. a et b (en) trie, NIST