 |
Discrete Mathematics & Theoretical Computer Science |
Margaret Archibald ; Julien Clément - Average depth in a binary search tree with repeated keys
dmtcs:3496 - Discrete Mathematics & Theoretical Computer Science, January 1, 2006, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities - https://doi.org/10.46298/dmtcs.3496Average depth in a binary search tree with repeated keysArticle
Authors: Margaret Archibald 1; Julien Clément 
2,3
- 1 School of Mathematics [Johannesburg]
- 2 Equipe AMACC - Laboratoire GREYC - UMR6072
- 3 Laboratoire d'Informatique Gaspard-Monge
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.
Source: HAL:hal-01184700v1
Volume: DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Section: Proceedings
Published on: January 1, 2006
Imported on: May 10, 2017
Keywords: Binary search trees,average case analysis,repeated keys,multiset,shuffle product,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
2 Documents citing this article
Consultation statistics
This page has been seen 266 times.
This article's PDF has been downloaded 215 times.