Discrete Mathematics & Theoretical Computer Science (Jan 2006)

Average depth in a binary search tree with repeated keys

  • Margaret Archibald,
  • Julien Clément

DOI
https://doi.org/10.46298/dmtcs.3496
Journal volume & issue
Vol. DMTCS Proceedings vol. AG,..., no. Proceedings

Abstract

Read online

Random sequences from alphabet $\{1, \ldots,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.

Keywords