Java Reference
In-Depth Information
chapter
22
I
n this chapter we describe a remarkable data structure called the
splay tree,
which supports all the binary search tree operations but does not guarantee
O
(log
N
) worst-case performance. Instead, its bounds are
amortized,
meaning
that, although individual operations can be expensive, any sequence of opera-
tions is guaranteed to behave as though each operation in the sequence exhib-
ited logarithmic behavior. Because this guarantee is weaker than that provided
by balanced search trees, only the data and two links per node are required for
each item and the operations are somewhat simpler to code. The splay tree has
some other interesting properties, which we reveal in this chapter.
In this chapter, we show
The concepts of amortization and self-adjustment
n
The basic bottom-up splay tree algorithm and a proof that it has loga-
rithmic amortized cost per operation
n
Implementation of splay trees with a top-down algorithm, using a
complete splay tree implementation (including a deletion algorithm)
n
Comparisons of splay trees with other data structures
n
Search WWH ::
Custom Search