de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

A survey of self-organizing data structures

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43989

Albers,  Susanne
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

1996-1-026
(Any fulltext), 11KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Albers, S., & Westbrook, J.(1996). A survey of self-organizing data structures (MPI-I-1996-1-026). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A03D-0
Abstract
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.