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 randomly chosen elements. Such a median of 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 partition and describe for these algorithms the asymptotic behaviour of the expected number of required comparisons to find order statistics in a data set of size for and fixed .
In the second part of the talk, we consider the size of the induced spanning subtree of 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 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 order statistics a Gaussian limit law. For 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 , the normalized parameter converges in law to the Normal distribution. The special case 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.
Back to the Index