Java Reference
In-Depth Information
By changing the potential function, you can prove different bounds
for splaying. Let the weight function
W
(
i
) be some function assigned
to each node in the tree and
S
(
i
) be the sum of the weights of all nodes
in the subtree rooted at
i,
including
i
itself. The special case
W
(
i
) = 1
for all nodes corresponds to the function used in the proof of the
splaying bound. Let
N
be the number of nodes in the tree and
M
be
the number of accesses. Prove the following two theorems.
a.
22.7
The total access time is
O
(
M
+ (
M
+
N
) log
N
).
b.
If
q
i
is the total number of times that item
i
is accessed and
q
i
> 0
for all
i,
then the total access time is
O
(
M
+
Σ
N
q
i
log(
M
/
q
i
)).
i
=
1
IN PRACTICE
22.8
Use the splay tree to implement a priority queue class.
Modify the splay tree to support order statistics.
22.9
PROGRAMMING PROJECTS
22.10
Compare empirically the simplified top-down splay implemented in
Section 22.6 with the original top-down splay discussed in Section
22.5.
Unlike balanced search trees, splay trees incur overhead during a
find
operation that can be undesirable if the access sequence is sufficiently
random. Experiment with a strategy that splays on a
find
operation
only after a certain depth
d
is traversed in the top-down search. The
splay does not move the accessed item all the way to the root, but
rather to the point at depth
d
where the splaying is started.
22.11
Compare empirically a top-down splay tree priority queue implemen-
tation with a binary heap by using
a. Random
insert
and
deleteMin
operations
b.
insert
and
deleteMin
operations corresponding to an event-driven
simulation
c.
insert
and
deleteMin
operations corresponding to Dijkstra's
algorithm
22.12
The splay tree is described in the paper [3]. The concept of amortized analysis
is discussed in the survey paper [4] and also in greater detail in [5]. A compar-
ison of splay trees and AVL trees is given in [1], and [2] shows that splay trees
perform well in some types of event-driven simulations.
Search WWH ::
Custom Search