Java Reference
In-Depth Information
Moreover, before the first operation the potential is 0, and since it can never
be negative,
Φ
M
-
Φ
0
≥
0
. Consequently, we obtain
M
∑
r
i
≤
(
3
log
N
+
1
)
F
+
(
4
log
N
+
1
)
I
(22.5)
i
=
1
showing that the cost of any sequence of finds and insertions is at most loga-
rithmic per operation. A deletion is equivalent to two splays, so it too is loga-
rithmic. Thus we must prove the two dangling claims—namely, Theorem 22.2
and the fact that an insertion of a node adds at most log
N
to the potential. We
prove both theorems by using telescoping arguments. We take care of the
insertion claim first, as Theorem 22.3.
Theorem 22.3
Insertion of the
N
th node in a tree as a leaf adds at most
log
N
to the potential of the
tree.
The only nodes whose ranks are affected are those on the path from the inserted
leaf to the root. Let
Proof
S
1
S
2
,
,
…
,
S
k
be their sizes prior to the insertion and note that
…
S
k
=
N
1
-
and
S
1
<< <
S
2
S
k
. Let
S
1
S
2
,
,
…
,
S
k
be the sizes after the inser-
tion. Clearly,
S
i
≤
S
i
for
ik
<
, since
S
i
=
S
i
+
1
. Consequently,
R
i
R
i
≤
. The
+
1
+
1
change in potential is thus
k
∑
k
-
1
(
R
i
-
R
i
)
≤
R
k
-
R
k
+
∑
(
R
i
-
R
i
)
≤
log
NR
1
-
≤
log
N
.
+
1
i
=
1
i
=
1
To prove Theorem 22.2, we break each splay step into its constituent zig,
zig-zag, and zig-zig parts and establish a bound for the cost of each type of
rotation. By telescoping these bounds, we obtain a bound for the splay. Before
continuing, we need a technical theorem, Theorem 22.4.
Theorem 22.4
If
ab
+
≤
c
and
a
and
b
are both positive integers, then
log
a
+
log
b
≤
2
log
c
-
2
.
Proof
By the arithmetic-geometric mean inequality,
ab
≤
(
a b
+
)
⁄
2
. Thus
ab c
2
≤
⁄
Squaring both sides gives
ab c
2
≤
⁄
4
. Then taking logarithms of both sides proves
the theorem.
We are now ready to prove Theorem 22.2.
Search WWH ::
Custom Search