N. Broutin ; L. Devroye - The Height of List-tries and TST

dmtcs:3536 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) - https://doi.org/10.46298/dmtcs.3536
The Height of List-tries and TSTConference paper

Authors: N. Broutin 1; L. Devroye 1

  • 1 School of Computer Science [Montréal]

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}$.

https://doi.org/10.46298/dmtcs.3536
Source: HAL:hal-01184784v1
Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
Section: Proceedings
Published on: January 1, 2007
Imported on: May 10, 2017
Keywords: Tries,branching process,height,de la Briandais,TST,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]

3 Documents citing this article

Share and export

Consultation statistics

This page has been seen 243 times.
This article's PDF has been downloaded 373 times.