The Variance of The Profile in Digital Search Trees
Ramin Kazemi, Mohammad Q Vahidi-Asl
Abstract
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.
Full Text: PDF PostScript