Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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 Connect in order to contact the contributor
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

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, ⟨10.46298/dmtcs.3536⟩. ⟨hal-01184784⟩

Share

Metrics

Record views

34

Files downloads

502