Drmota, Michael The variance of the height of digital search trees. (English) Zbl 1025.68027 Acta Inf. 38, No. 4, 261-276 (2002). 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. Cited in 2 Documents MSC: 68P10 Searching and sorting 68P05 Data structures Keywords:Kesten’s conjecture PDFBibTeX XMLCite \textit{M. Drmota}, Acta Inf. 38, No. 4, 261--276 (2002; Zbl 1025.68027) Full Text: DOI