Spanning tree size in Random Binary Search Trees

Details Spanning tree size in Random Binary Search Trees Spanning tree size in Random Binary Search Trees

2004-05-14

arxiv.org/abs/math/0405292v1

Annals of Applied Probability 2004, Vol. 14, No. 2, 718-733

Mathematics

Probability

Scientific paper

10.1214/105051604000000071

This paper deals with the size of the spanning tree of p randomly chosen nodes in a binary search tree. It is shown via generating functions methods, that for fixed p, the (normalized) spanning tree size converges in law to the Normal distribution. The special case p=2 reproves the recent result (obtained by the contraction method by Mahmoud and Neininger [Ann. Appl. Probab. 13 (2003) 253-276]), that the distribution of distances in random binary search trees has a Gaussian limit law. In the proof we use the fact that the spanning tree size is closely related to the number of passes in Multiple Quickselect. This parameter, in particular, its first two moments, was studied earlier by Panholzer and Prodinger [Random Structures Algorithms 13 (1998) 189-209]. Here we show also that this normalized parameter has for fixed p-order statistics a Gaussian limit law. For p=1 this gives the well-known result that the depth of a randomly selected node in a random binary search tree converges in law to the Normal distribution.

Affiliated with

Also associated with

No associations

Rating

Spanning tree size 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 Spanning tree size in Random Binary Search Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning tree size in Random Binary Search Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-671782