Java Reference
In-Depth Information
Theorem 22.2
If the
i
th splay operation uses
r
i
rotations,
Φ
i
-
Φ
i
+
r
i
≤
3
log
N
+
1
.
-
1
Before proving Theorem 22.2, let us determine what it means. The cost of
M
splays can be taken as rotations. If the
M
splays are consecutive
(i.e., no insertions or deletions intervene), the potential of the tree after the
i
th
splay is the same as prior to the (
i
+ 1)th splay. Thus we can use Theorem 22.2
M
times to obtain the following sequence of equations:
In all the proofs in
this section we use
the concept of tele-
scoping sums.
∑
r
i
M
i
=
1
Φ
1
-
Φ
0
+
r
1
≤
3
log
N
+
1
Φ
2
-
Φ
1
+
r
2
≤
3
log
N
+
1
Φ
3
-
Φ
2
+
r
3
≤
…
3
log
N
+
1
(22.1)
Φ
M
-
Φ
M
1
+
r
M
≤
3
log
N
+
1
-
These equations telescope, so if we add them, we obtain
Φ
M
-
Φ
0
+
∑
M
r
i
≤
(
3
log
N
+
1
)
M
(22.2)
i
=
1
which bounds the total number of rotations as
M
∑
r
i
≤
(
3
log
N
+
1
)
M
-
(
Φ
M
-
Φ
0
)
i
=
1
Now consider what happens when insertions are intermingled with find
operations. The potential of an empty tree is 0, so when a node is inserted in
the tree as a leaf, prior to the splay the potential of the tree increases by at
most log
N
(which we prove shortly). Suppose that
r
i
rotations are used for an
insertion and that the potential prior to the insertion is . After the inser-
tion, the potential is at most . After the splay that moves the
inserted node to the root, the new potential will satisfy
Φ
i
-
1
Φ
i
+
log
N
-
1
Φ
i
-
(
Φ
i
+
log
N
)
+
r
i
≤
3
log
N
+
1
-
1
(22.3)
Φ
i
-
Φ
i
+
r
i
≤
4
log
N
+
1
-
1
Suppose further that there are
F
finds and
I
insertions and that represents
the potential after the
i
th operation. Then, because each
find
is governed by
Theorem 22.2 and each insertion is governed by Equation 22.3, the telescop-
ing logic indicates that
Φ
i
M
r
i
≤
(
3
log
N
+
1
)
F
+
(
4
log
N
+
1
)
I
-
(
Φ
M
-
Φ
0
)
∑
(22.4)
i
=
1
Search WWH ::
Custom Search