Abstract (Susanne Albers)

In this talk we survey results on 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 binary search trees, has to be satisfied.

Of particular interest are self-organizing algorithms that work online, i.e., without knowledge of any future operations.

  1. In the area of self-organizing linear lists we present a series of deterministic and randomized online algorithms. We concentrate on competitive algorithms, i.e., algorithms that have a guaranteed performance with respect to an optimal offline algorithm.
  2. Regarding binary search trees, we mostly focus on a self-organizing online rule called splaying. We show how to analyze splay trees and present important theorems and open conjectures. We also discuss the practical efficiency of splay trees.
In the third part of the talk we show that online algorithms for self-organizing lists and trees can be used to build very effective data compression schemes. We report on theoretical and experimental results.

This talk is based on a survey article written together with Jeffery Westbrook (Yale University).


Last modified: August 30, 1996.
Kim Skak Larsen (kslarsen@imada.sdu.dk)