MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


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: (393 KBytes)

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},