An analytic approach for the analysis of rotations in fringe-balanced binary search trees

\begin{abstract} This paper presents an analytic approach to the construction cost of fringe-balanced binary search trees. In \cite{Mah1998}, Mahmoud used a bottom-up approach and an urn model of P\'olya. The present method is top-down and uses differential equations and Hwang's quasi-power theorem to derive the asymptotic normality of the number of rotations needed to constract such a {\it fringe balanced search tree}. We also obtain the exact expectation and variance with this method. Although P\'olya's urn model is not needed anymore, we also present an elegant analysis of it, based of an operator calculus as in Greene and Knuth \cite{GreKnu1982}. \end{abstract}



This paper is available in the PostScript format.

helmut@gauss.cam.wits.ac.za,



(Back to List of Papers)