Fringebalanced binary search trees are obtained by performing rotations only on subtrees of size three. The parameter ``number of rotations'' has recently been studied by Mahmoud [3], using a Pólya urn model. This talk, based on [5] proposes a topdown approach of the problem, that leads to a differential equation. The solution is related to the Weierstrass' Ãfunction. This fact allows to derive the asymptotic normality of the parameter by means of Hwang's quasipower theorem [2]. An alternative way of obtaining the exact expectation and variance, which relies on operator calculus, is also presented.
p_{n,k} = 

F_{n,m} = 


p_{n,k} 

F_{k1,l} F_{nk,ml} + 


p_{n,k} 

F_{k1,l} F_{nk,m1l} (1) 
M_{1}(z) = 

G(z,v) 
½ ½ ½ ½ 

= 

n M_{n}^{(1)} z^{n1}, and M_{2}(z) = 

G(z,v) 
½ ½ ½ ½ 

= 

n M_{n}^{(2)} z^{n1}, 
M_{n}= 

n  

(n ³ 6), Var_{n} = 

n  

(n ³ 12). 

(1+2v) G^{3}(z,v) + 

(1v) = 
æ ç ç è 

G(z,v) 
ö ÷ ÷ ø 

, 
z = 

dx/ 

. 
t=( 

)^{1/2} 
æ ç ç ç ç ç è 
z 


ö ÷ ÷ ÷ ÷ ÷ ø 
º( 

)^{1/2}(zs(v)), 
F(z,v)= 

+ O  (  zs(v)  ) 

. 
( 

)^{1/2}s(v) = _{2}F_{1} 
æ ç ç ç ç ç è 

½ ½ ½ ½ ½ ½ ½ 
 

ö ÷ ÷ ÷ ÷ ÷ ø 
. 
Pr 
ì ï ï í ï ï î 

£ x 
ü ï ï ý ï ï þ 
= F(x) + O 
æ ç ç è 

ö ÷ ÷ ø 
. 
A = 

. 
P_{n+1}(u) = 

p_{n,k} 
é ê ê ë 

u^{k1} + 
æ ç ç è 
1 

ö ÷ ÷ ø 
u^{k+1} 
ù ú ú û 
= 

æ ç ç è 
u + 

(1u^{2}) D 
ö ÷ ÷ ø 
p_{n,k} u^{k} 
E{X_{n+1}^{(2)}} = U D P_{n+1}(u) = 
æ ç ç è 
U + 
æ ç ç è 
1 

ö ÷ ÷ ø 
U D 
ö ÷ ÷ ø 
P_{n}(u) = 1 + 

E{X_{n}^{(2)}} 
R_{n+1}(u,v) = 

p_{n,k,l} 
æ ç ç è 

u^{k1}v^{l} + 

u^{k1}v^{l+1} + 
æ ç ç è 
1 

ö ÷ ÷ ø 
u^{k+1}v^{l} 
ö ÷ ÷ ø 
. 
E{R_{n+1}(u,v)} = 
æ ç ç è 

U_{u}U_{v}D_{u} + U_{u}U_{v}D_{v} 
ö ÷ ÷ ø 
R_{n}(u,v) = E{R_{n}(u,v)} + 

E{X_{n}^{(2)}}. 
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.