Cet article est une ébauche concernant l’informatique théorique.

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

En informatique, un arbre ternaire de recherche (ATR ou TST — pour Ternary Search Tree en anglais) est une structure de données adaptée pour la recherche et combinant les avantages d'un arbre binaire de recherche et d'un arbre préfixe.

Opérations

Recherche : La recherche requiert un temps en O(k) dans tous les cas, où k est la longueur de la clef.
Insertion : La complexité de l'insertion est la même que pour la recherche : O(k) dans tous les cas, où k est la longueur de la clef.
Suppression : La complexité de la suppression est la même que pour la recherche : O(k) dans tous les cas, où k est la longueur de la clef.
Parcours ordonné :

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Variantes

Une variante statique, économe en mémoire et très rapide de l'arbre ternaire de recherche est l'arbre radix.

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 Tas binomial Tas de Fibonacci Arbre cousu

Portail de l'informatique théorique