### Average depth in a binary search tree with repeated keys

*Margaret Archibald, Julien Clément*

#### Abstract

Random sequences from alphabet {1, …,r} are examined where repeated letters are allowed. Binary search trees are formed from these, and the average left-going depth of the first 1 is found. Next, the right-going depth of the first r is examined, and finally a merge (or `shuffle') operator is used to obtain the average depth of an arbitrary node, which can be expressed in terms of the left-going and right-going depths. The variance of each of these parameters is also found.

Full Text: PDF