非表示:
キーワード:
-
要旨:
This paper surveys results in the design and analysis of self-organizing
data structures for the search problem. We concentrate on two simple but
very popular data structures: the unsorted linear list and the binary search
tree. A self-organizing data structure has a rule or algorithm for
changing pointers or state data. The self-organizing rule is designed to
get the structure into a good state so that future operations can be
processed efficiently. Self-organizing data structures differ from constraint
structures in that no structural invariant, such as a balance constraint in
a binary search tree, has to be satisfied.
In the area of self-organizing linear lists we present a series of
deterministic and randomized on-line algorithms. We concentrate on
competitive algorithms, i.e., algorithms that have a guaranteed performance
with respect to an optimal offline algorithm.
In the area of binary search trees we present both on-line and off-line
algorithms. We also discuss a famous self-organizing
on-line rule called splaying and present important theorems and
open conjectures on splay trees. In the third part of the paper we show
that algorithms for self-organizing lists and trees can be used to build
very effective data compression schemes. We report on theoretical
and experimental results.
