Discussion on Random Binary Search Trees

Additional notes

Random binary search trees have been studied extensively. DevroyeL. Devroye. Applications of the theory of records in the study of random trees. Acta Informatica, 26(1):123–130, 1988. gives a proof of the lemmaThe lemma is about the length of search path in a binary search tree. and related results. There are much stronger results in the literature as well, the most impressive of which is due to ReedB. Reed. The height of a random binary search tree. Journal of the ACM, 50(3):306–332, 2003., who shows that the expected height of a random binary search tree is

$$\alpha\ln n - \beta\ln\ln n + O(1)$$

where $a \approx 4.31107$ is the unique solution on the interval $[2,\infty)$ of the equation $\alpha\ln((2e/\alpha)) = 1$ ...