MPI-I-96-1-026
A survey of self-organizing data structures
Albers, Susanne and Westbrook, Jeffery
October 1996, 39 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-96-1-026.ps (393 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1996-1-026
BibTeX
@TECHREPORT{AlbersWestbrook96,
AUTHOR = {Albers, Susanne and Westbrook, Jeffery},
TITLE = {A survey of self-organizing data structures},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-96-1-026},
MONTH = {October},
YEAR = {1996},
ISSN = {0946-011X},
}