On the Number of Descendants and Ascendants in Random Search Trees

Abstract

The number of descendants of a node in a binary search tree (BST) is the size of the subtree having this node as a root; the number of ascendants is the number of nodes on the path connecting this node with the root. Using a purely combinatorial approach (generating functions and differential equations) we are able to extend previous results. For the number of descendants we get explicit formulæ for all moments; for the number of ascendants, which is harder, we get the variance.

A natural extension of binary search trees occurs when performing local reorganisations. Poblete and Munro have already analyzed some aspects of these locally balanced binary search trees (LBSTs). Here, we relate these structures with the performance of median–of–three Quicksort. We get as new results the variances for ascendants and descendants in this setting.

If the rank of the node itself is picked at random ("grand averages"), the corresponding parameters only depend on the size $n$. In this instance, we get all the moments for the descendants (BST and LBST), as well as the probabilities. For ascendants (LBST), we get the variance and (in principle) the higher moments, as well as the (normal) limiting distribution.

The emphasis is on explicit formulæ, and these are sometimes quite involved. Thus, in some instances, we have decided to state abridged versions in the paper and collect the long forms into an appendix that can be downloaded from the URLs

http://info.tuwien.ac.at/theoinf/abstract/abs_120.htm

and

http://www.lsi.upc.es/~conrado/research/.