The Height of List-tries and TST

N. Broutin 1 L. Devroye 1
1 School of Computer Science [Montréal]
Abstract : We characterize the asymptotics of heights of the trees of de la Briandais and the ternary search trees (TST) of Bentley and Sedgewick. Our proof is based on a new analysis of the structure of tries that distinguishes the bulk of the tree, called the $\textit{core}$, and the long trees hanging down the core, called the $\textit{spaghettis}$.
Keywords : Tries branching process height de la Briandais TST
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.271-282, 2007, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01184784
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:59:35
Dernière modification le : jeudi 7 février 2019 - 16:57:26
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:16:36

Fichier

dmAH0118.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184784, version 1

Collections

INSMI | TDS-MACS

Citation

N. Broutin, L. Devroye. The Height of List-tries and TST. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.271-282, 2007, DMTCS Proceedings. 〈hal-01184784〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

231

Contact


archive-ouverte@inria.fr