Details
| Original language | English |
|---|---|
| Pages (from-to) | 279-297 |
| Number of pages | 19 |
| Journal | Annals of Applied Probability |
| Volume | 15 |
| Issue number | 1 A |
| Publication status | Published - Feb 2005 |
Abstract
We investigate the distribution of the depth of a node containing a specific key or, equivalently, the number of steps needed to retrieve an item stored in a randomly grown binary search tree. Using a representation in terms of mixed and compounded standard distributions, we derive approximations by Poisson and mixed Poisson distributions; these lead to asymptotic normality results. We are particularly interested in the influence of the key value on the distribution of the node depth. Methodologically our message is that the explicit representation may provide additional insight if compared to the standard approach that is based on the recursive structure of the trees. Further, in order to exhibit the influence of the key on the distributional asymptotics, a suitable choice of distance of probability distributions is important. Our results are also applicable in connection with the number of recursions needed in Hoare's [Comm. ACM 4 (1961) 321-322] selection algorithm FIND.
Keywords
- Asymptotic normality, Hoare's selection algorithm, Mixed Poisson distributions, Poisson approximation, Random permutations, Randomized algorithms
ASJC Scopus subject areas
- Mathematics(all)
- Statistics and Probability
- Decision Sciences(all)
- Statistics, Probability and Uncertainty
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Annals of Applied Probability, Vol. 15, No. 1 A, 02.2005, p. 279-297.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Mixed Poisson approximation of node depth distributions in random binary search trees
AU - Grübel, Rudolf
AU - Stefanoski, Nikolče
PY - 2005/2
Y1 - 2005/2
N2 - We investigate the distribution of the depth of a node containing a specific key or, equivalently, the number of steps needed to retrieve an item stored in a randomly grown binary search tree. Using a representation in terms of mixed and compounded standard distributions, we derive approximations by Poisson and mixed Poisson distributions; these lead to asymptotic normality results. We are particularly interested in the influence of the key value on the distribution of the node depth. Methodologically our message is that the explicit representation may provide additional insight if compared to the standard approach that is based on the recursive structure of the trees. Further, in order to exhibit the influence of the key on the distributional asymptotics, a suitable choice of distance of probability distributions is important. Our results are also applicable in connection with the number of recursions needed in Hoare's [Comm. ACM 4 (1961) 321-322] selection algorithm FIND.
AB - We investigate the distribution of the depth of a node containing a specific key or, equivalently, the number of steps needed to retrieve an item stored in a randomly grown binary search tree. Using a representation in terms of mixed and compounded standard distributions, we derive approximations by Poisson and mixed Poisson distributions; these lead to asymptotic normality results. We are particularly interested in the influence of the key value on the distribution of the node depth. Methodologically our message is that the explicit representation may provide additional insight if compared to the standard approach that is based on the recursive structure of the trees. Further, in order to exhibit the influence of the key on the distributional asymptotics, a suitable choice of distance of probability distributions is important. Our results are also applicable in connection with the number of recursions needed in Hoare's [Comm. ACM 4 (1961) 321-322] selection algorithm FIND.
KW - Asymptotic normality
KW - Hoare's selection algorithm
KW - Mixed Poisson distributions
KW - Poisson approximation
KW - Random permutations
KW - Randomized algorithms
UR - http://www.scopus.com/inward/record.url?scp=14544301012&partnerID=8YFLogxK
U2 - 10.1214/105051604000000611
DO - 10.1214/105051604000000611
M3 - Article
AN - SCOPUS:14544301012
VL - 15
SP - 279
EP - 297
JO - Annals of Applied Probability
JF - Annals of Applied Probability
SN - 1050-5164
IS - 1 A
ER -