Average Case-Analysis of Priority trees: A structure for priority queue administration

\begin{abstract} Priority trees (\mbox{\textit{p\/}-trees}) are a certain variety of binary trees of size $n$ constructed from permutations of the numbers $1,\dots,n$. In this paper we analyse several parameters depending on $n$ (the size) and $j$ (a number between $1$ and $n$), such as the length of the left path (connecting the root and the leftmost leaf), the height of node $j$ (= distance from the root), the number of left edges on the path from the root to the node $j$, the number of descendants of node $j$, the number of key comparisons when inserting an element between $j$ and $j+1$, the number of key comparisons when cutting the \mbox{\textit{p\/}-trees} into two \mbox{\textit{p\/}-trees}, the number of nodes with $0$, $1$ or $2$ children. Methodologically, recursions are set up according to a fundamental decomposition of the family $\mathcal{A}$ of \mbox{\textit{p\/}-trees} (using auxiliary quantities $\mathcal{B}$ and $\mathcal{C}$); using generating functions, they lead to systems of differential equations that can be solved explicitly with some efforts. The quantities of interest can then be identified as coefficients in the explicit forms of the generating functions. \end{abstract}

This paper is available in the Dvi and PostScript format.


(Back to List of Papers)