Digital Search Trees Again Revisited: The Internal Path Length Perspective

Authors:
  • PKPeter Kirschenhofer
    Peter Kirschenhofer
  • HPHelmut Prodinger
    Helmut Prodinger
  • WSWojciech Szpankowski
    Wojciech Szpankowski

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.

This publication has 18 references indexed in Scilit: