Algorithms Seminar Summer 2001

Real world accesses to data structures are generally not random, instead they typically exhibit various types of patterns. Some items may be accessed much more frequently than others. Accesses may also exhibit locality of reference whereby an access is close to a recent access. If information about the distribution of accesses is known, methods exist to construct data structures optimized for the distribution. However, in real applications, we may know that the access pattern will probably not be random, but we seldom know in advance exactly what distributional characteristics that the access pattern will have. Surprisingly, it is possible to design data structures that know nothing about the access distribution and yet perform asymptotically as well as those that know and have been optimized for a particular distribution. The best known such structure was the splay trees of Sleator and Tarjan. In this talk we will present the various theorems and conjectures, both new and old, surrounding splay trees. A brief overview of related structures will be also be presented.