Mathematics – Probability
Scientific paper
2005-03-31
Annals of Applied Probability 2005, Vol. 15, No. 1A, 279-297
Mathematics
Probability
Published at http://dx.doi.org/10.1214/105051604000000611 in the Annals of Applied Probability (http://www.imstat.org/aap/) by
Scientific paper
10.1214/105051604000000611
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.
Grübel Rudolf
Stefanoski Nikolce
No associations
LandOfFree
Mixed Poisson approximation of node depth distributions in random binary search trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Mixed Poisson approximation of node depth distributions in random binary search trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mixed Poisson approximation of node depth distributions in random binary search trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-721067