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 [email protected]