DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Font Size:  Small  Medium  Large

Average depth in a binary search tree with repeated keys

Margaret Archibald, Julien Clément


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

Valid XHTML 1.0 Transitional