Arbre ternaire de recherche

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

La recherche requiert un temps en O(k) dans tous les cas, où k est la longueur de la clef.

Insertion[modifier | modifier le code]

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[modifier | modifier le code]

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é[modifier | modifier le code]

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.