Arbre cousu

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En algorithmique, un arbre cousu, ou threaded tree en anglais^[1], est une structure de données, basée sur un arbre binaire.

Principe

Coudre un arbre binaire revient à :

parcourir cet arbre en parcours préfixe, postfixe ou infixe ;
dans le cadre de ce parcours, lier le fils droit de chaque feuille (originellement, il s'agit de $\varnothing$ ) à son successeur.

Il est nécessaire de matérialiser les nouvelles liaisons de manière différente des liaisons père-fils de l'arbre de départ. Dans le cas contraire, la figure ne serait plus un arbre (présence de cycles).

Types

D'une manière générale, on dénombre trois sortes d'arbre cousus :

Arbre cousu en préordre

Un arbre dont le chaînage suit un parcours préfixe de l'arbre : nœuds parents en premier, nœuds enfants ensuite.

Arbre cousu en préordre

Arbre cousu en postordre

Un arbre dont le chaînage suit un parcours postfixe de l'arbre : nœuds enfants en premier, nœuds parents en dernier.

Arbre cousu en postordre

Arbre cousu en inordre

Un arbre dont le chaînage suit un parcours infixe de l'arbre : nœud fils gauche, nœud parent, nœud fils droit.

Dans le cas d'un arbre binaire de recherche, ce chaînage correspond à une liste chaînée triée.

Historique

Le concept d'arbre cousu est dû à Joseph Morris qui le publia en 1979^[2].

Notes et références

↑ Une référence pour la traduction en français : « Cours d'algorithmique », sur polypolytech.
↑ Joseph M. Morris, « Traversing binary trees simply and cheaply », Information Processing Letters, Elsevier, vol. 9, n^o 5,‎ 1979, p. 197-200

Lien externe

K. R. Kaplan, « Threaded Search Trees », sur Université Rutgers.

v · m Arbre enraciné
Arbre binaire	Arbre binaire de recherche Arbre de fouille Arbre cartésien MVP Tree (en) Top tree (en) T-tree (en)
Arbre équilibré	AA tree (en) Arbre AVL LLRB tree (en) Arbre bicolore Arbre bouc-émissaire Arbre splay Treap
Arbre B	B*-tree (en) Bx-tree (en) UB-tree (en) 2-3 tree (en) Arbre 2-3-4 (a,b)-tree (en) Dancing tree Htree (en)
Trie	Arbre des suffixes Arbre radix Arbre ternaire de recherche X-fast trie (en) Y-fast trie (en)
Partition binaire de l'espace trees	Quadtree Octree Arbre kd (relaxé) Implicit k-d tree (en) Vp-tree
Arbres non binaires	Arbre exponentiel Fusion tree (en) arbre d'intervalles arbre PQ arbre de portée (range tree) arbre SPQR arbre de Van Emde Boas
Arbre de base de données spatiales	R-arbre R+ tree (en) R* tree (en) X-tree (en) M-tree (en) arbre de segments Hilbert R-tree (en) Priority R-tree (en)
Autres arbres	Arbre de Merkle Arbre couvrant de poids minimal Arbre syntaxique Arbre de la syntaxe abstraite Finger tree (en) Order statistic tree (en) Arbre métrique Cover tree (en) BK-tree (en) Doubly chained tree iDistance (en) Link-cut tree (en) Fenwick tree (en) Tas Binaire Binomial Fibonacci Arbre cousu