Profile Height of Random Binary Search Trees

The purpose of this article is to survey recent results on distributional properties of random binary search trees. In particular we consider the profile and the height.1 Introduction Probably the most widely used sorting algorithm is the algorithmQuicksort which was invented by C. A. R. Hoare [14, 15]. It is the standard sorting procedure in Unix systems, and the basic idea can be described as follows:A list of n (different) real numbers A = (x1, x2,. .. , xn) is given. Select an element (a pivot) xj from this list. Divide the remaining numbers into sets A,A> of numberssmaller (or equal) and larger than xj. Next apply the same procedure to each of these two sets if they contain more than one element. Finally, we end up with a sorted list of the original numbers.