Spanning tree size in random binary search trees. (English) Zbl 1126.68031

Summary: 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 H. M. Mahmoud and R. Neininger [Ann. Appl. Probab. 13, No. 1, 253–276 (2003; Zbl 1033.60007)], 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 A. Panholzer and H. Prodinger [Random Struct. Algorithms 13, No. 3–4, 189–209 (1998; Zbl 0959.68513)]. 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.


68P05 Data structures
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
68P10 Searching and sorting
Full Text: DOI arXiv


[1] Dobrow, R. (1996). On the distribution of distances in recursive trees. J. Appl. Probab. 33 749–757. · Zbl 0859.05037
[2] Flajolet, Ph. and Odlyzko, A. (1990). Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216–240. · Zbl 0712.05004
[3] Greene, D. and Knuth, D. (1982). Mathematics for the Analysis of Algorithms , 2nd ed. Birkhäuser, Boston. · Zbl 1151.68750
[4] Hwang, H.-K. (1998). On convergence rates in the central limit theorems for combinatorial structures. European J. Combin. 19 329–343. · Zbl 0906.60024
[5] Janson, S. (2003). The Wiener index of simply generated random trees. Random Structures and Algorithms 22 337–358. · Zbl 1025.05021
[6] Mahmoud, H. (1992). Evolution of Random Search Trees . Wiley, New York. · Zbl 0762.68033
[7] Mahmoud, H. and Neininger, R. (2003). Distribution of distances in random binary search trees. Ann. Appl. Probab. 13 253–276. · Zbl 1033.60007
[8] Neininger, R. (2002). The Wiener index of random trees. Combin. Probab. Comput. 11 587–597. · Zbl 1013.05029
[9] Panholzer, A. and Prodinger, H. (1998). A generating functions approach for the analysis of grand averages for Multiple Quickselect. Random Structures Algorithms 13 189–209. · Zbl 0959.68513
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.