Abstract.
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 \(\vec{E} (H_n - \vec{E} H_n)^2\) and all centralized moments are bounded. These kinds of concentration properties are already known for tries 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: 8 November 2000 / 23 October 2001
Rights and permissions
About this article
Cite this article
Drmota, M. The variance of the height of digital search trees. Acta Informatica 38, 261–276 (2002). https://doi.org/10.1007/s236-002-8034-5
Issue Date:
DOI: https://doi.org/10.1007/s236-002-8034-5