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