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
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 core, and the long trees hanging down the core, called the spaghettis.
Tshering C. Dorji;El-sayed Atlam;Susumu Yata;Mahmoud Rokaya;Masao Fuketa;et al., 2009, New methods for compression of MP double array by compact management of suffixes, Information Processing & Management, 46, 5, pp. 502-513, 10.1016/j.ipm.2009.08.004.
N. BROUTIN;L. DEVROYE, 2007, An Analysis of the Height of Tries with Random Weights on the Edges, Combinatorics Probability Computing, 17, 2, pp. 161-202, 10.1017/s0963548307008796.