Skip to Main content Skip to Navigation
Conference papers

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}$.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184784
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 4:59:35 PM
Last modification on : Thursday, June 18, 2020 - 12:32:05 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:16:36 PM

File

dmAH0118.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184784, version 1

Collections

Citation

N. Broutin, L. Devroye. The Height of List-tries and TST. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.271-282. ⟨hal-01184784⟩

Share

Metrics

Record views

71

Files downloads

741