On the Concentration of the Height of Binary Search Trees

摘要

The expectation of the absolute value of the difference between the heights of two random binary search trees of n nodes is less than 6.25 for infinitely many n. Given a plausible assumption, this expectation is less than 4.96 for all but a finite number of values of n.