Alois Panholzer: About Multiple Quickselect and the Spanning Tree Size in Binary Search Trees

This is a joint work with Helmut Prodinger (partially).

In the first part of the talk, we reconsider Multiple Quickselect, which is an algorithm that uses the idea of Quicksort to search for several order statistics simultaneously. In order to improve the efficiency of Quicksort, one can use as pivot element in the partitioning stage the median of $2t+1$ randomly chosen elements. Such a median of $2t+1$ partition can also be applied to Multiple Quickselect to reduce the number of comparisons. Here we give an analysis of such Multiple Quickselect variants, that use median of $2t+1$ partition and describe for these algorithms the asymptotic behaviour of the expected number of required comparisons to find $p$ order statistics in a data set of size $n$ for $n \to \infty$ and fixed $p$.

In the second part of the talk, we consider the size of the induced spanning subtree of $p$ randomly chosen nodes in a random binary search tree. In our analysis, we use the fact, that the ``spanning tree size'' is closely related to the number of passes in Multiple Quickselect (now we mean the ordinary algorithm not the $2t+1$ variants). This parameter, in particular its first two moments were studied earlier by Panholzer and Prodinger [PP98]. 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. For the spanning tree size, we can also show via generating functions methods, that for fixed $p$, the normalized parameter converges in law to the Normal distribution. The special case $p=2$ re-proves the recent result (obtained by Mahmoud and Neininger [MN02] using the contraction method), that the distribution of distances in random binary search trees has a Gaussian limit law.

Bibliography

MN02

Hosam M. Mahmoud and Ralph Neininger.
Distribution of distances in random binary search trees.
To appear in the Annals of Applied Probability. Paper available at http://neyman.mathematik.uni-freiburg.de/homepages/neininger/dist.ps, 2002.

PP98

Alois Panholzer and Helmut Prodinger.
A generating functions approach for the analysis of grand averages for multiple QUICKSELECT.
In Proceedings of the Eighth International Conference ``Random Structures and Algorithms'' (Poznan, 1997), volume 13, pages 189-209, 1998.

Back to the Index