An analytic approach to the height of binary search trees
By using analytic tools it is shown that the expected value of the height H-n of binary search trees of size n is asymptotically given by EHn = c log n + O(log log n) and its variance by VHn = O((log log n)(2)), where c = 4.31107....The same bounds have been obtained by Devroye and Reed [3] by completely different methods.
binary search tree average case analysis