A Top-Down Analysis of Fringe-Balanced Binary Search Trees

The trees in the title are obtained by performing rotations on subtrees of size 3 whenever necessary. Mahmoud has recently considered the parameter ``number of rotations'', by means of a P\'olya-Eggenberger urn model. Alternatively, we propose a top-down approach that leads to differential equations. The solution is related to the Weierstrass' $\wp$-function. This fact allows to derive the asymptotic normality of the parameter by means of Hwang's quasi-power theorem rather easily. We can also describe the above mentioned urn model by an operator calculus as in the book ``Mathematics for the Analysis of Algorithms'' by Greene and Knuth. This leads to rather simple and convenient computations. The results were obtained jointly with Alois Panholzer.