Trie
1094237
24350415
2007-12-26T12:39:25Z
Estirabot
308039
robot Ajoute: [[ca:Trie]]
[[Image:trie example.svg|thumb|right|250px|Un '''trie''' pour les clés "to", "tea", "ten", "i", "in", et "inn".]]
En informatique, un '''trie''' (''prefix-tree'') est un [[arbre (informatique)|arbre numérique ordonné]] qui est utilisé pour stocker une [[tableau associatif|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 ''trie'' 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 ''trie'' vient de l'anglais ''retrieval''.
{{Portail informatique}}
[[Catégorie:Structure de données]]
[[ca:Trie]]
[[cs:Trie]]
[[de:Trie]]
[[en:Trie]]
[[es:Trie]]
[[gl:Trie]]
[[ja:トライ木]]
[[pl:Drzewo trie]]
[[pt:Trie]]
[[ru:Префиксное дерево]]
[[zh:Trie]]