Arbre ternaire de recherche

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.

Sommaire

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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre ternaire de recherche de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Content addressable memory — Mémoire adressable par contenu Pour les articles homonymes, voir CAM. La mémoire adressable par contenu (CAM, en anglais Content Addressable Memory) est un type de mémoire informatique spécial utilisé dans certaines applications de recherche à… …   Wikipédia en Français

  • Memoire adressable par contenu — Mémoire adressable par contenu Pour les articles homonymes, voir CAM. La mémoire adressable par contenu (CAM, en anglais Content Addressable Memory) est un type de mémoire informatique spécial utilisé dans certaines applications de recherche à… …   Wikipédia en Français

  • Mémoire Adressable Par Contenu — Pour les articles homonymes, voir CAM. La mémoire adressable par contenu (CAM, en anglais Content Addressable Memory) est un type de mémoire informatique spécial utilisé dans certaines applications de recherche à très haute vitesse. Elle est… …   Wikipédia en Français

  • Mémoire adressable par contenu — Pour les articles homonymes, voir CAM. La mémoire adressable par contenu (CAM, en anglais Content Addressable Memory) est un type de mémoire informatique spécial utilisé dans certaines applications de recherche à très haute vitesse. Elle est… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • ALLIAGES — Les alliages représentent une illustration matérielle du vieux dicton «l’union fait la force». L’homme a toujours cherché des matériaux plus performants à l’utilisation, plus faciles à fabriquer ou à mettre en œuvre et plus économiques. Les… …   Encyclopédie Universelle

  • FORME — L’histoire du concept de forme et des théories de la forme est des plus singulières. Nous vivons dans un monde constitué de formes naturelles. Celles ci sont omniprésentes dans notre environnement et dans les représentations que nous nous en… …   Encyclopédie Universelle

  • Daoïsme — Taoïsme 道 dào « la Voie », calligraphie 草書 cǎoshū « herbes folles », un style très libre influencé par le taoïsme. Le taoïsme (chinois: 道教, pinyin: dàojiào, « enseignement de la voie ») est à la fois une philosophie… …   Wikipédia en Français

  • Religion taoïste — Taoïsme 道 dào « la Voie », calligraphie 草書 cǎoshū « herbes folles », un style très libre influencé par le taoïsme. Le taoïsme (chinois: 道教, pinyin: dàojiào, « enseignement de la voie ») est à la fois une philosophie… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”