Java Reference
In-Depth Information
Proof of
Theorem 22.6
(continued from previous page)
Also,
S
i
()
S
i
()
≥
. Consequently,
R
i
()
R
i
()
≥
. Making this substitution and rear-
ranging terms gives
(22.6)
Δ
≤
R
f
P
()
+
R
f
G
()
-
2
R
i
X
()
From Figure 22.5,
S
f
()
S
f
()
S
f
()
+
≤
. Applying Theorem 22.4, we obtain
log
S
f
()
+
log
S
f
() 2 log
S
f
() 2
≤
-
, which by the definition of rank, becomes
(22.7)
R
f
()
R
f
() 2
R
f
() 2
+
≤
-
Substituting Equation 22.7 into Equation 22.6 yields
(22.8)
Δ
≤
2
R
f
() 2
R
i
()
-
-
2
As for the zig rotation,
, so we can add it to the right side of Equa-
R
f
()
R
i
() 0
-
>
tion 22.8, factor, and obtain the desired
Δ
≤
3
R
f
()
R
i
()
(
-
)
-
2
Finally, we prove the bound for the zig-zig case.
Theorem 22.7
For a zig-zig step,
Δ
≤
3(
R
f
()
R
i
())
-
-
2.
As before, we have three changes, so the potential change is given by
Proof
Δ
=
R
f
X
()
-
R
i
X
()
+
R
f
P
()
-
R
i
P
()
+
R
f
G
()
-
R
i
G
()
From Figure 22.6,
S
f
X
()
=
S
i
G
()
;
their ranks must be equal, so we obtain
Δ
=
-
R
i
X
()
+
R
f
P
()
-
R
i
P
()
+
R
f
G
()
We also can obtain
R
i
P
()
>
R
i
X
()
and
R
f
P
()
<
R
f
X
()
.
Making this substitution and
rearranging gives
(22.9)
Δ
<
R
f
()
R
f
() 2
R
i
()
+
-
(continues next page)
Search WWH ::
Custom Search