Trie (informatique)
- Trie (informatique)
-
Un
trie pour les clés "A", "to", "tea", "ten", "ted", "i", "in", et "inn".
En informatique, un ou une trie[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 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[1].
Notes et références
Notes
- ↑ Le terme vient de retrievable memory, mais l'usage dans la littérature francophone est d'utiliser le masculin
- ↑ À l'origine [ˈtriː] comme dans retrievable, mais la plupart du temps [ˈtraɪ][1]
Références
- (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
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Trie (informatique) de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
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
INFORMATIQUE ET SCIENCES HUMAINES - Histoire et informatique — Les historiens utilisent l’informatique depuis quelques dizaines d’années. À partir des années 1970, après la parution de quelques livres pionniers (M. Couturier, T. K. Rabb), l’emploi de l’ordinateur pour le traitement de données historiques… … Encyclopédie Universelle
Diviser Pour Régner (Informatique) — Pour les articles homonymes, voir Diviser pour régner. Diviser pour régner est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous problèmes analogues. L étape de subdivision est appliquée récursivement … Wikipédia en Français
Diviser pour regner (informatique) — Diviser pour régner (informatique) Pour les articles homonymes, voir Diviser pour régner. Diviser pour régner est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous problèmes analogues. L étape de… … Wikipédia en Français
Diviser pour régner (informatique) — Pour les articles homonymes, voir Diviser pour régner. Diviser pour régner (divide and conquer) est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous problèmes analogues. L étape de subdivision est… … Wikipédia en Français
Moteur (informatique) — Moteur (homonymie) Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
interclassement — ● n. m. Fusion de deux ensembles distincts de données triées pour n en former plus qu un seul, trié lui aussi. Voir fusion, fusionner … Dictionnaire d'informatique francophone
Bubble Sort — Tri à bulles Exemple du tri à bulles utilisant une liste de nombres aléatoires Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus petits éléments d une liste, comme les bulles d… … Wikipédia en Français
Bubblesort — Tri à bulles Exemple du tri à bulles utilisant une liste de nombres aléatoires Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus petits éléments d une liste, comme les bulles d… … Wikipédia en Français
Tri a bulles — Tri à bulles Exemple du tri à bulles utilisant une liste de nombres aléatoires Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus petits éléments d une liste, comme les bulles d… … Wikipédia en Français
