Java Reference
In-Depth Information
22.4.1 proof of the splaying bound
First, if the node to splay is already at the root, there are no rotations and no
potential change. Thus the theorem is trivially true, and we may assume at
least one rotation. We let X be the node involved in the splay. We need to show
that, if r rotations are performed (a zig-zig or zig-zag counts as two rotations),
r plus the change in potential is at most 3 log N + 1. Next, we let Δ be the
change in potential caused by any of the splay steps zig, zig-zag, or zig-zig.
Finally, we let R i ( X ) and S i ( X ) be the rank and size of any node X immediately
before a splay step and R f ( X ) and S f ( X ) be the rank and size of any node X
immediately after a splay step. Following are the bounds that are to be proven.
For a zig step that promotes node X,
Δ
3( R f ( X ) - R i ( X )); for the other
two steps, Δ
3( R f ( X ) - R i ( X )) - 2. When we add these bounds over all the
steps that comprise a splay, the sum telescopes to the desired bound. We prove
each bound separately in Theorems 22.5-22.7. Then we can complete the
proof of Theorem 22.2 by applying a telescoping sum.
Theorem 22.5
3( R f ( X ) - R i ( X )) .
For a zig step,
Δ≤
Proof
As mentioned earlier in this section, the only nodes whose ranks change in a zig step
are X and P . Consequently, the potential change is R f ( X ) - R i ( X ) + R f ( P ) - R i ( P ) .
From Figure 22.4, S f ( P ) < S i ( P ) ; thus it follows that R f ( P ) - R i ( P ) < 0 . Consequently,
the potential change satisfies
Δ≤ R f ( X ) - R i ( X ) . As S f ( X ) > S i ( X ) , it follows that
R f ( X ) - R i ( X ) > 0 ; hence
Δ≤ 3( R f ( X ) - R i ( X )) .
The zig-zag and zig-zig steps are more complicated because the ranks of
three nodes are affected. First, we prove the zig-zag case.
Theorem 22.6
For a zig-zag step, Δ≤3( R f ( X ) - R i ( X )) - 2 .
Proof
As before, we have three changes, so the potential change is given by
Δ
=
R f () R i ()
-
+
R f () R i ()
-
+
R f () R i ()
-
From Figure 22.5,
S f ()
=
S i ()
, so their ranks must be equal. Thus we obtain
Δ
=
-
R
i () R f () R
+
-
i () R f ()
+
(continues next page)
Search WWH ::




Custom Search