Java Reference
In-Depth Information
Proof of
Theorem 22.7
(continued from previous page)
From Figure 22.6,
S i () S f () S f (),
+
so applying Theorem 22.4 yields
(22.10)
R i X
()
+
R f G
()
2 R f X
()
-
2
Rearranging Equation 22.10, we obtain
(22.11)
R f ()2 R f () R i ()
-
-
2
When we substitute Equation 22.11 into Equation 22.9, we get
Δ
3 R f () R i ()
(
-
)
-
2
Now that we have established bounds for each splaying step, we can
finally complete the proof of Theorem 22.2.
Proof of
Theorem 22.2
Let R 0 ( X ) be the rank of X prior to the splay. Let R i ( X ) be X 's rank after the i th splay-
ing step. Prior to the last splaying step, all splaying steps must be zig-zags or zig-zigs.
Suppose that there are k such steps. Then the total number of rotations performed at
that point is 2 k . The total potential change is This
sum telescopes to At this point, the total number of rotations
plus the total potential change is bounded by because the 2 k term cancels
and the initial rank of X is not negative. If the last rotation is a zig-zig or a zig-zag,
then a continuation of the telescoping sum gives a total of 3 R ( root ) . Note that here,
on the one hand, the -2 in the potential increase cancels the cost of two rotations.
On the other hand, this cancellation does not happen in the zig, so we would get a
total of 3 R ( root ) +1 . The rank of the root is log N , so then—in the worst case—the total
number of rotations plus the change in potential during a splay is at most 3 log N + 1 .
Σ
k
(3( R i () R i
-
- ())
-
2.
i
=
1
3( R k () R 0 ())
-
-
2 k .
3 R k ()
Although it is complex, the proof of the splay tree bound illustrates sev-
eral interesting points. First, the zig-zig case is apparently the most expensive:
It contributes a leading constant of 3, whereas the zig-zag contributes 2. The
proof would fall apart if we tried to adapt it to the rotate-to-root algorithm
because, in the zig case, the number of rotations plus the potential change is
The 1 at the end does not telescope out, so we would not
be able to show a logarithmic bound. This is fortunate because we already
know that a logarithmic bound would be incorrect.
R f X
()
-
R i X
()
+
1.
Search WWH ::




Custom Search