×

The variance of the height of digital search trees. (English) Zbl 1025.68027

Summary: It is shown that the distribution of the height \(H_n\) of digital search tree is extremely concentrated. Especially it is proved that the variance \({\mathbf E}(H_n-{\mathbf E}H_n)^2\) and all centralized moments are bounded. These kinds of concentration properties are already known for trees and binary search trees. However, for digital search trees one expects much more, namely that the height is (asymptotically) concentrated at (at most) two levels. This conjecture – sometimes called Kesten’s conjecture – remains unsolved but the present results might be a first step towards its resolution.

MSC:

68P10 Searching and sorting
68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI