Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


A survey of self-organizing data structures

Albers, Susanne and Westbrook, Jeffery

MPI-I-96-1-026. October 1996, 39 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-96-1-026.ps393 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  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},