%%%%%%%%% %%%%%%%%% Latex2e file for the paper %%%%%%%%% On the Number of Descendants and Ascendants in Random Search Trees %%%%%%%%% by C. Martinez, A. Panholzer, H. Prodinger %%%%%%%%% (26 pages) %%%%%%%%% %%%%%%%%% \documentclass[reqno,11pt]{amsart} \usepackage{epsfig} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \makeatletter \def\@theoremfont{\it} \def\slanttheorems{\def\@theoremfont{\sl}} \def\@begintheorem#1#2[#3]{% \@theoremfont\trivlist \global\setbox0=\hbox{\bf #1}\global\setbox1=\hbox{\bf #2}\item[\hskip \labelsep{\bf #1\ #2.}]} \let\@opargbegintheorem\relax \makeatother %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \slanttheorems %%%% various specific macros \newcommand{\desc}[2]{D_{#1,#2}} \newcommand{\descrnd}[1]{D_{#1}} \newcommand{\asc}[2]{A_{#1,#2}} \newcommand{\ascrnd}[1]{A_{#1}} \newcommand{\descgf}{\mathsf{D}} \newcommand{\ascgf}{\mathsf{A}} \newcommand{\descrndgf}{\overline{\descgf}} \newcommand{\ascrndgf}{\overline{\ascgf}} \newcommand{\mdesc}[3]{d^{(#1)}_{#2,#3}} \newcommand{\masc}[3]{a^{(#1)}_{#2,#3}} \newcommand{\mdescrnd}[2]{d^{(#1)}_{#2}} \newcommand{\mascrnd}[2]{a^{(#1)}_{#2}} \newcommand{\mdescgf}[1]{\avgdescgf^{(#1)}} \newcommand{\mascgf}[1]{\avgascgf^{(#1)}} \newcommand{\mdescrndgf}[1]{\avgdescrndgf^{(#1)}} \newcommand{\mascrndgf}[1]{\avgascrndgf^{(#1)}} \newcommand{\avgdesc}[2]{d_{#1,#2}} \newcommand{\avgasc}[2]{a_{#1,#2}} \newcommand{\avgdescrnd}[1]{d_{#1}} \newcommand{\avgascrnd}[1]{a_{#1}} \newcommand{\avgdescgf}{\mathcal{D}} \newcommand{\avgascgf}{\mathcal{A}} \newcommand{\avgdescrndgf}{\overline{\avgdescgf}} \newcommand{\avgascrndgf}{\overline{\avgascgf}} \newcommand{\probdescrnd}[2]{p_{#1,#2}} \newcommand{\descmedgf}{\mathsf{D}_{z}} \newcommand{\descrndmedgf}{\overline{\descgf}_{z}} \newcommand{\mdescmedgf}[1]{\avgdescmedgf^{(#1)}} \newcommand{\mdescrndmedgf}[1]{\avgdescrndmedgf^{(#1)}} \newcommand{\avgdescmedgf}{\mathcal{D}_{z}} \newcommand{\avgdescrndmedgf}{\overline{\avgdescmedgf}} \newcommand{\ascmedgf}{\mathsf{A}_{z}} \newcommand{\ascrndmedgf}{\overline{\ascgf}_{z}} \newcommand{\avgascmedgf}{\mathcal{A}_{z}} \newcommand{\avgascrndmedgf}{\overline{\avgascgf}_{z}} \newcommand{\mascmedgf}[1]{\avgascmedgf^{(#1)}} \newcommand{\randomvar}[2]{X_{#1,#2}} \newcommand{\grandrandomvar}[1]{X_{#1}} \newcommand{\gf}{\mathsf{X}} \newcommand{\grandgf}{\overline{\gf}} \newcommand{\moment}[3]{x^{(#1)}_{#2,#3}} \newcommand{\grandmoment}[2]{x^{(#1)}_{#2}} \newcommand{\mgf}[1]{\avggf^{(#1)}} \newcommand{\grandmgf}[1]{\grandavggf^{(#1)}} \newcommand{\avg}[2]{x_{#1,#2}} \newcommand{\grandavg}[1]{x_{#1}} \newcommand{\avggf}{\mathcal{X}} \newcommand{\grandavggf}{\overline{\avggf}} \newcommand{\parz}{\frac{\partial}{\partial z}} \newcommand{\parv}{\frac{\partial^s}{\partial v^s}} \newcommand{\gfz}{{\mathsf{X}_{z}}} \newcommand{\grandgfz}{{\overline{\gf}_{z}}} \newcommand{\qsmedgf}{\mathsf{C}_{z}} \newcommand{\qsmed}[2]{C_{#1,#2}} \newcommand{\bcomm}{\ensuremath{[\![}} \newcommand{\ecomm}{\ensuremath{]\!]}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\pordef}{\mathbin\overset{\text{def}}{=}} % por definicion \newcommand{\img}{\text{i}} % i = (-1)^(1/2) \newcommand{\stirfk}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} % numero de Stirling % primera especie \newcommand{\stirsk}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} % numero de Stirling % segunda especie \newcommand{\ffact}[2]{#1^{\underline{#2}}} % falling factorial \newcommand{\rfact}[2]{#1^{\overline{#2}}} % raising factorial \newcommand{\Kron}[1]{\bcomm{#1}\ecomm} % Generalizacion delta Kronecker \newcommand{\ldlm}{[} \newcommand{\rdlm}{]} \newcommand{\Res}[1]{\mathop{\textrm{Res}}\nolimits\left\ldlm#1\right\rdlm} % Residuo \newcommand{\Exp}[1]{\mathop{\mathbb{E}}\nolimits\left\ldlm#1\right\rdlm} % E(X) \newcommand{\Var}[1]{\mathop{\mathbb{V}}\nolimits\left\ldlm#1\right\rdlm} % Var(X) \newcommand{\Prob}[1]{\mathop{\mathbb{P}}\nolimits\left\ldlm#1\right\rdlm} % Prob \newcommand{\bigOh}{\mathop{\mathcal{O}}\nolimits} % O-grande \newcommand{\hypergeom}[6]{{}_{#1}#2_{#3} % \left(\left.\fracwithdelims..[0pt]{#4}{#5}\right| #6\right)} % hipergeometrica \newcommand{\almostall}{\hbox{\rlap{$_{\thinspace\forall}$}{$^{^\infty}$}}} \newcommand{\infoften}{\hbox{\rlap{$_{\thinspace\exists}$}{$^{^\infty}$}}} \providecommand{\implies}{\Longrightarrow} \renewcommand{\th}[1]{\ensuremath{#1^{\text{th}}}} \newcommand{\theoremname}{Theorem} \newcommand{\lemmaname}{Lemma} \newcommand{\corollaryname}{Corollary} \newcommand{\propositionname}{Proposition} \newcommand{\definitionname}{Definition} \newcommand{\conjecturename}{Conjecture} \newcommand{\claimname}{Claim} \newcommand{\of}{of\ } \newtheorem{theorem}{\theoremname}[section] \newtheorem{lemma}{\lemmaname}[section] \newtheorem{corollary}{\corollaryname}[section] \newtheorem{proposition}{\propositionname}[section] \newtheorem{defn}{\definitionname}[section] \newtheorem{conjecture}{\conjecturename}[section] \newtheorem{claim}{\claimname}[section] \setlength{\textwidth}{6.5in} \setlength{\textheight}{9in} \setlength{\topmargin}{0cm} \setlength{\oddsidemargin}{0cm} \setlength{\evensidemargin}{0cm} \frenchspacing \makeatletter \def\ps@headings{\ps@empty \def\@evenhead{\normalfont\scriptsize \hfil \leftmark{}{}\hfil\llap{\thepage}}% \def\@oddhead{\normalfont\scriptsize \hfil \rightmark{}{}\hfil\llap{\thepage}}% \let\@mkboth\markboth} \makeatother \pagestyle{headings} \begin{document} \title[{\sc the electronic journal of combinatorics 5 (1998), \#R20\hfill}] {On the Number of Descendants and Ascendants in Random Search Trees${}^{\ast}$} \thanks{${}^{\ast}$ This research was partly done while the third author was visiting the CRM (Centre de Recerca Matem\`atica, Institut d'Estudis Catalans). The first author was supported by the ESPRIT Long Term Research Project ALCOM~IT (contract no. 20244). The second author was supported by the FWF Project 12599-MAT. All $3$ authors are supported by the Project 16/98 of Acciones Integradas 1998/99. \newline The appendix of this paper with all the outsize expressions is downloadable from the URLs \newline \textsf{http://info.tuwien.ac.at/theoinf/abstract/abs\_120.htm} and \textsf{http://www.lsi.upc.es/\~{}conrado/research/}} \maketitle \bigskip \begin{minipage}[t]{7.5cm} \begin{center} {\large {\sc Conrado Mart\'{\i}nez}} \end{center} \medskip \begin{footnotesize} Departament de Llenguatges i Sistemes Inform\`atics, \\ Polytechnical University of Catalonia, \\ Pau Gargallo 5, E-08028 Barcelona, Spain. \\ email: \scriptsize{\texttt{Conrado.Martinez@lsi.upc.es}} \\ www: \scriptsize{\texttt{{http://www-lsi.upc.es/\~{}conrado/home.html}}} \end{footnotesize} \end{minipage} \hfill \begin{minipage}[t]{7.5cm} \begin{center} {\large {\sc Alois Panholzer}} \end{center} \medskip \begin{footnotesize} Institut f\"ur Algebra und Diskrete Mathematik, \\ Technical University of Vienna, \\ Wiedner Hauptstrasse 8--10, \\ A-1040 Vienna, Austria. \\ email: \scriptsize{\texttt{{e9125354@fbma.tuwien.ac.at}}} \end{footnotesize} \end{minipage} \bigskip \begin{center} \begin{minipage}[t]{7.5cm} \begin{center} {\large {\sc Helmut Prodinger}} \end{center} \medskip \begin{footnotesize} Institut f\"ur Algebra und Diskrete Mathematik, \\ Technical University of Vienna, \\ Wiedner Hauptstrasse 8--10, \\ A-1040 Vienna, Austria. \\ email: \scriptsize{\texttt{{Helmut.Prodinger@tuwien.ac.at}}}\\ www: \scriptsize{\texttt{{http://info.tuwien.ac.at/theoinf/proding.htm}}} \end{footnotesize} \end{minipage} \end{center} \bigskip \begin{center} {Submitted: January 7, 1997; Accepted: March 26, 1998.} \end{center} \bigskip \begin{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 formula{\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 \mbox{(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 formula{\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 \textsf{http://info.tuwien.ac.at/theoinf/abstract/abs\_120.htm} and \textsf{http://www.lsi.upc.es/\~{}conrado/research/}. \end{abstract} \vfill \noindent {\bf AMS Subject Classification.} 05A15 (primary) 05C05, 68P10 (secondary) \thispagestyle{empty} \clearpage \pagestyle{myheadings} \section{Introduction} \label{sec:introduction} \noindent\textbf{Binary search trees} are among the most important and commonly used data structures, their applications spanning a wide range of the areas of Computer Science. Standard binary search trees (BSTs, for short) are still the subject of active research, see for instance the recent articles~\cite{AraSei,RouMar96}. Deepening our knowledge about binary search trees is interesting in its own; moreover, most of this knowledge can be translated and applied to other data structures such as heap ordered trees, $k$-d-trees~\cite{FV90}, and to important algorithms like quicksort and Hoare's Find algorithm for selection (also known as quickselect)~\cite{Hoare61,Hoare62,Sedgewick,Sedgewick88}. We assume that the reader is already familiar with binary search trees and the basic algorithms to manipulate them~\cite{Knuth3,Sedgewick88,GonBae91}. Height and weight-balanced versions of the binary search trees, like AVL and red-black trees~\cite{AVL,RBT}, have been proposed and find many useful applications, since all of them guarantee good worst-case performance of both searches and updates. \bigskip \noindent\textbf{Locally balanced search trees} (LBSTs) were introduced by Bell~\cite{Bell} and Walker and Wood~\cite{WW76}, and thoroughly analyzed by Poblete and Munro in~\cite{PobMun85}. LBSTs have been proposed as an alternative to more complex balancing schemes for search trees. In these search trees, only local rebalancing is made; after each insertion, local rebalancing is applied to ensure that all subtrees of size 3 in the tree are complete\footnote{The generalization of the local rebalancing heuristic to subtree sizes larger than 3 is straightforward.}. The basic idea of the heuristic is that the construction of poorly balanced trees becomes less likely. A similar idea, namely, selecting a sample of 3 elements and taking the median of the sample as the pivot element for partitioning in algorithms like quicksort and quickselect has been shown to yield significant improvements in theory and practice~\cite{Sedgewick,KirMarPro97}. \bigskip \noindent\textbf{Random search trees,} either random BSTs or random LBSTs, are search trees built by performing $n$ random insertions into an initially empty tree~\cite{Knuth3,Mahmoud}. An insertion of a new element into a search tree of size $k$ is said to be random, if the new element falls with equal probability into any of the $k+1$ intervals defined by the $k$ keys already present in the tree (equivalently, the new element replaces any of the $k+1$ external nodes in the tree with equal probability). Random search trees can also be defined as the result of the insertion of the elements of a random permutation of $\{1,\dots,n\}$ into an initially empty tree. \bigskip \noindent\textbf{Ascendants and descendants} of the \th{j} internal node of a random search tree of size $n$ are denoted $\asc{n}{j}$ and $\desc{n}{j}$, respectively. Besides the two aforementioned random variables, we also consider other random variables: the number of descendants $\descrnd{n}$ and the number of ascendants $\ascrnd{n}$ of a randomly chosen internal node in a random search tree of size $n$. This corresponds to averaging $\desc{n}{j}$ and $\asc{n}{j}$ over $j$. We remark, that all the distributions, as well as the expectations $\Exp{X}$ and probabilities $\Prob{X}$ are induced by the creation process of the random search trees (BSTs resp.\ LBSTs). The number of descendants and the number of ascendants in random BSTs have been investigated in several previous works (\cite{AroDen,BroShu,Lyn,Lou,Lent}). The number of ascendants of a random node in a random LBST has been studied in~\cite{PobMun85,Pob93}. We define the number of descendants $\desc{n}{j}$ as the size of the subtree rooted at the \th{j} node, so we count the \th{j} node as a descendant of itself. The number of ascendants $\asc{n}{j}$ is the number of internal nodes in the path from the root of the tree to the \th{j} node, both included. It is worth mentioning the following symmetry property (which is very easy to prove) for the random variables we are going to consider.\footnote{We remark, that here and in the sequel equalities between random variables are equalities in distribution, which is often denoted by ${\stackrel{\rm d}{=}}$.} \begin{proposition} \label{prop:symmetry} For any $n>0$ and any $1\le j\le n$, \begin{gather*} \desc{n}{j} = \desc{n}{n+1-j}, \\ % \equald \asc{n}{j} = \asc{n}{n+1-j}. % \equald \end{gather*} \end{proposition} The performance of a successful search is obviously proportional to the number of ascendants of the sought internal node. The next proposition states this relation, as well as other interesting relationships that hold for both random BSTs and random LBSTs. \begin{proposition} \label{prop:tree-parameters} Consider a random search tree of size $n$ and let \begin{align*} S_{n,j} &= \text{\# of comparisons in a successful search for the \th{j} element,} \displaybreak[0] \\ S_n &= \text{\# of comparisons in a successful search for a randomly chosen element,} \displaybreak[0] \\ U_n &= \text{\# of comparisons in a unsuccessful search for a randomly chosen external node,} \displaybreak[0] \\ P_{n,j} &= \text{depth of the \th{j} element,} \displaybreak[0] \\ I_n &= \sum_{1\le j\le n}P_{n,j} = \text{internal path length,} \end{align*} Then, \begin{align*} S_{n,j} &= P_{n,j} + 1=\asc{n}{j},\\ S_n &= \ascrnd{n},\\ \Exp{U_n} &= \frac{n}{n+1}\left(1+\Exp{\ascrnd{n}}\right),\\ \Exp{I_n} &= n\left(\Exp{\ascrnd{n}}-1\right),\\ \Exp{\ascrnd{n}} &= \Exp{\descrnd{n}}. \end{align*} \end{proposition} There is also a close relationship between the performance of quickselect~\cite{Hoare61,Ifip,KirMarPro97} and the number of ascendants. \begin{proposition} \label{prop:quickselect} Let $F_{n,j}$ be the number of recursive calls made by quickselect to select the \th{j} element out of $n$ elements. Then $$F_{n,j}=\asc{n}{j}.$$ If we consider $\asc{n}{j}$ in random BSTs, then this corresponds to the selection of the pivots at random in each phase of quickselect. If we consider $\asc{n}{j}$ in random LBSTs, then the proposition applies for the variant of quickselect that uses the median of a random sample of three elements as the pivot in each partitioning phase. \end{proposition} The study of the number of descendants has applications in the context of paged trees (see for instance~\cite{Knuth3,FlaHos}). A paged binary search tree with \emph{page capacity} $b$ stores all its subtrees of size $\le b$ (possibly empty) in pages; typically, the pages reside in secondary memory and the elements within a page are not organized as search trees (see Figure~\ref{fig:paged-bst}: the pagination of the search tree at the left is indicated using dashed lines; a more ``realistic'' representation of the same tree appears at its right). Let $\mathcal{P}_n^{(b)}$ be the number of pages in a random search tree of size $n$ with page capacity $b$. It is obvious that $\mathcal{P}_n^{(b)}=\mathcal{I}_n^{(b)}+1$, where $\mathcal{I}_n^{(b)}$ is the number of internal nodes that are the root of a subtree that contains more than $b$ items. In other words, in a paged search tree, we have external nodes (\emph{pages}) that may contain up to $b$ keys; if $\mathcal{P}_n^{(b)}$ is the number of external nodes or pages in a paged search tree, then $\mathcal{I}_n^{(b)}=\mathcal{P}_n^{(b)}-1$ is the number of internal nodes in the tree, and these internal nodes are in one-to-one correspondance with the internal nodes with $>b$ descendants in the non-paged search tree. \begin{proposition} \label{prop:paged-trees} For all $n$, and for any constant $b\ge 1$, \begin{equation*} \Exp{\mathcal{P}_n^{(b)}} = n \Prob{\descrnd{n}>b} + 1. \end{equation*} \end{proposition} \begin{proof} Let $\delta_j$ be the indicator random variable for the predicate ``the \th{j} element has more than $b$ descendants.''. Then $\mathcal{I}_n^{(b)}=\sum_{1\le j\le n} \delta_j$. The proposition follows taking expectations in both sides of this equation, because of the linearity of expectations and $\Exp{\delta_j}=\Prob{\desc{n}{j}>b}$. \end{proof} %% Figure of a paged BST % \begin{figure} \begin{center} \epsfig{file=pBST.eps}%,height=5cm} \end{center} \caption{A paged binary search tree with page capacity $b=3$} \label{fig:paged-bst} \end{figure} Results about the probabilistic behavior of the number of descendants are also useful in the analysis of the performance of quicksort if recursive calls are not made on small subfiles (say, of size $\le b$). \begin{proposition} \label{prop:quicksort} Let $C_n^{(b)}$ and $R_n^{(b)}$ be the number of comparisons\footnote{We only count those made during the partitioning phases.} and the number of partitions made by quicksort to sort $n$ elements, when the recursion halts on subfiles of size $\le b$. Notice that standard quicksort corresponds to the case where $b=1$. Then \begin{align*} \Exp{R_n^{(b)}} &=n\Prob{\descrnd{n}>b},\\ \Exp{C_n^{(b)}} &=n\left(\Exp{\descrnd{n}}-1\right)- n \sum_{1 \le m \le b} (m-1) \Prob{\descrnd{n} = m}. \end{align*} The strategy for the selection of pivots is related with the type of random search trees that we consider: for BSTs, we have selection of pivots at random; for LBSTs, we have that the pivots are the medians of random samples of three elements. \end{proposition} \begin{proof} It is well known that we can associate to each particular execution of quicksort a binary search tree: the root contains the pivot element of the first stage, and the left and right subtrees are recursively built for the elements smaller and larger than the pivot, respectively. Each internal node in the search tree corresponds to a recursive call to quicksort. We will make a partitioning of a given subfile if and only if the subfile contains $>b$ elements, i.e. the corresponding internal node has $>b$ descendants, and the claim in the proposition follows. On the other hand, let $\epsilon_j$ be the number of comparisons made between the \th{j} element and other elements, during the partition where the \th{j} element was selected as a pivot. Clearly, if $\desc{n}{j}\le b$ then $\epsilon_j=0$, since no recursive call will be made that chooses the \th{j} element as a pivot. On the other hand, if $\desc{n}{j}>b$, the \th{j} element will be compared with each of its descendants (except itself) in the associated search tree. Hence, $\Exp{\epsilon_j} = \sum_{m=b+1}^{n} (m-1) \Prob{\desc{n}{j} = m}$. We need only to sum over $j$ to get the desired result. \end{proof} \bigskip \noindent\textbf{The structure of the paper} is as follows. We start with an overview of some basic facts about generating functions and, in particular, about probability generating functions (Section~\ref{sec:gfun}). In Section~\ref{sec:desc-bst} we develop the main steps of our approach, taking the analysis of the number of descendants in random BSTs as a first introductory example. We provide here alternative derivations to the results of Lent~\cite{Lent}, finding the probability that the \th{j} node in a random BST of size $n$ has $m$ descendants (Theorem~\ref{theo:prob-desc-bst}). We also find exact and asymptotic values for all ordinary moments, including the expected value and variance (Theorem~\ref{theo:mom-desc-bst}). Then we analyze the number of descendants of a random node, obtaining the probability that $\descrnd{n}=m$, as well as the moments of $\descrnd{n}$ (Theorems~\ref{theo:prob-rdesc-bst} and~\ref{theo:mom-desc-bst}). The remaining sections are devoted to the analysis of the number of ascendants and descendants in random LBSTs. In Section~\ref{sec:lbsts} we formally define LBSTs and give an equivalent characterization of the model of randomness which is more suitable to our purposes. Among our new results, in Section~\ref{sec:desc-lbst} we derive an explicit form for the generating function of the probability distribution of $\desc{n}{j}$ (Theorem~\ref{theo:pgf-desc-lbst}) and closed formul{\ae} for the average (Theorem~\ref{theo:avg-desc-lbst}) and the second factorial moment (Theorem~\ref{theo:var-desc-lbst}). Moreover, we find the probability distribution of $\descrnd{n}$ (Theorem~\ref{theo:prob-rdesc-lbst}) and all its moments (Theorem~\ref{theo:mom-rdesc-lbst}). In Section~\ref{sec:asc-lbst}, we compute $\Exp{\asc{n}{j}}$, the average number of ascendants of the \th{j} node in a random LBST of size $n$ (Theorem~\ref{theo:avg-asc-lbst}). We are also able to compute the PGF of $\ascrnd{n}$, the number of ascendants of a random node (Theorem~\ref{theo:pgf-rasc-lbst}), as well as all its moments (Theorems~\ref{theo:avg-rasc-lbst} and~\ref{theo:var-rasc-lbst}), thus extending the results of Poblete and Munro~\cite{PobMun85}. The results of previous works and the new results in this paper are summarized in Table~\ref{table:results}. Entries corresponding to new results in this paper and to alternative derivations of previous results are marked by `${}^\ast$'. \begin{table} \begin{center} % \hspace*{-2em} \begin{tabular}{@{}l|l|l|l|l|} \cline{2-5} & \multicolumn{2}{|c|}{\small{BST}} & \multicolumn{2}{|c|}{\small{LBST}} \\ \cline{2-5} & \small{Of a given node} & \small{Of a random node} & \small{Of a given node} & \small{Of a random node} \\ \hline% \vline & \small{Average~\cite{AroDen},} & \small{Probability,} & \small{Average~\cite{KirMarPro97},} & \small{Average,} \\% \vline \ \raisebox{-1.5ex}[0cm][0cm]{\small{Ascendants}} & \small{variance$^\ast$} & \small{moments, limit} & \small{variance$^\ast$} & \small{variance~\cite{PobMun85}$^\ast$,} \\% \vline & & \small{distribution~\cite{Lyn,BroShu,Lou,KirsProd}} & & \small{higher order moments,} \\% \vline & & & & \small{PGF, limit distribution$^\ast$} \\ \hline% \vline \ \raisebox{-1.5ex}[0cm][0cm]{\small{Descendants}} & \small{Probability,} & \small{Probability,} & \small{PGF, average,} & \small{Probability,} \\% \vline & \small{moments~\cite{Lent}$^\ast$} & \small{moments~\cite{Lent}$^\ast$} & \small{variance$^\ast$} & \small{moments$^\ast$} \\ \hline \end{tabular} \end{center} \caption{Summary of previous works and the results of this paper.} \label{table:results} \end{table} \section{Mathematical Preliminaries} \label{sec:gfun} We start recalling the definition of \emph{generating function}, for the reader's convenience. Given a sequence $\{a_n\}_{n\ge 0}$ its generating function $A(z)$ is the formal power series \begin{equation*} A(z) = \sum_{n\ge 0} a_n z^n. \end{equation*} As usual, $[z^n]A(z)$ denotes the coefficient of $z^n$ in $A(z)$ (the \th{n} coefficient of $A(z)$). Excellent sources of information about generating functions and their applications to combinatorics and the analysis of algorithms are~\cite{Wil90,FV90,SedgFlaj,Knuth3}. We make extensive use in this paper of probability generating functions (PGFs) as well as multivariate generating functions whose coefficients are PGFs themselves. We define them in turn. Given a discrete random variable $X$, its probability generating function $X(z)$ is \begin{equation*} X(z) = \sum_m \Prob{X = m} z^m. \end{equation*} If we assume further that $X\ge 0$ and let $p_m=\Prob{X = m}$, the PGF of the random variable $X$ is nothing but the ordinary generating function of the sequence $\{p_m\}_{m\ge 0}$. We list now a few important, although elementary, properties of PGFs. \begin{proposition} For any discrete random variable $X$, its probability generating function $X(z)$ satisfies: \begin{enumerate} \item $X(1) = 1$. \item $X'(1) = \left.\dfrac{dX}{dz}\right|_{z=1} = \Exp{X}$. \item $X^{(s)}(1) = \left.\dfrac{d^sX}{dz^s}\right|_{z=1} = \Exp{\ffact Xs}$, where $\ffact Xs$ denotes the \th{s} falling factorial of $X$, that is, $\ffact Xs=X(X-1)\dots(X-s+1)$. The quantity $\Exp{\ffact Xs}$ is customarily called the \th{s} factorial moment of the random variable $X$. Ordinary and central moments may be recovered from factorial moments quite easily. For instance, if $\mu=\Exp{X}$, the variance of $X$ is given by \begin{displaymath} \Var{X}=\Exp{(X-\mu)^2} = \Exp{\ffact{X}{2}} + \Exp{X}- \Exp{X}^2. \end{displaymath} \end{enumerate} \end{proposition} \bigskip Since we will mostly deal with families of random variables, with two ($n$ and $j$) or one ($n$) index, we will systematically work with multivariate generating functions of these families. For instance, if we were interested in the family $\{\randomvar{n}{j}\}_{1\le j\le n}$, we would introduce a generating function $\gf(z,u,v)$ in three variables, such that the coefficient of $z^nu^jv^m$ in $\gf(z,u,v)$ is the probability that $\randomvar{n}{j}$ is $m$. Thus \begin{equation} \gf(z,u,v) = \sum_{n,j,m} \Prob{\randomvar{n}{j}=m} z^n u^j v^m, \label{eq:gf} \end{equation} where the indices of summation $n$, $j$ and $m$ run in the appropriate ranges (or we assume that $\Prob{\randomvar{n}{j}=m}$ is 0 whenever $n<1$, $j<1$, $j>n$ or $m<0$). Notice that, by definition, $[z^nu^j]\gf(z,u,v)$ is the PGF of the random variable $\randomvar{n}{j}$, and $[z^nu^jv^m]\gf(z,u,v)=\Prob{\randomvar{n}{j}=m}$. For technical reasons that will be clearer later, we will also use sometimes the derivative w.r.t. $z$ of such a multivariate generating function. We will introduce then \begin{align*} \gfz(z,u,v) &= \parz\sum_{n,j,m} \Prob{\randomvar{n}{j}=m}z^n u^j v^m \\ &= \sum_{n,j,m} n\Prob{\randomvar{n}{j}=m}z^{n-1} u^j v^m \end{align*} rather than the more natural definition given in Equation~\eqref{eq:gf}. This means that once we were able to extract coefficients from such a generating function, let us say the coefficient of $z^{n-1}u^jv^m$, we must divide by $n$ to obtain $\Prob{\randomvar{n}{j}=m}$. Furthermore, we are also interested in investigating all the moments of the random variables: mean, variance, and higher order moments. We differentiate the generating function $\gf(z,u,v)$ $s$~times with respect to $v$ and let $v=1$, to get the generating function for the \th{s} factorial moments, i.e. \begin{equation} \mgf{s}(z,u) = \left.\frac{\partial^s \gf(z,u,v)}{\partial v^s}\right|_{v=1}, \qquad s\ge 1. \label{eq:mgf} \end{equation} Recall that $[z^nu^j]\mgf{s}(z,u)=\Exp{\ffact{\randomvar{n}{j}}{s}}$. Grand averages correspond to the situation where the \emph{rank} ---the parameter $j$ in $\randomvar{n}{j}$--- is random itself. More precisely, let $\grandrandomvar{n}\equiv\randomvar{n}{Z_n}$, where $Z_n$ is a uniformly distributed random variable in $\{1,\dots,n\}$. Then $\grandrandomvar{n}$ is the grand average of the random variables $\randomvar{n}{1},\dots,\randomvar{n}{n}$. It follows that \begin{equation} \Prob{\grandrandomvar{n}=m}= \frac 1n\sum_{1\le j\le n}\Prob{\randomvar{n}{j}=m}. \label{eq:grand-average} \end{equation} We remark that $\grandrandomvar{n} \not= \frac{1}{n}\left(\randomvar{n}{1} + \cdots + \randomvar{n}{n}\right)$, even if the $\randomvar{n}{j}$'s are independent. Unless we are dealing with a differentiated version of the generating function $\gf(z,u,v)$, we have \begin{equation} \grandgf(z,v)= \gf(z,1,v) = \sum_{n,m} z^nv^m \sum_{1\le j\le n} \Prob{\randomvar{n}{j}=m}. \label{eq:ga-gf} \end{equation} Thus the coefficient $[z^nv^m]\grandgf(z,v)$, divided by $n$, is the probability that $\grandrandomvar{n}$ is $m$. In the case that $\gfz(z,u,v)$ were a differentiated generating function, then we should divide the coefficient $[z^{n-1}v^m]\grandgfz(z,v)$ by $n^2$. Finally, computing the derivatives of $\gf(z,v)$ w.r.t. $v$ and setting $v=1$ yields the generating functions for the factorial moments of the grand average $\grandrandomvar{n}$. \bigskip The main steps of the systematic procedure that we will follow are thus: \begin{enumerate} \item Set up a recurrence for $\Prob{\randomvar{n}{j}=m}$; \item Translate the recurrence to a functional equation over the corresponding generating function $\gf(z,u,v)$; \item Solve the functional equation; \item Extract the coefficients of $\gf(z,u,v)$; \item Repeatedly differentiate $\gf(z,u,v)$ w.r.t. $v$ and set $v=1$; extract the coefficients to get the factorial moments of $\randomvar{n}{j}$; \item Set $\grandgf(z,v)=\gf(z,1,v)$ and repeat steps 4 and 5 for $\grandgf(z,v)$. \end{enumerate} In practice, the procedure might fail for several reasons. Typically, because we are not able to solve the equation at step 3 or to extract the coefficients of a given generating function. Although we have (almost) not used them in this paper, the reader should be aware of the existing powerful techniques to extract asymptotic information about the coefficients of a generating function if we know its behaviour near its singularities or in some case, even if we only know the functional equation satisfied by the generating function~\cite{FV90,FlOd90}. Also, if we are not able to solve and get an explicit form for $\gf(z,u,v)$, we can still differentiate w.r.t. to $v$ or set $u=1$ and try to solve the (easier) resulting differential equations, to get information about the moments or the grand average. The functional equations that arise in our study are linear partial differential equations of the first (BSTs) and of the second (LBSTs) order. The former can be solved, in principle, by quadrature through the variation of constant ---actually, functions in $u$ and $v$--- method. For the second order differential equations, the theory of hypergeometric differential equations comes into play~\cite{Kam77}. Nowadays, most of the necessary mathematical knowledge is embodied into modern computer algebra systems. In our case, \textsc{Maple} needed little or no assistance to solve the differential equations that we had. The last step, that of extracting coefficients in exact form, was, at large, the least systematic and mechanical one. A great deal of combinatorial identities, inspired guessing and patience was needed. Standard \textsc{Maple} tools like the function \textsf{interp} or the \textsc{Gfun} package~\cite{SalZim} proved also to be useful. However, once the solution is obtained, it is just a matter of minutes to check its correctness. It is quite difficult to provide a detailed and ordered description of the methods that we used to extract coefficients from generating functions. As a result, the paper contains only some hints here and there, while some claims are just stated without further explanation. \section{The number of descendants in random BSTs} \label{sec:desc-bst} The number of the descendants $\desc{n}{j}$ of the \th{j} node of a BST of size $n$ is recursively computed as the number of descendants in the left subtree of the \th{j} node, plus the number of descendants in its right subtree, plus one (to count the \th{j} node itself). The probability that $\desc{n}{j}=m$ is computed conditioning on the events ``the rank of the root is $k$,'' that means the root is the $k^{th}$ node of a search tree. Recall that, for a random BST of size $n$, the rank of the root is $k$ with probability $1/n$, for $k=1,\dots,n$. Using the recursive definition of $\desc{n}{j}$ we have \begin{align} \Prob{\desc{n}{j}=m} &= \sum_{k=1}^{n}\Prob{\desc{n}{j}=m \,|\, \text{the root is the \th{k} element}} \notag \\ & \qquad\times \Prob{\text{the root is the \th{k} element}} \notag \\ &= \frac1n\Kron{m=n}+ \frac1n\sum_{k=1}^{j-1}\Prob{\desc{n-k}{j-k}=m} +\frac1n\sum_{k=j+1}^{n}\Prob{\desc{k-1}{j}=m}, \label{eq:rec-prob-desc-bst} \end{align} where $\Kron{P}$ is 1 if $P$ is true and 0 otherwise~\cite{GraKnuPat}. This recursion translates nicely into a functional equation over the generating function for the family of random variables $\{\desc{n}{j}\}$. Solving the functional equation and extracting coefficients of the generating function, we get the following theorem, which was already found by Lent~\cite{Lent} using probabilistic techniques. \begin{theorem} \label{theo:prob-desc-bst} The probability that the \th{j} internal node of a random binary search tree of size $n$ has $m$ descendants is, assuming that $j \le n+1-j$, \begin{align*} \Prob{\desc{n}{j}=m} &= \begin{cases} \dfrac{2}{(m+1)(m+2)} & \text{for $1\le m < j$,} \\[2mm] \dfrac{1}{(m+1)(m+2)}\left(1+\frac{2j}{m}\right) & \text{for $j \le m < n+1-j$,} \\[2mm] \dfrac{2(n+1)}{m(m+1)(m+2)} & \text{for $n+1-j \le m < n$,} \\[2mm] \dfrac1n & \text{for $m=n$.} \end{cases} \end{align*} For the cases where $j > n+1-j$ we can use the symmetry on $j$ and $n+1-j$ (Proposition~\ref{prop:symmetry}) to compute the corresponding probabilities. Also, the distribution function for $\desc{n}{j}$ is \begin{equation*} \Prob{\desc{n}{j} \le m} = \begin{cases} \dfrac{m}{m+2} & \text{for $1\le m < j$,} \\[2mm] \dfrac{m+1}{m+2}-\dfrac{j}{(m+1)(m+2)} & \text{for $j \le m< n+1 -j$,}\\[2mm] \dfrac{m^2+3m+1-n}{(m+1)(m+2)} & \text{for $n+1-j\le m < n$,} \\[2mm] 1 & \text{for $m=n$.} \end{cases} \end{equation*} \end{theorem} \begin{proof} We start defining the generating function \begin{equation*} \descgf(z,u,v) = \sum_{1\le j,m\le n} \Prob{\desc{n}{j} = m} z^nu^jv^m. \end{equation*} Multiplying both sides of~\eqref{eq:rec-prob-desc-bst} by $nz^{n-1}u^jv^m$ and summing for all $n\ge1$, $1\le j\le n$ and $m\ge1$, yields \begin{gather} \frac{\partial\descgf}{\partial z} = \frac{u\descgf}{1-uz}+\frac{\descgf}{1-z}+\frac{uv}{(1-vz)(1-uvz)}, \notag\\ \descgf(0,u,v) = 0. \label{eq:deq-desc-bst} \end{gather} The solution to the differential equation above is relatively simple \begin{align} \descgf(z,u,v) &= \frac{uz}{v(1-z)(1-uz)}\nonumber\\ &-\frac{u(1-v)(v-u)}{(1-z)(1-uz)v^2(1-u)}\log\frac{1}{1-vz}\nonumber\\ &-\frac{(1-v)(1-uv)}{(1-z)(1-uz)v^2(1-u)}\log\frac{1}{1-uvz}. \label{eq:sol-desc-bst} \end{align} The statement of the theorem follows after extracting the coefficient $[z^nu^jv^m]\descgf(z,u,v)$. \end{proof} The explicit and simple form of the trivariate generating function in Theorem~\ref{theo:prob-desc-bst} allows us to compute all the moments \textsl{explicitly}. It is convenient to deal with a sort of shifted factorial moments; the ordinary moments can be computed by linear combinations of the shifted factorial ones. \begin{theorem} \label{theo:mom-desc-bst} Let $\mdesc{s}{n}{j}=\Exp{\ffact{\left(\desc{n}{j}+2\right)}{s}}$ and $\avgdesc{n}{j}=\mdesc{1}{n}{j}$, where $\desc{n}{j}$ denotes the number of descendants of the \th{j} internal node in a random binary search tree of size $n$. For all $n>0$ and all $1\le j\le n$, \begin{enumerate} \item $\avgdesc{n}{j}= H_j+H_{n+1-j}+1$, \item $\mdesc{2}{n}{j}= 2(n+1)H_n-2jH_j-2(n+1-j)H_{n+1-j}+2(n+2)$. \item For all $s\ge 3$, \begin{equation*} \mdesc{s}{n}{j}= \frac s{s-2}\ffact{(n+1)}{s-1} -\frac s{(s-1)(s-2)}\bigg[\ffact j{s-1} +\ffact{(n+1-j)}{s-1}\bigg]. \end{equation*} \end{enumerate} \end{theorem} \begin{proof} We begin by introducing \begin{equation*} \mdescgf{s}(z,u) = \left.\frac{\partial^s(v^2\descgf(z,u,v))}{\partial v^s}\right|_{v=1}, \end{equation*} and hence its coefficients are \begin{equation*} \mdesc{s}{n}{j} = [z^nu^j]\mdescgf{s}(z,u) = \Exp{\ffact{(\desc{n}{j}+2)}{s}}. \end{equation*} The shifted moments are particularly easy to obtain, since the coefficients of $\mdescgf{s}(z,u)$ that we seek are linear combinations of the coefficients of the next generating functions: \begin{align*} \parv \log\frac1{1-vz}\Big|_{v=1}&=(s-1)!\left(\frac{z}{1-z} \right)^{s}, \displaybreak[0]\\ \parv v\log\frac1{1-vz}\Big|_{v=1}&=(s-1)!\left(\frac{z}{1-z} \right)^{s} +s(s-2)!\left(\frac{z}{1-z}\right)^{s-1}, \displaybreak[0]\\ \parv v^2\log\frac1{1-vz}\Big|_{v=1}&=(s-1)!\left(\frac{z}{1-z} \right)^{s} +2s(s-2)!\left(\frac{z}{1-z}\right)^{s-1} \displaybreak[0] \\ & {} +s(s-1)(s-3)!\left(\frac{z}{1-z}\right)^{s-2}, \displaybreak[0]\\ \parv \log\frac1{1-uvz}\Big|_{v=1}&=(s-1)!\left(\frac{uz}{1-uz} \right)^{s}, \displaybreak[0]\\ \parv v\log\frac1{1-uvz}\Big|_{v=1}&=(s-1)!\left(\frac{uz}{1-uz }\right)^{s} +s(s-2)!\left(\frac{uz}{1-z}\right)^{s-1}, \displaybreak[0]\\ \parv v^2\log\frac1{1-uvz}\Big|_{v=1}&=(s-1)!\left(\frac{uz}{1- uz}\right)^{s} +2s(s-2)!\left(\frac{uz}{1-uz}\right)^{s-1} \displaybreak[0] \\ & {} +s(s-1)(s-3)!\left(\frac{uz}{1-uz}\right)^{s-2}. \end{align*} We might additionally observe that for all $n \ge 0$ and $1 \le j \le n$ \begin{align*} [z^nu^j]\frac{1}{(1-z)^{s+1}(1-uz)(1-u)}&=\binom{s+n+1}{s+1} - \binom{s+n-j}{s+1},\\ [z^nu^j]\frac{1}{(1-z)(1-uz)^{s+1}(1-u)}&=\binom{s+j+1}{s+1}, \quad\text{and}\\ [z^nu^j]\frac{1}{(1-z)^2(1-uz)^{2}}&=(j+1)(n+1-j). \end{align*} Theorem~\ref{theo:mom-desc-bst} is an immediate consequence of the formul{\ae} above. \end{proof} \begin{corollary} \label{cor:expvar-desc-bst} The expected value and variance of $\desc{n}{j}$ are, respectively, \begin{align*} \Exp{\desc{n}{j}} &= H_j+H_{n+1-j}-1, \\ \Var{\desc{n}{j}} &= 2(n+1)H_n-(2j+1)H_j-(2n-2j+3)H_{n+1-j}\\ &+ 2(n+2)-H_j^2-H^2_{n+1-j}-2H_jH_{n+1-j}. \end{align*} Furthermore, for $j = \alpha n$, with $0 < \alpha < 1$, we have \begin{align*} \Exp{\desc{n}{\alpha n}} &= 2\log n+\log\alpha+\log(1-\alpha)+2\gamma-1+o(1),\\ \Var{\desc{n}{\alpha n}} &= 2n\Big(1-\alpha\log\alpha -(1-\alpha)\log(1-\alpha) \Big) + \bigOh(\log^{2} n), \end{align*} where $\gamma=0.5772156649\dots$ is Euler's constant. \end{corollary} To recover higher order ordinary moments, we only need to express the ordinary powers as linear combinations of the shifted falling factorials with coefficients $\lambda_{s,k}$. Thus $$ x^s=\sum_{k=0}^s\lambda_{s,k}\ffact{(x+2)}{k}.$$ It is easy to show that $$ \lambda_{s,k}=\sum_{i=k}^s \stirsk{i}{k}\binom si (-2)^{s-i}, $$ where $\stirsk{i}{k}$ denote Stirling numbers of the second kind. The coefficients $\lambda_{s,k}$ satisfy a recursion that is similar to that of the Stirling numbers $$ \lambda_{s+1,k}=\lambda_{s,k-1}+(k-2)\lambda_{s,k}, $$ and $\lambda_{s,0}=(-2)^s$. \bigskip Let us consider now $\descrnd{n}$, the number of descendants of a random node in a random BST of size $n$. The following two theorems give closed formul{\ae} for the probability that $\descrnd{n}$ is $m$ and for the shifted factorial moments of $\descrnd{n}$, i.e. for $\mdescrnd{s}{n}=\Exp{\ffact{\left(\descrnd{n}+2\right)}{s}}$. \begin{theorem} The probability that a randomly chosen internal node in a random binary search tree of size $n$ has $m$ descendants is given by $$ \Prob{\descrnd{n} = m} = \begin{cases} \dfrac{2(n+1)}{n(m+1)(m+2)} & \text{for $1\le m < n$,} \\[2mm] \dfrac 1n & \text{for $m=n$}. \end{cases} $$ \label{theo:prob-rdesc-bst} \end{theorem} \begin{proof} Plug $u=1$ into the solution of~\eqref{eq:sol-desc-bst} to get \begin{equation} \descrndgf(z,v)= \descgf(z,1,v) = -\frac{2(1-v)}{v^2(1-z)^2}\log\frac{1}{1-vz} - \frac{z(zv-v^{2}+2v-2)}{v(1-vz)(1-z)^{2}}. \label{eq:sol-rdesc-bst} \end{equation} The coefficient of $[z^nv^m]\descrndgf(z,v)$, divided by $n$, is the sought probability. \end{proof} \begin{theorem} \label{theo:mom-rdesc-bst} The \th{s} shifted factorial moment $\mdescrnd{s}{n}=\Exp{\ffact{\left(\descrnd{n}+2\right)}{s}}$ of the number of descendants of a random node in a random binary search tree of size $n$ is given by \begin{enumerate} \item $\avgdescrnd{n} = \mdescrnd{1}{n} = 2(1+\frac 1n)H_n-1$, \item $\mdescrnd{2}{n} = 3(n+1)$. \item For all $s\ge 3$, $$ \mdescrnd{s}{n} = \frac1n\left(\ffact{(n+2)}{s}+\frac{2}{s-1}\ffact{(n+1)}{s}\right) \sim \frac{s+1}{s-1}n^{s-1}. $$ \end{enumerate} \end{theorem} \begin{proof} Repeated differentiation of the generating function $v^2\descrndgf(z,v)$ w.r.t. $v$ and setting $v=1$, gives us the generating functions of the shifted factorial moments. Their coefficients are extracted much in the same way as in Theorem~\ref{theo:mom-desc-bst}. \end{proof} A few comments concerning the last theorem are in order now. Observe that for $s\ge3$ $$ \frac1n\sum_{j=1}^n\mdesc{s}{n}{j}= \frac{\ffact{(n+1)}{s-1}}{s-1}\bigg(s+1 +\frac{2}{n}\bigg). $$ Asymptotically, this quantity is $$ \sim \frac{s+1}{s-1}n^{s-1}, $$ one of the observations in the work of Lent~\cite{Lent}. The coincidence in asymptotic behavior with $\mdescrnd{s}{n}$ is remarkable; recall that in general \begin{equation*} \Exp{\descrnd{n}^s} \not= \Exp{\bigg(\frac 1n\sum_{1\le j\le n}\desc{n}{j}\bigg)^s}, \end{equation*} except when $s=1$ and the same observation holds for the shifted factorial moments we were dealing with. Last, but not least, we can obtain the following corollaries, from Propositions~\ref{prop:paged-trees} and~\ref{prop:quicksort} and the theorems in this section. These results can already be found in~\cite{Knuth3}, although there is a slight difference in $\Exp{C_n^{(b)}}$, because $n+1$ comparisons per partition are counted there, while we count $n-1$ comparison per partition. \begin{corollary} The expected number of pages in a random binary search tree of size $n$ with page capacity $b$ is \begin{equation*} \Exp{\mathcal{P}_n^{(b)}} = 2\frac{n+1}{b+2}. \end{equation*} The \emph{filling ratio} for binary search trees is thus \begin{equation*} \gamma_b = \frac{n/b}{\Exp{\mathcal{P}_n^{(b)}}} \sim \frac{1}{2}. \end{equation*} \end{corollary} \begin{corollary} The expected number of recursive calls to sort a random permutation of size $n$, when the recursion stops in subfiles of size $\le b$ is \begin{equation*} \Exp{R_n^{(b)}} = \frac{2n-b}{b+2}. \end{equation*} Also, the expected number of comparisons to sort a random permutation of size $n$, when the recursion stops in subfiles of size $\le b$ is \begin{equation*} \Exp{C_n^{(b)}} = 2(n+1)\left(H_n-H_{b+1}\right)+n+5-\frac{6(n+1)}{b+2} . \end{equation*} \end{corollary} \section{The number of ascendants in random BSTs} Considering the element $k$ of the root of a BST, we obtain for the number of ascendants $\asc{n}{j}$ of the \th{j} node of a BST of size $n$ the following recursion: \begin{align} \Prob{\asc{n}{j}=m} &= \frac1n\Kron{m=1}+ \frac1n\sum_{k=1}^{j-1}\Prob{\asc{n-k}{j-k}=m-1} +\frac1n\sum_{k=j+1}^{n}\Prob{\asc{k-1}{j}=m-1}. \label{eq:rec-prob-asc-bst} \end{align} Introducing the generating function for the family of random variables $\{\asc{n}{j}\}$ \begin{equation*} \ascgf(z,u,v) = \sum_{1\le j,m\le n} \Prob{\asc{n}{j} = m} z^nu^jv^m, \end{equation*} this recursion translates by multiplying both sides by $nz^{n-1}u^jv^m$ and summing for all $n\ge1$, $1\le j\le n$ and $m\ge1$ into the following differential equation: \begin{equation*} \frac{\partial\ascgf}{\partial z} = \frac{v}{1-z} \ascgf + \frac{uv}{1-uz} \ascgf + \frac{uv}{(1-z)(1-uz)} \end{equation*} with the initial condition $\ascgf(0,u,v) = 0$. This differential equation has the following solution \begin{equation} \ascgf(z,u,v) = \frac{uv}{(1-z)^{v} (1-uz)^{v}} \int_{0}^{z} (1-t)^{v-1} (1-ut)^{v-1} dt . \label{sol:asc-bst} \end{equation} Starting with this generating function, it is easy to get the following theorems. At first we obtain an old result from \cite{AroDen}: \begin{theorem} The expected number of ascendants $\avgasc{n}{j}=\Exp{\asc{n}{j}}$ of the \th{j} node in a random binary search tree of size $n$ is \begin{align*} \avgasc{n}{j} &= H_{j} + H_{n+1-j} - 1 . \end{align*} \end{theorem} \begin{proof} Starting with \eqref{sol:asc-bst}, taking derivatives w.r.t. $v$ and setting $v=1$, we get the generating function $\avgascgf(z,u)$, whose coefficients are the expected values $\avgasc{n}{j}=\Exp{\asc{n}{j}}$. It is given by \begin{equation*} \avgascgf(z,u) = \frac{u}{(1-z)(1-uz)} \log\frac{1}{1-z} + \frac{1}{(1-z)(1-uz)} \log\frac{1}{1-uz} - \frac{uz}{(1-z)(1-uz)} . \end{equation*} It is easy to extract the coefficients of this expression, which leads immediately to the stated theorem. \end{proof} \begin{theorem} The second factorial moment $\masc{2}{n}{j}=\Exp{\ffact{\left(\asc{n}{j}\right)}{2}}$ of the number of ascendants of the \th{j} node in a random binary search tree of size $n$ is \begin{equation}\begin{split} \masc{2}{n}{j} &= {\frac {2 \left (n+1\right )}{\left (n+1-j\right )j}} H_{n} + H_{j}^{2}+2H_{j}H_{n+1-j}+{\frac {2\left (-nj-n+{j}^{2}-j-1\right )} {\left (n+1-j\right )j}} H_{j} + H_{n+1-j}^{2} \\ & \quad {} + {\frac {2\left (-nj- n+{j}^{2}-j-1\right )}{\left (n+1-j\right )j}} H_{n+1-j} -H_{j}^{(2)} - H_{n+1-j}^{(2)} - {\frac {2 (-2\,nj+2\,{j}^{2}-2\,j-1)}{\left (n+1-j\right )j}} \, . \end{split}\end{equation} \end{theorem} \begin{proof} Differentiating equation \eqref{sol:asc-bst} two times w.r.t. $v$ and setting $v=1$ gives the generating function $\mascgf{2}(z,u)$ of the second factorial moments $\masc{2}{n}{j}$ of the number of ascendants: \begin{align*} \mascgf{2}(z,u) & = -{\frac {2zu}{\left (1-uz\right )\left (1-z\right )}} \log\frac{1}{1-uz}-{\frac {2zu}{\left (1-uz\right )\left (1-z\right )}} \log\frac{1}{1-z} \displaybreak[0] \\ & \quad {} -{\frac {2 \left (uz-u-1\right )} {\left (1-uz\right )\left (1-z\right )}} \log\frac{1}{1-z}\log\frac{1}{1-uz} + {\frac{u}{\left (1-uz\right )\left (1-z\right )}} \log^{2}\frac{1}{1-z} \displaybreak[0] \\ & \quad {} + {\frac {1}{\left (1-uz \right )\left (1-z\right )}} \log^{2}\frac{1}{1-uz} + {\frac {2 u}{\left (1-uz\right ) \left (1-z\right )}} \int _{0}^{z} \log\frac{1}{1-t} \log\frac{1}{1-ut} {dt} . \end{align*} Extracting the coefficients leads to the given theorem. Since one expression in $\mascgf{2}(z,u)$ turns out to be a bit messier, we sketch how to extract the coefficients of it. First we get the following sum \begin{align*} & [z^{n}u^{j}] \frac{1}{(1-z)(1-uz)}\int_{0}^{z} \log\frac{1}{1-t} \log\frac{1}{1-ut} dt = \sum_{k=0}^{j} \sum_{l=0}^{n-j+k} [z^{l}u^{k}] \int_{0}^{z} \log\frac{1}{1-t} \log\frac{1}{1-ut} dt \\ & \quad = \sum_{k=1}^{j} \sum_{l=k+2}^{n-j+k} \frac{1}{l k (l-k-1)} \, , \end{align*} which can be simplified to \begin{align*} & \sum_{k=1}^{j} \sum_{l=k+2}^{n-j+k} \frac{1}{l k (l-k-1)} = \sum_{k=1}^{j} \frac{1}{k} \sum_{l=1}^{n-j-1} \frac{1}{l (l+k+1)} = \sum_{k=1}^{j} \frac{1}{k(k+1)} \sum_{l=1}^{n-j-1} \left( \frac{1}{l} - \frac{1}{l+k+1}\right) \displaybreak[0] \\ & \quad = \sum_{k=1}^{j} \frac{1}{k(k+1)} \left(H_{n-j-1} + H_{k+1} - H_{n-j+k} \right) = \sum_{k=1}^{j} \left(\frac{1}{k} - \frac{1}{k+1}\right) \left(H_{n-j-1} + H_{k+1} - H_{n-j+k} \right) \displaybreak[0] \\ & \quad = H_{n-j-1} \sum_{k=1}^{j} \left(\frac{1}{k}-\frac{1}{k+1}\right) + \sum_{k=1}^{j} \left(\frac{H_{k}}{k}-\frac{H_{k+1}}{k+1}\right) + \sum_{k=1}^{j} \left(\frac{1}{k}-\frac{1}{k+1}\right) \\ & \qquad {} - \sum_{k=1}^{j} \left(\frac{H_{n-j+k}}{k}-\frac{H_{n-j+k+1}}{k+1}\right) - \frac{1}{n-j} \sum_{k=1}^{j} \left(\frac{1}{k+1}-\frac{1}{n-j+k+1}\right)\, . \end{align*} The sums telescope and we finally get \begin{align*} & [z^{n}u^{j}] \frac{1}{(1-z)(1-uz)}\int_{0}^{z} \log\frac{1}{1-t} \log\frac{1}{1-ut} dt = \frac{n+1}{(j+1)(n-j)} \left(H_{n+1}-H_{j+1}-H_{n+1-j} \right) \\ & \quad {} + \frac{2jn^{2}-4nj^{2}+2j^{3}+n^{2}-jn+2n-2j+1}{(n-j)(j+1)(n+1-j)} \, . \end{align*} \end{proof} The next theorem gives the variance, which is now easy to obtain. \begin{theorem} The variance $\Var{\asc{n}{j}}$ of the number of ascendants of the \th{j} node in a random search tree of size $n$ is \begin{equation}\begin{split} \Var{\asc{n}{j}} &= {\frac {2 \left (n+1\right )}{\left (n+1-j\right )j}} H_{n} + {\frac {\left (nj-2\,n-{j}^{2}+j-2\right )}{\left (n+1-j\right )j}} H_{j} + {\frac {\left (nj-2\,n-{j}^{2}+j-2\right )}{\left (n+1-j\right )j}} H_{n+1-j} \\ & \quad {} -H_{j}^{(2)}-H_{n+1-j}^{(2)} +{\frac {2 (nj-{j}^{2}+j+1)}{\left (n+1-j\right )j}} \, . \end{split}\end{equation} {\flushright{\hfill $\qed$}} \end{theorem} \section{Locally balanced binary search trees} \label{sec:lbsts} One approach to avoid drastically unbalanced binary search trees is the introduction of strict balance constraints like in AVLs or red-black trees~\cite{AVL,RBT}. Such schemes guarantee logarithmic performance of searches and updates in the worst-case, but they have additional space requirements and are more difficult to implement than standard BSTs. As an alternative, several authors~\cite{Bell,WW76,PobMun85} have suggested the use of a simple heuristic that makes the construction of poorly balanced trees much less likely than with the use of the standard algorithms. Furthermore, the heuristic was shown to yield significant savings in the expected search time. The basic idea is really simple: whenever a son is appended to a node that itself is a single son (its ``brother'' is an external node), a rotation of the three nodes is performed to place the median of the three elements as the root of the subtree and the other two elements as sons (see Figure~\ref{fig:lbst}). Since no other kind of rebalancing operation is ever made, Poblete and Munro refer to this technique as a \emph{fringe} heuristic. We will call the binary search trees constructed in this way \emph{locally balanced binary search trees} (LBST, for short). \begin{figure} \begin{center} \epsfig{file=lbst.eps,height=5cm} \end{center} \caption{The fringe heuristic} \label{fig:lbst} \end{figure} Poblete and Munro~\cite{PobMun85} and Poblete~\cite{Pob93} carry on the analysis of this heuristic and some generalizations by means of bottom-up or fringe techniques: they basically study the number of nodes that are at level $k$ and which are the root of a subtree of size 1 or 2. As we have already mentioned in the introduction, the standard model for random LBSTs states that a random LBST of size $n$ is the result of $n$ random insertions into an initially empty tree. Equivalently, a random LBST of size $n$ is the result of inserting the elements of a random permutation of $\{1,\dots,n\}$ into an initially empty tree. Here, we show that a recursive, top-down definition of the randomness model is also possible. This characterization of the model of randomness is more amenable to the kind of algebraic manipulations that we want to carry on; as we will see, the recurrence relations for the analyzed quantities translate to equations over generating functions in a natural way, almost automatically. \begin{defn} \label{def:random-lbsts} \begin{enumerate} \item A random binary search tree of size $s\le 2$ is also a random locally balanced search tree. Recall that a BST of size 2 is random if the smallest (resp. largest) key is the root with probability 1/2. \item A binary search tree $T$ of size $n\ge 3$, with left and right subtrees $T_1$ and $T_2$, is a random LBST if and only if, both $T_1$ and $T_2$ are random independent LBSTs, and \begin{equation*} \pi_{n,k}=\Prob{\,|T_1|=k-1 \,\Big|\, |T|=n\,{}} = \frac{(k-1)(n-k)}{\binom n3}, \qquad\text{for all $1\le k\le n$.} \end{equation*} \end{enumerate} \end{defn} The reader should have noticed that the only difference between this definition and that for random BSTs relies on the \emph{splitting probabilities} $\pi_{n,k}$. In the case of BSTs, each element of the random permutation has the same probability (namely, $1/n$) of being the first element and hence of becoming the root. In the case of LBSTs, when $n\ge 3$, the probability that the \th{k} element is one of the first three elements of the permutation and is the median of these three elements is \begin{displaymath} \frac{1}{n} \times \frac{k-1}{n-1} \times \frac{n-k}{n-2} \times 3! = \pi_{n,k}. \end{displaymath} Indeed, the left hand side of the equation above give us the probability that the \th{k} element is the first, times the probability that it is followed by a smaller element, times the probability that the two elements are followed by a larger element. For any permutation of such three elements, we have that the \th{k} element is among the first three elements and it is their median. Now, under these conditions the \th{k} element will be the root of the LBST (after the insertion of the first three elements, with rebalancing if necessary). The insertion of the fourth, fifth, etc. elements will not affect the root of the LBST. The principle applies recursively to the subsequences of elements smaller and greater than the selected element and the definition follows. This argument also justifies the deep connection between LBSTs, quicksort and quickselect (see Propositions~\ref{prop:quickselect} and~\ref{prop:quicksort}), when we consider the variants that select the median of 3 elements taken at random as the pivot of each partitioning phase. \section{The number of descendants in random LBSTs} \label{sec:desc-lbst} As in Section~\ref{sec:desc-bst}, let $\desc{n}{j}$ denote the number of descendants of the \th{j} node, but now in a random LBST of size $n$. The recursion for $\Prob{\desc{n}{j}=m}$ is almost the same as for random BSTs, the only difference being the splitting probability $\pi_{n,k}$, the probability that the root of the LBST is the \th{k} element. Thus, \begin{align} \Prob{\desc{n}{j}=m} &= \bigg[ \sum_{1\le kn-4$, by symmetry) appear in the appendix. % Table~\ref{table:avg-desc-lbst} at the end of the paper. \label{theo:avg-desc-lbst} \end{theorem} \begin{proof} Taking the first derivative with respect to $v$, and setting $v=1$ we get\footnote{It turns out that Maple gets stuck doing the work in the obvious way, i.e. take the derivative, then take the limit when $v\to 1$. But we can produce the differential equations satisfied by the generating functions for the factorial moments from the differential equation~\eqref{eq:deq-desc-lbst} and solve them. Also, the problem can be fixed by computing a \texttt{series} expansion of the derivatives around $v=1$.} \begin{align*} \left.\frac{\partial\descmedgf}{\partial v}\right|_{v=1} &= \frac{B_0(z,u)}{70 (1-uz)^2 (1-u)^7(1-z)^2} \\ &+\frac{B_1(z,u)}{7(1-u)^7(1-uz)^2}\log\frac{1}{1-z} \\ &+\frac{B_2(z,u)}{7(1-z)^2(1-u)^7}\log\frac{1}{1-uz}, \end{align*} where the $B_i(z,u)$'s are polynomials in $z$ and $u$. Their explicit value can be found in the appendix % Appendix~\ref{app:polynomials} at the end of this paper. In order to get to the coefficients, we use formul{\ae} such as \begin{align*} [z^nu^j]\frac{1}{(1-u)^4(1-uz)^2}\log\frac1{1-z}&= (n+1)\binom{j-n+3}3\Big(H_n-H_{n-1-j}\Big)\\ &+\frac{(j+1)n^3}6 -\frac{5(j+1)(j+2)n^2}{12}\\ &+\frac{(j+1)(11j^2+40j+30)n}{36} -\frac{3j-10}{12}\binom{j+3}3, \end{align*} \begin{align*} [z^nu^j]\frac{1}{(1-u)^5(1-uz)^2}\log\frac1{1-z}&= (n+1)\binom{j-n+4}4\Big(H_n-H_{n-1-j}\Big)\\ &-\frac{(j+1)n^4}{24} +\frac{(7j+18)(j+1)n^3}{48}\\ &-\frac{(j+1)(13j^2+65j+75)n^2}{72}\\ &+\frac{(j+1)(25j^3+173j^2+348j+180)n}{288}\\ &-\frac{12j-65}{60}\binom{j+4}4, \end{align*} and similar ones that are not too hard to obtain. To retrieve the final answer, we have also to take into account that we need to shift the coefficients in $z^n$ by 1 and multiply by $\frac 1n$, because we were considering $\parz\sum_{n,j,m}\Prob{\desc{n}{j}=m}z^nu^jv^m$. Putting everything together, the theorem follows. \end{proof} \begin{theorem} The second factorial moment of the number of descendants $\mdesc{2}{n}{j}=\Exp{\ffact{\desc{n}{j}}2}$ of the \th{j} node in a random LBST of size $n$ is, when $5\le j\le n-4$, \begin{align*} \mdesc{2}{n}{j} &= \left(\frac {36n}{5}-\frac {12}{35}\right) H_n + \left(\frac {36j}{5}-\frac {36n}{5}-\frac {48}{7}\right) H_{n+1-j} +\left(\frac {12}{35}-\frac {36j}{5}\right) H_j\\ &-\frac{132}{35j}-\frac {132}{35(n+1-j)} +\frac {3489}{175}-\frac {33j}{5} +\left(\frac {66}{7}-\frac {429j}{35}+\frac {33j^2}{5}\right)\frac{1}{n}\\ &+\frac {132 (j-1)^{2}}{35\ffact n2} +\frac { 44(2j-3) \ffact{(j-1)}2}{ 35\ffact n3} +\frac {66 (j-2 )\ffact{(j-1)}3}{35 \ffact n4}\\ &-\frac {66(2j-5) \ffact{(j-1)}4}{35 \ffact n5} +\frac {44(j-3)\ffact{(j-1)}5}{35 \ffact n6}. \end{align*} The formul{\ae} for the second factorial moment in the special cases (when $j\le 4$ or $j>n-4$) are collected in a table in the appendix. % table (Table~\ref{table:var-desc-lbst}) at the end of the paper. \label{theo:var-desc-lbst} \end{theorem} \begin{proof} The second factorial moment $\mdesc{2}{n}{j}$ is the coefficient of $z^{n-1}u^j$ times $\frac1n$ in \begin{align*} \left.\frac{\partial^2 \descmedgf}{\partial v^2}\right|_{v=1}& = \frac{C_0(z,u)}{35(1-z)^2(1-u)^7(1-uz)^2}\\ &+\frac{C_1(z,u)}{35(1-z)^2(1-u)^7(1-uz)^2} \log\frac{1}{1-z}\\ &+\frac{C_2(z,u)}{35(1-z)^2(1-u)^7(1-uz)^2} \log\frac{1}{1-uz} \end{align*} where the $C_i(z,u)$'s are polynomials in $z$ and $u$. They have been listed in the appendix. % Appendix~\ref{app:polynomials}. Using techniques similar to the ones in the proof of Theorem~\ref{theo:avg-desc-lbst}, we extract the coefficients and obtain the stated result. \end{proof} As in Section~\ref{sec:desc-bst}, we shift now our attention to the number of descendants of a random node in a random LBST of size $n$. We start giving an explicit expression for the probability distribution of $\descrnd{n}$. \begin{theorem} The probability that a random node in a random LBST of size $n$ has $m$ descendants is \begin{equation*} \Prob{\descrnd{n}=m} = \frac{12}{7}\,\frac{(n+2+m)(n-1-m)}{n^2(m+1)(m+2)} -\frac{12}{7}\, \frac{\ffact{m}{5}}{n\ffact{n}{6}}+\frac{12}{7n^2}, \end{equation*} for\/ $5\le m b \ge 0 \; \text{and} \; n \ge 3 \, , \label{rec_comp_qs_med} \end{align} with initial values $\qsmed{2}{0} = 1$, $\qsmed{2}{1} = 1$ and $\qsmed{n}{b} = 0$ otherwise. (With these initial values we take care of the one additional comparison, sorting a subfile of length $2$, when the pages are smaller than $2$.) To solve this recurrence, we introduce the bivariate generating function \newline $\qsmedgf(z,v) = \sum_{n > b \ge 0} \qsmed{n}{b} n z^{n-1} v^{b}$. Multiplying both sides of equation \eqref{rec_comp_qs_med} by $n (n-1) (n-2) z^{n-3} v^{b}$ and summing up over all $n > b \ge 0$ leads to the following differential equation \begin{align} \frac{\partial^{2}}{\partial z^{2}} \qsmedgf(z,v) & = \frac{12}{(1-z)^{2}} \qsmedgf(z,v) \\ & \quad + \frac {\scriptstyle{12({z}^{6}{v}^{4}+{z}^{5}{v}^{4}+{z}^{5}{v}^{3}-15\,{z}^{4}{v} ^{3}+10\,{z}^{3}{v}^{3}+10\,{z}^{3}{v}^{2}-5\,{z}^{2}{v}^{3}+5\,{z}^{2 }{v}^{2}-5\,{z}^{2}v+z{v}^{3}-4\,z{v}^{2}-4\,zv+z+{v}^{2}+v+1)}}{\left ( 1-z\right )^{5}\left (1-zv\right )^{5}} \, , \notag \end{align} with initial conditions $\qsmedgf(0,v) = 0$ and $\parz \qsmedgf(0,v) = 2 (1+v)$. This differential equation is of Eulerian type, and can be solved easily. We get then \begin{align} \qsmedgf(z,v) & = \left({\frac {120}{7}}\,{\frac {\left (1-z\right )^{4} \left (v+2\right ){v}^{5}}{\left (1-v\right )^{8}}}+{\frac {24}{7}}\,{\frac {1} {\left (1-v\right )\left (1-z\right )^{3}}}\right) \log\frac{1}{1-z} \notag \\ & \quad +\left (-{\frac {120}{7}}\,{\frac {\left (1-z\right )^{ 4}\left (v+2\right ){v}^{5}}{\left (1-v\right )^{8}}}+{\frac {24}{7}} \,{\frac {2\,v-3}{\left (1-v\right )\left (1-z\right )^{3}{v}^{2}}} \right ) \log\frac{1}{1-zv} \notag \\ & \quad -12\,{\frac {v}{\left (1-v\right )^{3}\left (1-zv\right )}} +2\,{\frac {v}{\left (1-zv\right )^ {2}\left (1-v\right )}}-2\,{\frac {v}{\left (1-zv\right )^{3}\left ( 1-v\right )}} \\ & \quad {} -{\frac {2}{49}}\,{\frac {89\,v-252}{\left (1-v\right ) \left (1-z\right )^{3}v}}-\frac{2}{7}\,{\frac {7\,{v}^{2}-31\,v+36}{\left (1-z \right )^{2}\left (1-v\right )^{2}v}}-{\frac {12}{7}}\,{\frac {2\,v-3}{\left (1-v\right )^{3}\left (1-z\right )}} \notag \\ & \quad {} +{\frac {2}{49}}\,{\frac {R(z,v)}{\left (1-v\right )^{7}}} \, . \notag \end{align} with \newline $ R(z,v) = 40\, {z}^{4}{v}^{6}+929\,{z}^{4}{v}^{5}+327\,{z}^{4}{v}^{4}-23\,{z}^{4}{v}^ {3}-23\,{z}^{4}{v}^{2}+12\,{z}^{4}v-2\,{z}^{4}-160\,{z}^{3}{v}^{6}- 3296\,{z}^{3}{v}^{5} -468\,{z}^{3}{v}^{4}+92\,{z}^{3}{v}^{3}+92\,{z}^{3 }{v}^{2}-48\,{z}^{3}v+8\,{z}^{3}+240\,{z}^{2}{v}^{6}+4104\,{z}^{2}{v}^ {5}-768\,{z}^{2}{v}^{4}+282\,{z}^{2}{v}^{3} -138\,{z}^{2}{v}^{2}+72\,{z }^{2}v-12\,{z}^{2}-160\,z{v}^{6}-1896\,z{v}^{5}+1632\,z{v}^{4}-1168\,z {v}^{3}+372\,z{v}^{2}-48\,zv +8\,z+40\,{v}^{6}+54\,{v}^{5}-618\,{v}^{4} +1132\,{v}^{3}-828\,{v}^{2}+222\,v-2 \, . $ \medskip Extracting the coefficients, we get with $\Exp{C_n^{(b)}} = \qsmed{n}{b} = \frac{1}{n} [z^{n-1} v^{b}] \qsmedgf(z,v)$ the required expectations. This leads to \begin{theorem} The expected number of comparisons to sort a random permutation of size $n$, when the recursion stops in subfiles of size $\le b$ and the pivots are selected as the median of samples of three elements, is for $n > b \ge 0$ and $n \ge 6$ given as \begin{equation*} \Exp{C_n^{(b)}} = \frac{12}{7} (n+1) H_{n} - \frac{12}{7} (n+1) H_{b+1} + \frac{37 n}{49} + \frac{219}{49} - \frac{36(n+1)}{7(b+2)} + \frac{4(3b-1)(b+1)^{\underline{6}}}{49 n^{\underline{6}}} \, . \end{equation*} \end{theorem} \section{The number of ascendants of a given node in a LBST} \label{sec:asc-lbst} As in the case of the number of ascendants in a random BST, computing the probability that the \th{j} node in a random LBST has $m$ ascendants turns out to be an extremely difficult problem. However, the recursive definition can easily be translated to a differential equation for the corresponding generating function $\ascmedgf(z,u,v)$. Because of the same technical reason discussed in Section~\ref{sec:desc-lbst}, the function $\ascmedgf(z,u,v)$ is actually the derivative w.r.t. $z$ of the generating function such that the coefficient of $z^nu^j$ is the PGF of $\asc{n}{j}$. The recurrence for $\asc{n}{j}$ \begin{equation*} \asc{n}{j} = \sum_{k=1}^{j-1} \pi_{n,k} (\asc{n-k}{j-k}+1) + \pi_{n,j} + \sum_{k=j+1}^{n} \pi_{n,k} (\asc{k-1}{j}+1) \quad \text{for} \; n \ge 3 \, , \end{equation*} with initial values $\asc{0}{j} = 0$, $\asc{1}{1} = 1$, $\asc{2}{1} = \frac{3}{2}$, $\asc{2}{2} = \frac{3}{2}$ and $\asc{n}{j} = 0$ otherwise, translates into the second-order differential equation \begin{equation} \frac16\frac{\partial^2\ascmedgf}{\partial z^2}= \frac v{(1-z)^2}\ascmedgf + \frac{u^2v}{(1-uz)^2}\ascmedgf + \frac{u^2v}{(1-z)^2(1-uz)^2}, \label{eq:deq-asc-lbst} \end{equation} and the initial values are $\ascmedgf(0,u,v)= uv$ and $\parz\ascmedgf(0,u,v)= uv(1 + v)(1 + u)$. This differential equation is the starting point for our next theorems. \begin{theorem} The expected number of ascendants $\avgasc{n}{j}=\Exp{\asc{n}{j}}$ of the \th{j} node in a random locally balanced search tree of size $n$ is \begin{align*} \avgasc{n}{j} &= \frac{24}{35}H_n+ \frac{18}{35}H_j+\frac{18}{35}H_{n+1-j} \\ &+\frac{12}{35j}+\frac{12}{35(n+1-j)} -\frac{279}{175}-\frac{6}{7n} \\ &+\frac{18j}{35n}-\frac{12(j-1)^2}{35\ffact n2}- \frac{4(2j-3)\ffact{(j-1)}{2}}{35\ffact n3} \\ &-\frac{6(j-2)\ffact{(j-1)}{3}}{35\ffact n4} +\frac{6(2j-5)\ffact{(j-1)}{4}}{35\ffact n5}- \frac{4(j-3)\ffact{(j-1)}{5}}{35\ffact n6}, \end{align*} for $5\le j\le n-4$. % Table~\ref{table:avg-asc-lbst} we give also In the appendix we give alse the cases $j=1,2,3,4$. The cases where $j>n-4$ follow from the special cases with $j\le 4$ and the symmetry in $j$ and $n+1-j$ of $\avgasc{n}{j}$. \label{theo:avg-asc-lbst} \end{theorem} \begin{proof} Although it is in principle possible to solve the differential equation\footnote{With the substitutions $\ascmedgf(z,u,v) = \Big(\frac{(1-z)(1-u)}{u}\Big)^{\frac{1+\sqrt{1+24v}}{2}} B(z,u,v)$ and $z=1+t(1-u)/u$, the resulting differential equation is hypergeometric.}~\eqref{eq:deq-asc-lbst}, it is sufficient for our purpose to take derivatives w.r.t. $v$ and setting $v=1$, to get the differential equation for $\avgascmedgf(z,u)$, the generating function whose coefficients are the expected values $\avgasc{n}{j}=\Exp{\asc{n}{j}}$. It is \begin{equation} \frac16\frac{\partial^2\avgascmedgf}{\partial z^2}- \left(\frac{1}{(1-z)^2}+\frac{u^2}{(1-uz)^2}\right)\avgascmedgf= \frac u{1-u} \left(\frac{1}{(1-z)^4}-\frac{u^3}{(1-uz)^4}\right), \label{eq:deq-avgasc-lbst} \end{equation} and the initial conditions are now $\avgascmedgf(0,u)= u$ and $\parz\avgascmedgf(0,u)=3u(1+u)$. The solution of the differential equation~\eqref{eq:deq-avgasc-lbst} yields the explicit form \begin{align*} \avgascmedgf(z,u) &= \frac{D_0(z,u)}{(1-z)^2(1-u)^7(1-uz)^2}\\ &+\frac{D_1(z,u)}{(1-z)^2(1-u)^7(1-uz)^2} \log\frac{1}{1-z}\\ &+\frac{D_2(z,u)}{(1-z)^2(1-u)^7(1-uz)^2} \log\frac{1}{1-uz}, \end{align*} where the polynomials $D_i(z,u)$ can be found in the appendix. % Appendix~\ref{app:polynomials}. Once we have the explicit form for $\avgascmedgf$, extracting the coefficients is just a matter of patience and careful computations. A possible shortcut is to expand each of the three main parts of $\avgascmedgf$ as power series in $z$ and $u$, and spot a pattern in the shape of the coefficients. The inspired guesses can be readily checked and proved by induction. For instance, the coefficient of $z^nu^j$ in the purely rational term of $\avgascmedgf$ is \begin{displaymath} -\frac{69}{175}n+\frac{18}{35}j -\frac9{175}, \end{displaymath} whenever $5\le j\le n-4$; the remaining values of $j$ are special cases that we have to consider separately. Similarly, the coefficient of $z^nu^j$ in the second term ---the one that contains $\log(1/(1-uz))$ as a factor--- is \begin{displaymath} \frac{18H_j(n+1)}{35}-{\frac {18j}{35}}+{ \frac {12n}{35j}}-{\frac {12}{35}}+{\frac {12}{35j}}. \end{displaymath} In the same vein, an explicit formula for the coefficient of the first term can be obtained. Finally, we collect everything, consider the coefficient $z^{n-1}u^j$ and divide by $n$, since $\ascmedgf$ is a derivative w.r.t. $z$. \end{proof} The differential equation~\eqref{eq:deq-avgasc-lbst} is exactly the same as the one for the number of passes in quickselect with median-of-three (see Proposition~\ref{prop:quickselect}). The only difference between the expected number of passes in quickselect, as given in the work by Kirschenhofer et al.~\cite{KirMarPro97}, and the number of ascendants in LBSTs relies on the initial conditions. The reason is that in the mentioned paper only one recursive call is counted if we want to select some element in a file of size $\le 2$, while the average number of ascendants of the \th{j} node in a random LBST of size $n\le 2$ is $3/2$ (for $j=1$ and $j=2$). Then $\avgasc{n}{j}$ and the expected number of passes to select the \th{j} element out of $n$ differ in the constant term, exactly by $1/7$. In a similar way, when differentiating the differential equation~\eqref{eq:deq-asc-lbst} two times w.r.t. $v$ and setting $v=1$, we get the differential equation for $\mascmedgf{2}(z,u)$, the generating function whose coefficients are the second factorial moments $\masc{2}{n}{j}$ of the number of ascendants. Solving this differential equation and extracting the coefficients leads to the second factorial moments, which are given in the appendix. \bigskip In~\cite{PobMun85} the authors considered the expectation and variance of $\ascrnd{n}$ in random LBSTs. To be more precise, they stated the problem in terms of unsuccessful search costs. Here, we are able to reproduce their results and extend them to higher order moments. Since we deal with ascendants of internal nodes, our results can be naturally stated in terms of successful search costs, and then translated to unsuccessful costs using Proposition~\ref{prop:tree-parameters}. where $\avgascrnd{n}=\Exp{\ascrnd{n}}$ is the expected number of ascendants of a random node in a random tree with $n$ nodes. \begin{theorem} \label{theo:pgf-rasc-lbst} Let \begin{equation*} \ascrndmedgf(z,v) = \frac{\partial}{\partial z}\sum_{n,m} \Prob{\ascrnd{n}=m}\,z^nv^m. \end{equation*} Then \begin{align*} \ascrndmedgf(z,v) &=\frac{v}{(1-2v)(1-z)^2} \\ &-\frac{v^2}{(1-2v)\Delta}\Big((\Delta + 4v+3)(1-z)^{-(\Delta-1)/2} +(\Delta - 4v-3)(1-z)^{(\Delta+1)/2}\Big), \end{align*} where $\Delta=\sqrt{1+48v}$. \end{theorem} \begin{proof} The differential equation to be solved (from Equation~\eqref{eq:deq-asc-lbst}, plugging $u=1$) is $$ \frac16 \frac{\partial^2\ascrndmedgf}{\partial z^2} =\frac{2v}{(1-z)^2}\ascrndmedgf+\frac v{(1-z)^4}, $$ where $\ascrndmedgf(z,v)=\ascmedgf(z,1,v)$ and the initial conditions are $\ascrndmedgf(0,v)=v$ and $\parz\ascrndmedgf(0,v)=2v(1+v)$. Recall that $\ascrndmedgf(z,v)=\ascmedgf(z,1,v)$. The solution of the differential equation above is the explicit form given in the theorem. \end{proof} Extracting coefficients in exact form from there is quite difficult. However, as Philippe Flajolet kindly pointed to us, asymptotic information and most notably, the limiting probability distribution can be established~\cite{FlaSor93,Hwang}. In this case, it follows that $\ascrnd{n}$ converges in distribution (converges in law) to a Gaussian distribution, i.e. $$\Prob{\frac{\ascrnd{n}-\frac{12}{7}\log n} {\sqrt{\frac{300}{343}\log n}} < x} = \frac{1}{\sqrt{2\pi}}\int^x_{-\infty}e^{-t^2/2}\,dt + \bigOh\left(\frac{1}{\sqrt{\log n}}\right).$$ This result follows from the asymptotic estimation for the average and the variance of $\ascrnd{n}$ and the fact that $\ascrndmedgf(z,v)$ is essentially a quasi-power of $[z^n]\ascrndmedgf(z,v)$ in a neighborhood of $v=1$, i.e. $$[z^n]\ascrndmedgf(z,v) = c(v) \cdot n^{(\Delta-3)/2} \left(1 + \bigOh(1/\sqrt{n})\right),$$ and the error term is uniformly bounded. Using the expansion \cite{FlOd90} \begin{equation*} [z^{n}] (1-z)^{\alpha} = \frac{n^{-\alpha-1}}{\Gamma\left(-\alpha\right)} \left(1+ \frac{\alpha(\alpha+1)}{2n} + \mathcal{O}\Big(\frac{1}{n^{2}} \Big)\right) \end{equation*} we get uniformly in the circle $|v-1|<\frac{1}{4}$ \begin{align*} [z^{n}] \ascrndmedgf(z,v) = [z^{n}] -\frac{v^2}{(1-2v)\Delta} (\Delta +4v+3)(1-z)^{-(\Delta-1)/2} + \mathcal{O}(n) \\ = - \frac{v^{2}(\Delta+4v+3)}{(1-2v)\Delta\Gamma(\frac{\Delta-1}{2})} \cdot n^{\frac{\Delta-3}{2}} \left(1 + \bigOh\Big(\frac{1}{\sqrt{n}}\Big)\right) . \end{align*} Applying the following \textit{quasi-power} theorem of Hwang \cite{Hwang,FlaSed} leads immediately to the above given result. \begin{theorem}\textup{\textbf{(Quasi-power theorem [H.-K.~Hwang])}} Assume that the Laplace transforms $\lambda_{n}(s) = \Exp{e^{s X_{n}}}$ of a sequence of random variables $X_{n}$ are analytic in a disc $|s|<\rho$, for some $\rho > 0$, and satisfy there an expansion of the form \begin{equation*} \lambda_{n}(s) = e^{\beta_{n} U(s) + V(s)} \left(1+\mathcal{O} \Big(\frac{1}{\kappa_{n}}\Big)\right) , \end{equation*} with $\beta_{n}$, $\kappa_{n} \to + \infty$, and $U(s)$, $V(s)$ analytic in $|s| \le \rho$. Assume also the variability condition, \begin{equation*} U''(0) \neq 0 . \end{equation*} Under these assumptions, the mean and variance of $X_{n}$ satisfy \begin{equation*} \Exp{X_{n}} = \beta_{n} U'(0) + V'(0) + \mathcal{O}(\kappa_{n}^{-1}) \, , \quad \Var{X_{n}} = \beta_{n} U''(0) + V''(0) + \mathcal{O}(\kappa_{n}^{-1}) . \end{equation*} The distribution of $X_{n}$ is asymptotically Gaussian and the speed of convergence to the Gaussian limit is $\mathcal{O}(\kappa_{n}^{-1} + \beta_{n}^{-1/2})$: \begin{equation*} \Prob{\frac{X_{n}-\beta_{n}U'(0)}{\sqrt{\beta_{n} U''(0)}} \le x} = \Phi(x) + \mathcal{O}\left(\frac{1}{\kappa_{n}} + \frac{1}{\sqrt{\beta_{n}}} \right). \end{equation*} $\Phi(x)$ denotes here the distribution function of the Gaussian normal distribution. \hfill \qed \end{theorem} \medskip The next step in our programme is to differentiate $\ascrndmedgf$ as many times as needed w.r.t. $v$ and set $v=1$, in order to get the generating functions for factorial moments. \begin{theorem} \label{theo:avg-rasc-lbst} The expected number of ascendants $\avgascrnd{n}=\Exp{\ascrnd{n}}$ of a random node in a random LBST of size $n$, when $n\ge 6$, is \begin{equation*} \avgascrnd{n} = \frac{12}{7}\Big(1+\frac1n\Big)% H_n-\frac{1}{49}\Big(124-\frac9n\Big). \end{equation*} \end{theorem} \begin{proof} Let, as usual, \begin{displaymath} \mascrndgf{s}(z)=\left.\frac{\partial^s\ascrndmedgf}{\partial v^s}\right|_{v=1}. \end{displaymath} To avoid cluttering the notation, we also let $\avgascrndmedgf(z)=\mascrndgf{1}(z)$. Here is the generating function for the expectations $$ \avgascrndmedgf(z) = \frac{24}{7}\frac{1}{(1-z)^3}\log\frac{1}{1-z} +\frac{4}{49}(1-z)^{-3}+(1-z)^{-2}-\frac{4}{49}(1-z)^4. $$ Then we extract the \th{(n-1)} coefficient and divide by $n^2$ to get the expected value of $\ascrnd{n}$; recall that since we are averaging w.r.t. $j$ and $\ascrndmedgf$ is already a partial derivative w.r.t $z$, we have in fact \begin{displaymath} \Exp{\ascrnd{n}}=\frac{1}{n^2}[z^{n-1}]\avgascrndmedgf(z). \end{displaymath} \end{proof} \begin{theorem} \label{theo:var-rasc-lbst} The variance of the number of ascendants, $\ascrnd{n}$, of a random node in a random LBST with $n$ nodes, or equivalently, the variance of the successful search cost for a random element in a LBST of size $n$ is, when $n\ge 6$, \begin{align*} \Var{\ascrnd{n}} &= \frac{1}{343}\Big(300+\frac{2100}{n}-\frac{216}{n^2}\Big)H_n\\ &-\frac{144}{49}\Big(1+\frac1n\Big)\Big(\frac{H_n^2}{n}+H_n^{(2)}\Big) +\frac{1}{2401}\Big(10758+\frac{2431}{n}-\frac{81}{n^2}\Big) +\frac{2304}{343n\,\ffact{n}{6}}. \end{align*} \end{theorem} \begin{proof} Analogously to what we did in the proof of the previous theorem, we compute the second derivative of $\ascrndmedgf(z,v)$, and let $v=1$. Then \begin{align*} \mascrndgf{2}(z) &= \frac{288}{49}\frac{1}{(1-z)^3}\log^2\frac{1}{1-z} +\Big(-\frac{480}{343}\frac{1}{(1-z)^3} +\frac{96}{343}(1-z)^4\Big)\log\frac{1}{1-z}\\ &+\frac{9988}{2401}\frac{1}{(1-z)^3} -4\frac{1}{(1-z)^2} -\frac{384}{2401}(1-z)^4. \end{align*} Extracting the coefficients is not as easy as before, but it is also doable, yielding the second factorial moment: \begin{gather*} \Exp{\ffact{\ascrnd{n}}{2}} = \frac{144}{49}\Big(1+\frac1n\Big)\Big(H_n^2-H_n^{(2)}\Big)- \frac{1}{343}\Big({3264}+\frac{1248}{n}\Big)H_n\\ +\frac{1}{2401}\Big(32210-\frac{242}{n}\Big) +\frac{2304}{343n\,\ffact{n}{6}}. \end{gather*} From here, the remaining computations are just mechanical. \end{proof} For higher order moments, i.e. $s>2$, the procedure applies but the computations get messier. If we do only consider the main order term in $\mascrnd{s}{n}=\Exp{\ffact{\ascrnd{n}}{s}}$, then the result is much easier. \begin{theorem} \label{theo:mom-rasc-lbst} The \th{s} factorial moment of the number of ascendants, $\ascrnd{n}$, of a random node in a random LBST with $n$ nodes, or equivalently, the \th{s} factorial moment of the successful search cost for a random element in a LBST of size $n$ is, when $n\ge 6$, \begin{equation*} \mascrnd{s}{n} = \left(\frac{12}{7}\right)^s\,\log^s n + \bigOh(\log^{s-1} n). \end{equation*} \end{theorem} \section*{Acknowledgements} We thank Philippe Flajolet for useful comments and suggestions. We also wish to thank the authors of the computer algebra system \textsc{Maple} who, although they might not know, greatly contributed to make this paper possible. \bibliographystyle{plain} \begin{thebibliography}{10} \bibitem{AVL} G.M. {Adel'son-Vel'skii} and E.M. Landis. \newblock An algorithm for the organization of information. \newblock {\em Dokladi Akademia Nauk SSSR}, 146(2):263--266, 1962. \newblock English translation in Soviet Math. Doklay 3 ,1962, 1259-1263. \bibitem{AraSei} C.R. Aragon and R.G. Seidel. \newblock Randomized search trees. \newblock In {\em Proc. of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS)}, pages 540--545, 1989. \bibitem{AroDen} S.R. Arora and W.T. Dent. \newblock Randomized binary search technique. \newblock {\em Comm. ACM}, 12(2):77--80, 1969. \bibitem{Bell} C.J. Bell. \newblock {\em An Investigation into the Principles of the Classification and Analysis of Data on an Automatic Digital Computer}. \newblock PhD thesis, Leeds University, 1965. \bibitem{BroShu} G.G. Brown and B.O. Shubert. \newblock On random binary trees. \newblock {\em Mathematics of Operations Research}, 9(1):43--65, 1984. \bibitem{FlOd90} Ph. Flajolet and A.M. Odlyzko. \newblock Singularity analysis of generating functions. \newblock {\em SIAM Journal on Discrete Mathematics}, 3(2):216--240, May 1990. \bibitem{FlaSed} Ph.~Flajolet and R.~Sedgewick. \newblock The Average Case Analysis of Algorithms: Multivariate Asymptotics and Limit Distributions. \newblock {\em Rapport de recherche de l'INRIA} \#3162, 1997. \bibitem{FlaSor93} Ph. Flajolet and M.~Soria. \newblock General combinatorial schemas: Gaussian limit distributions and exponential tails. \newblock {\em Discrete Mathematics}, 114, 1993. \bibitem{GonBae91} G.H. Gonnet and R.~{Baeza-Yates}. \newblock {\em Handbook of {A}lgorithms and {D}ata {S}tructures - In {P}ascal and {C}}. \newblock Addison-Wesley, 2nd edition, 1991. \bibitem{GraKnuPat} R.L. Graham, D.E. Knuth, and O.~Patashnik. \newblock {\em Concrete {M}athematics}. \newblock Addison-Wesley, 1989. \bibitem{RBT} L.J. Guibas and R.~Sedgewick. \newblock A dichromatic framework for balanced trees. \newblock In {\em Proc. of the 19th Annual IEEE Symposium on Foundations of Computer Science (FOCS)}, pages 8--21, 1978. \bibitem{Hoare61} C.A.R. Hoare. \newblock Find ({A}lgorithm 65). \newblock {\em Comm. ACM}, 4:321--322, 1961. \bibitem{Hoare62} C.A.R. Hoare. \newblock Quicksort. \newblock {\em Comput. J.}, 5:10--15, 1962. \bibitem{FlaHos} M.~Hoshi and Ph. Flajolet. \newblock Page usage in a quadtree index. \newblock {\em BIT}, 32(3):384--402, 1992. \bibitem{Hwang} H.-K. Hwang. \newblock {\em Th\'eor\`emes limites pour les structures combinatoires et les fonctions arithm\'etiques}. \newblock PhD thesis, Ecole Polytechnique, 1994. \bibitem{Kam77} E.~Kamke. \newblock {\em Differentialgleichungen: L\"osungsmethoden und {L}\"osungen}. \newblock Teubner, Stuttgart, 1977. \bibitem{KirMarPro97} P. Kirschenhofer, C. Mart{\'{\i}}nez, and H. Prodinger. \newblock {Analysis} {of} {Hoare's} {Find} {Algorithm} {with} {Median-of-three} {partition}. \newblock {\em Random Structures {\&} Algorithms}, 10:143--156, 1997. \bibitem{KirsProd} P.~Kirschenhofer and H.~Prodinger. \newblock Comparisons in {H}oare's {F}ind algorithm. \newblock {\em Combinatorics, Probability and Computing}, 7:111-120, 1998. \bibitem{Ifip} D.E. Knuth. \newblock Mathematical analysis of algorithms. \newblock In {\em Proc. of the 1971 IFIP Congress}, pages 19--27, Amsterdam, 1972. North-Holland. \bibitem{Knuth3} D.E. Knuth. \newblock {\em The {A}rt of {C}omputer {P}rogramming: {S}orting and {S}earching}, volume~3. \newblock Addison-Wesley, 1973. \bibitem{Lent} J.~Lent. \newblock {\em Probabilistic analysis of some searching and sorting algorithms}. \newblock PhD thesis, George Washington University, 1996. \bibitem{Lou} G.~Louchard. \newblock Exact and asymptotic distributions in digital and binary search trees. \newblock {\em Theoretical Informatics and Applications}, 21(4):479--496, 1987. \bibitem{Lyn} W.C. Lynch. \newblock More combinatorial properties of certain trees. \newblock {\em Comput. J.}, 7:299--302, 1965. \bibitem{Mahmoud} H.M. Mahmoud. \newblock {\em Evolution of Random Search Trees}. \newblock Wiley Interscience, 1992. \bibitem{Pan97} A. Panholzer. \newblock {\em Untersuchungen zur durchschnittlichen Gestalt gewisser Baumfamilien. Mit besonderer Be\-r{\"u}ck\-sich\-ti\-gung von Anwendungen in der Informatik.} \newblock PhD thesis, Technische Universit{\"a}t Wien, 1997. \bibitem{Pob93} P.V. Poblete. \newblock The analysis of heuristics for search trees. \newblock {\em Acta Informatica}, 30:233--248, 1993. \bibitem{PobMun85} P.V. Poblete and J.I. Munro. \newblock The analysis of a fringe heuristic for binary search trees. \newblock {\em J. Algorithms}, 6:336--350, 1985. \bibitem{RouMar96} S.~Roura and C.~Mart\'{\i}nez. \newblock Randomization of search trees by subtree size. \newblock In J.~D\'{\i}az and M.~Serna, editors, {\em Proc. of the 4th European Symposium on Algorithms (ESA)}, volume 1136 of {\em LNCS}, pages 91--106. Springer, 1996. \bibitem{SalZim} B.~Salvy and P.~Zimmermann. \newblock Gfun: a {M}aple package for the manipulation of generating and holonomic functions in one variable. \newblock {\em ACM Transactions on Mathematical Software}, 20(2):163--177, 1994. \bibitem{Sedgewick} R.~Sedgewick. \newblock {\em Quicksort}. \newblock Garland, New York, 1978. \bibitem{Sedgewick88} R.~Sedgewick. \newblock {\em Algorithms in C}. \newblock Addison-Wesley, 3rd edition, 1997. \bibitem{SedgFlaj} R.~Sedgewick and Ph. Flajolet. \newblock {\em An Introduction to the Analysis of Algorithms}. \newblock Addison-Wesley, 1996. \bibitem{FV90} J.S. Vitter and Ph. Flajolet. \newblock Average-case analysis of algorithms and data structures. \newblock In J.~van Leeuwen, editor, {\em Handbook of Theoretical Computer Science}, chapter~9. North-Holland, 1990. \bibitem{WW76} A.~Walker and D.~Wood. \newblock Locally balanced binary trees. \newblock {\em Comput. J.}, 19(4):322--325, 1976. \bibitem{Wil90} H.~Wilf. \newblock {\em Generatingfunctionology}. \newblock Academic Press, 1990. \end{thebibliography} \end{document}