On the number of descendants and ascendants in random search trees (Q1384587)

The paper under review focusses on two commonly used data structures in computer science, binary search trees (BSTs) and their related counterparts, locally balanced binary search trees (LBSTs) in which, after each insertion, local rebalancing is applied to any three node subtrees not in the classic parent and two children configuration. The main goal is to count the number of ascendants and descendants of a given node and of a random node in either a BST or an LBST, and this is accomplished by means of a number of theorems that assess the expected number of ascendants or descendants of the \(j\)th node of a particular type of tree. A number of other statistics, including probability distributions and moments, are also obtained. The methods employed make use of probability generating functions, differential equations, and the computer algebra package MAPLE. This work extends a great deal of previous work in the area including that of \textit{S. R. Arora} and \textit{W. T. Dent} [Randomized binary search technique, Commun. ACM 12, 77-90 (1969; Zbl 0167.45901)], \textit{P. Kirschenhofer}, \textit{H. Prodinger} and \textit{C. Martínez} [Analysis of Hoare's FIND algorithm with median-of-three partition, Random Struct. Algorithms 10, No. 1-2, 143-156 (1997; Zbl 0867.68034)], \textit{J. Lent} [Probabilistic analysis of some searching and sorting algorithms, PhD thesis, George Washington University (1996)] and \textit{P. V. Poblete} and \textit{J. I. Munro} [The analysis of a fringe heuristic for binary search trees, J. Algorithms 6, 336-350 (1985; Zbl 0576.68052)].