An Analysis of Binary Search Trees Formed from Sequences of Nondistinct Keys

The expected depth of each key in the set of binary search trees formed from all sequences composed from a multiset {p1 · 1, p2 · 2, p3 · 3, ···, pn · n} is obtained, and hence the expected weight of such trees. The expected number of left-to-right local minima and the expected number of cycles in sequences composed from a multiset are then deduced from these results. © 1976, ACM. All rights reserved.