Arbre ternaire de recherche
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
[modifier | modifier le code]- 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
[modifier | modifier le code]Une variante statique, économe en mémoire et très rapide de l'arbre ternaire de recherche est l'arbre radix.
