Arbre ternaire de recherche
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/44px-Max-cut.svg.png)
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bb/Ternary_Search_Tree.png/220px-Ternary_Search_Tree.png)
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é :
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Fairytale_warning.png/17px-Fairytale_warning.png)
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 binaire |
|
Arbre équilibré |
|
Arbre B |
|
Trie |
|
Partition binaire de l'espace trees | |
Arbres non binaires |
|
Arbre de base de données spatiales |
|
Autres arbres |
|
Portail de l'informatique théorique