Java Reference
In-Depth Information
The technique of amortized analysis is very interesting, and some general
principles have been developed to formalize the framework. Check the refer-
ences for more details.
top-down splay trees
22.5
A direct implementation of the bottom-up splay strategy requires a pass
down the tree to perform an access and then a second pass back up the tree.
These passes can be made by maintaining parent links, by storing the access
path on a stack, or by using a clever trick to store the path (using the avail-
able links in the accessed nodes). Unfortunately, all these methods require
expending a substantial amount of overhead and handling many special
cases. Recall from Section 19.5 that implementing search tree algorithms
with a single top-down pass is a better approach and we can use dummy
nodes to avoid special cases. In this section we describe a top-down splay
tree that maintains the logarithmic amortized bound, is faster in practice,
and uses only constant extra space. It is the method recommended by the
inventors of the splay tree.
The basic idea behind the top-down splay tree is that, as we descend the
tree searching for some node X, we must take the nodes that are on the access
path and move them and their subtrees out of the way. We must also perform
some tree rotations to guarantee the amortized time bound.
As for red-black
trees, top-down
splay trees are
more efficient in
practice than their
bottom-up counter-
parts.
At any point in the middle of the splay, a current node X is the root of its
subtree; it is represented in the diagrams as the middle tree. Tree L stores
nodes that are less than X; similarly, tree R stores nodes that are larger than X .
Initially, X is the root of T, and L and R are empty. Descending the tree two
levels at a time, we encounter a pair of nodes. Depending on whether these
nodes are smaller or larger than X, we place them in L or R, along with sub-
trees that are not on the access path to X . Thus the current node on the search
path is always the root of the middle tree. When we finally reach X, we can
then attach L and R to the bottom of the middle tree. As a result, X has been
moved to the root. The remaining tasks then are to place nodes in L and R and
to perform the reattachment at the end, as illustrated in the trees shown in
Figure 22.9. As is customary, three symmetric cases are omitted.
In all the diagrams, X is the current node, Y is its child, and Z is a grand-
child (should an applicable node exist). (The precise meaning of the term
applicable is made clear during the discussion of the zig case.)
If the rotation should be a zig, the tree rooted at Y becomes the new root of
the middle tree. Node X and subtree B are attached as a left child of the smallest
We maintain three
trees during the
top-down pass.
 
 
Search WWH ::




Custom Search