On Robson's convergence and boundedness conjectures concerning the height of binary search trees

M Drmota - Theoretical computer science, 2004 - Elsevier
Theoretical computer science, 2004Elsevier
Let Cn denote the number of nodes in a random binary search tree (of n nodes) at the
maximal level. In this paper we present a direct proof of Robson's boundedness conjecture
saying that the expected values ECn remain bounded as n→∞. We also prove that ECn is
asymptotically (multiplicatively) periodic which shows that Robson's convergence conjecture
(that is, ECn is convergent) is only true if the limiting periodic function C˜(x) is constant.
Interestingly, it can be shown that C˜(x) is almost constant in the sense that possible …
Let Cn denote the number of nodes in a random binary search tree (of n nodes) at the maximal level. In this paper we present a direct proof of Robson's boundedness conjecture saying that the expected values ECn remain bounded as n→∞. We also prove that ECn is asymptotically (multiplicatively) periodic which shows that Robson's convergence conjecture (that is, ECn is convergent) is only true if the limiting periodic function C˜(x) is constant. Interestingly, it can be shown that C˜(x) is almost constant in the sense that possible oscillations are very small. However, it seems to be a difficult problem to decide whether C˜(x) is really constant or not. We present similar properties for the variance of the height VarHn, too.
Elsevier