\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
{\bf Conrado Mart\'{\i}nez, Alois Panholzer and Helmut Prodinger}
\medskip
\noindent
{\bf On the Number of Descendants and Ascendants in Random Search Trees}
\vskip.5cm


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{\ae} 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{\ae}, 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 
  
\noindent
   {\tt http://info.tuwien.ac.at/theoinf/abstract/abs\_120.htm}

\noindent and

\noindent
   {\tt http://www.lsi.upc.es/\~{}conrado/research/}.


\bye