A note on the height of binary search trees 论文

摘要

Let H n be the height of a binary search tree with n nodes constructed by standard insertions from a random permutation of 1, … , n . It is shown that H n /log n → c = 4.31107 … in probability as n → ∞, where c is the unique solution of c log((2 e )/ c ) = 1, c ≥ 2. Also, for all p > 0, lim n →∞ E ( H p n )/ log p n = c p . Finally, it is proved that S n /log n → c * = 0.3733 … , in probability, where c * is defined by c log((2 e )/ c ) = 1, c ≤ 1, and S n is the saturation level of the same tree, that is, the number of full levels in the tree.