Alternatives to splay trees with O(log n) worst-case access times

Splay trees are a self adjusting form of search tree that supports access operations in &Ogr;(log n) amortized time. Splay trees also have several amazing distribution sensitive properties, the strongest two of which are the working set theorem and the dynamic finger theorem. However, these two theorems are shown to poorly bound the performance of splay trees on some simple access sequences. The unified conjecture is presented, which subsumes the working set theorem and dynamic finger theorem, and accurately bounds the performance of splay trees over some classes of sequences where the existing theorems' bounds are not tight. While the unified conjecture for splay trees is unproven, a new data structure, the unified structure, is presented where the unified conjecture does hold. This structure also has a worst case of &Ogr;(log n) per operation, in contrast to the &Ogr;(n) worst case runtime of splay trees. A second data structure, the working set structure, is introduced. The working set structure has the same performance attributed to splay trees through the working set theorem, except the runtime is worst case per operation rather than amortized.