Fringe-balanced 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 top-down 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 quasi-power theorem [2]. An alternative way of obtaining the exact expectation and variance, which relies on operator calculus, is also presented.
pn,k = |
|
Fn,m = |
|
|
pn,k |
|
Fk-1,l Fn-k,m-l + |
|
|
pn,k |
|
Fk-1,l Fn-k,m-1-l (1) |
M1(z) = |
|
G(z,v) |
½ ½ ½ ½ |
|
= |
|
n Mn(1) zn-1, and M2(z) = |
|
G(z,v) |
½ ½ ½ ½ |
|
= |
|
n Mn(2) zn-1, |
Mn= |
|
n - |
|
(n ³ 6), Varn = |
|
n - |
|
(n ³ 12). |
|
(1+2v) G3(z,v) + |
|
(1-v) = |
æ ç ç è |
|
G(z,v) |
ö ÷ ÷ ø |
|
, |
z = |
|
dx/ |
|
. |
t=( |
|
)1/2 |
æ ç ç ç ç ç è |
z- |
|
|
ö ÷ ÷ ÷ ÷ ÷ ø |
º( |
|
)1/2(z-s(v)), |
F(z,v)= |
|
+ O | ( | z-s(v) | ) |
|
. |
( |
|
)1/2s(v) = 2F1 |
æ ç ç ç ç ç è |
|
½ ½ ½ ½ ½ ½ ½ |
- |
|
ö ÷ ÷ ÷ ÷ ÷ ø |
. |
Pr |
ì ï ï í ï ï î |
|
£ x |
ü ï ï ý ï ï þ |
= F(x) + O |
æ ç ç è |
|
ö ÷ ÷ ø |
. |
A = |
|
. |
Pn+1(u) = |
|
pn,k |
é ê ê ë |
|
uk-1 + |
æ ç ç è |
1- |
|
ö ÷ ÷ ø |
uk+1 |
ù ú ú û |
= |
|
æ ç ç è |
u + |
|
(1-u2) D |
ö ÷ ÷ ø |
pn,k uk |
E{Xn+1(2)} = U D Pn+1(u) = |
æ ç ç è |
U + |
æ ç ç è |
1- |
|
ö ÷ ÷ ø |
U D |
ö ÷ ÷ ø |
Pn(u) = 1 + |
|
E{Xn(2)} |
Rn+1(u,v) = |
|
pn,k,l |
æ ç ç è |
|
uk-1vl + |
|
uk-1vl+1 + |
æ ç ç è |
1- |
|
ö ÷ ÷ ø |
uk+1vl |
ö ÷ ÷ ø |
. |
E{Rn+1(u,v)} = |
æ ç ç è |
|
UuUvDu + UuUvDv |
ö ÷ ÷ ø |
Rn(u,v) = E{Rn(u,v)} + |
|
E{Xn(2)}. |
This document was translated from LATEX by HEVEA.