Annals of Combinatorics 2 (1998) 173-184

An Analytic Approach for the Analysis of Rotations in Fringe-balanced Binary Search Trees

Alois Panholzer1 and Helmut Prodinger2

Institut für Algebra und Diskrete Mathematik, Technical University of Vienna Wiedner Hauptstrasse 8-10, A-1040 Vienna, Austria

Received May 12, 1998

AMS Subject Classification: 68P05

Abstract.This paper presents an analytic approach to the construction cost of fringe-balanced binary search trees. In [7], Mahmoud used a bottom-up approach and an urn model of Pólya. 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 construct such a fringe balanced search tree. We also obtain the exact expectation and variance with this method. Although Pólya's urn model is no longer needed, we also present an elegant analysis of it based on an operator calculus as in [4].

Keywords: fringe-balanced trees, Weierstrass' wp-function, central limit theorem


1.  M. Abramowitz and I.A. Stegun, Handbook of Mathematical Functions, Eds., 9th Edition, Dover Publications, Inc., New York, 1970.

2.  Flajolet and A.M. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990) 216–240.

3.  Flajolet and R. Sedgewick, The average case analysis of algorithms: Multivariate asymptotics and limit distributions, Technical Report \#3162, INRIA, 1997.

4.  D.H. Greene and D.E. Knuth, Mathematics for the analysis of algorithms, 2nd Ed., Birkhäuser, Boston, 1982.

5.  H.-K. Hwang, Thèorèmes limites pour les structures combinatoires et les fonctions arithmètiques, PhD thesis, Ecole Polytechnique, 1994.

6.  E. Kamke, Differentialgleichungen - Lösungsmethoden und Lösungen, Vol. 1, 10th Ed., Teubner, Stuttgart, 1983.

7.  H. Mahmoud, On rotations in fringe-balanced binary trees, Inform. Process. Lett. 65 (1998) 41–46.

8.  C. Martïnez, A. Panholzer, and H. Prodinger, On the number of descendants and ascendants in random search trees, Electron. J. Combin. 5 (1) (1998) \#R20.

9.  P. Poblete and I. Munro, The analysis of a fringe heuristic for binary search trees, J. Algorithms 6 (1985) 336–350.

10.  R. Sedgewick and Ph. Flajolet, Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, Massachusetts, 1996.

11.  R. Smythe, Central limit theorems for urn models, Stochastic Process. Appl. 65 (1996) 115–137.

12.  W. Walker and D. Wood, Locally balanced binary search trees, Comput. J. 19 (1976) 322–325.

13.  H. Wenzel and P. Meinhold, Gewöhnliche Differentialgleichungen, Teubner, Stuttgart, 1994.

14.  E.T. Whittaker and G.N. Watson, A Course of Modern Analysis, 4th Ed., University Press, Cambridge, 1927.

Get the LaTex | DVI | PS file of this abstract.