Digital Search Trees Again Revisited: The Internal Path Length Perspective
Authors:
- Peter KirschenhoferPKPeter Kirschenhofer
- Helmut ProdingerHPHelmut Prodinger
- Wojciech SzpankowskiWSWojciech Szpankowski
- 1 June 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (3) , 598-616
Abstract
This paper studies the asymptotics of the variance for the internal path length in a symmetric digital search tree under the Bernoulli model. This problem has been open until now. It is proved that the variance is asymptotically equal to $N \cdot 0.26600 + N \cdot \delta (\log _2 N)$, where N is the number of stored records and $\delta (x)$ is a periodic function of mean zero and a very small amplitude. This result completes a series of studies devoted to the asymptotic analysis of the variances of digital tree parameters in the symmetric case. In order to prove the previous result a number of nontrivial problems concerning analytic continuations and some others of a numerical nature had to be solved. In fact, some of these techniques are motivated by the methodology introduced in an influential paper by Flajolet and Sedgewick.
Keywords
This publication has 18 references indexed in Scilit:
- On some applications of formulae of Ramanujan in the analysis of algorithmsMathematika, 1991
- On the balance property of Patricia tries: External path length viewpointTheoretical Computer Science, 1989
- On the variance of the external path length in a symmetric digital trieDiscrete Applied Mathematics, 1989
- Ramanujan’s Notebooks1989
- A diffusion limit for a class of randomly-growing binary treesProbability Theory and Related Fields, 1988
- Further results on digital search treesTheoretical Computer Science, 1988
- Digital Search Trees RevisitedSIAM Journal on Computing, 1986
- Modular Functions and Dirichlet Series in Number Theory1976
- A note on growing binary treesDiscrete Mathematics, 1973
- File structures using hashing functionsCommunications of the ACM, 1970