On the Dynamic Finger Conjecture for Splay Trees Part I: Splay Sorting log n-Block Sequences
Richard Cole, B. K. Mishra, Jeanette P. Schmidt, Aaron N. Siegel · 1995
A special case of the Dynamic Finger Conjecture is proved; this special case introduces a number of useful techniques. 1 Introduction The splay tree is a self-adjusting binary search tree devised by Sleator and Tarjan [ST85]. It supports the operations search, insert and delete, collectively called accesses. The splay tree is simply a binary search tree; each access will cause some rotations to be performed on the tree. Sleator and Tarjan showed that a sequence of m accesses performed on a splay tree takes time O(m log n), where n is the maximum size attained by the tree (n m). They also showed that in an amortized sense, up to a constant factor, on sufficiently long sequences of searches, the splay tree has as good a running time as the optimal weighted binary search tree. In addition, they conjectured that its performance is, in fact, essentially as good as that of any search tree. Before discussing these conjectures it will be helpful to review the operation of the splay tree an...