On the number of descendants and ascendants in random search trees

We consider here the probabilistic analysis of the number of descendants and the number of ascendants of a given internal node in a random search tree. The performance of several important algorithms on search trees is closely related to these quantities. For instance, the cost of a successful search is proportional to the number of ascendants of the sought element. On the other hand, the probabilistic behavior of the number of descendants is relevant for the analysis of paged data structures and for the analysis of the performance of quicksort, when recursive calls are not made on small subfiles. We also consider the number of ascendants and descendants of a random node in a random search tree, i.e., the grand averages of the quantities mentioned above. We address these questions for standard binary search trees and for locally balanced search trees. These search trees were introduced by Poblete and Munro and are binary search trees such that each subtree of size 3 is balanced; in other words, binary search trees where there are not two adjacent internal nodes with only one son each. In this work, we follow a purely combinatorial approach, extensively using generating functions, and derive exact and asymptotic expressions for the probability distribution and moments of some of the considered quantities, finding several new results as well as alternative derivations for already known results