Constant bounds on the moments of the height of binary search trees
We show that binary search trees of a given size tend to have smaller height when the root division is into two subtrees of more balanced sizes. We deduce that the expectation of the absolute value of the difference in height of two binary search trees of the same number of nodes is less than 3.135 infinitely often. We also deduce strong upper bounds on the probability of large deviations from the median. Putting together these two conclusions and a simple and plausible conjecture on critical nodes leads to O(1) bounds on all moments of binary search tree heights. (C) 2002 Elsevier Science B.V. All rights reserved.
height binary search tree quicksort