Java Reference
In-Depth Information
summary
In this chapter we described the splay tree, which is a recent alternative to the
balanced search tree. Splay trees have several remarkable properties that can
be proved, including their logarithmic cost per operation. Other properties are
suggested in the exercises. Some studies have suggested that splay trees can
be used for a wide range of applications because of their apparent ability to
adapt to easy access sequences.
In Chapter 23 we describe two priority queues that, like the splay tree,
have poor worst-case performance but good amortized performance. One of
these, the pairing heap, seems to be an excellent choice for some applications.
key concepts
90-10 rule States 90 percent of the accesses are to 10 percent of the data items.
However, balanced search trees do not take advantage of this rule. (844)
amortized analysis Bounds the cost of a sequence of operations and distributes
the cost evenly to each operation in the sequence. (845)
bottom-up splay tree A tree in which items are rotated to the root by using a
slightly more complicated method than that used for a simple rotate-to-
root strategy. (847)
potential function An accounting device used to establish an amortized time
bound. (851)
rank In the splay tree analysis, the logarithm of a node's size. (851)
rotate-to-root strategy Rearranges a binary search tree after each access so as
to move frequently accessed items closer to the root. (846)
splaying A rotate-to-root strategy that allows the logarithmic amortized bound
to be obtained. (847)
top-down splay tree A type of splay tree that is more efficient in practice than
its bottom-up counterpart, as was the case for red-black trees. (857)
zig and zig-zag Cases that are identical to the rotate-to-root cases. Zig is used
when X is a child of the root, and zig-zag is used when X is an inside
(grandchild) node. (848)
zig-zig A case unique to the splay tree, which is used when X is an outside
(grandchild) node. (848)
 
 
Search WWH ::




Custom Search