CMU-CS-09-171
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-09-171

Properties of Multi-Splay Trees

Jonathan Derryberry, Daniel Sleator, Chengwen Chris Wang

November 2009

CMU-CS-09-171.pdf


Keywords: Dynamic optimality, binary search trees, competitive algorithms

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.

18 pages


Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu