Results and problems on self-adjusting search trees and related data structures

The splay tree is a form of self-adjusting search tree invented almost 25 years ago. Splay trees are remarkably efficient in both theory and practice, but many questions concerning splay trees and related data structures remain open. Foremost among these is the dynamic optimality conjecture, which states that the amortized efficiency of splay trees is optimum to within a constant factor among all kinds of binary search trees. That is, are splay trees constant-competitive? A broader question is whether there is any form of binary search tree that is constant-competitive. Recently, three different groups of researchers have devised kinds of search trees that are loglog-competitive, improving on the logcompetitiveness of balanced trees. At least one of these data structures, the multisplay tree, has many if not all of the nice asymptotic properties of splay trees (even though it is more complicated than splay trees). We review this recent work and look at remaining open problems, of which there are many, including resolving the question of whether splay trees themselves are loglog-competitive. We also look at a more complicated class of data structures that maintain information about a dynamic collection of disjoint trees. We review various versions of the dynamic trees problem, describe efficient solutions (both worst-case and amortized), and list open problems.