Computer Science Department
School of Computer Science, Carnegie Mellon University
Properties of Multi-Splay Trees
Jonathan Derryberry, Daniel Sleator, Chengwen Chris Wang
We show that multi-splay trees have most of the properties that splay trees have. Specifically, we show that multi-splay trees have the following properties: the access lemma, static optimality, the static finger property, the working set property, and key-independent optimality. Moreover, we prove that multi-splay trees have the deque property, which was conjectured by Tarjan in 1985 for splay trees, but remains unproven despite a significant amount of research toward proving it.