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.
- 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.
- 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)