Kazemi, Ramin and Vahidi-Asl, Mohammad Q. - The Variance of the Profile in Digital Search Trees

dmtcs:555 - Discrete Mathematics & Theoretical Computer Science, September 16, 2011, Vol. 13 no. 3
The Variance of the Profile in Digital Search Trees

Authors: Kazemi, Ramin and Vahidi-Asl, Mohammad Q.

What today we call digital search tree (DST) is Coffman and Eve's sequence tree introduced in 1970. A digital search tree is a binary tree whose ordering of nodes is based on the values of bits in the binary representation of a node's key. In fact, a digital search tree is a digital tree in which strings (keys, words) are stored directly in internal nodes. The profile of a digital search tree is a parameter that counts the number of nodes at the same distance from the root. In this paper we concentrate on external profile, i.e., the number of external nodes at level k when n strings are sorted. By assuming that the n input strings are independent and follow a (binary) memoryless source the asymptotic behaviour of the average profile was determined by Drmota and Szpankowski (2011). The purpose of the present paper is to extend their analysis and to provide a precise analysis of variance of the profile. The main (technical) difference is that we have to deal with an inhomogeneous part in a proper functional-differential equations satisfied by the second moment and Poisson variance. However, we show that the variance is asymptotically of the same order as the expected value which implies concentration. These results are derived by methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization, the saddle point method and singularity analysis.

Source : oai:HAL:hal-00990500v1
Volume: Vol. 13 no. 3
Section: Analysis of Algorithms
Published on: September 16, 2011
Submitted on: January 31, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Browsing statistics

This page has been seen 43 times.
This article's PDF has been downloaded 59 times.