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 TST
Authors: N. Broutin 1; L. Devroye 1
NULL##NULL
N. Broutin;L. Devroye
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}$.
Broutin, N.; Devroye, L., 2008, An Analysis Of The Height Of Tries With Random Weights On The Edges, Combinatorics, Probability And Computing, 17, 2, pp. 161-202, 10.1017/s0963548307008796.
Broutin, N.; Devroye, L.; McLeish, E., 2008, Weighted Height Of Random Trees, Acta Informatica, 45, 4, pp. 237-277, 10.1007/s00236-008-0069-0.