The Height of List-tries and TST

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}$.
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 11 mai 2017 - 01:02:53
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

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〉

Partager

Métriques

Consultations de la notice

47

Téléchargements de fichiers

106