DIGITAL SEARCH-TREES AGAIN REVISITED - THE INTERNAL PATH-LENGTH PERSPECTIVE

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 . 0.26600 + N . delta(log2 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.