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

  • 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 binaire
Arbre équilibré
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
Arbres non binaires
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
  • icône décorative Portail de l'informatique théorique