Arbre ternaire de recherche
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é :
Variantes
Une variante statique, économe en mémoire et très rapide de l'arbre ternaire de recherche est l'arbre radix.
Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.