CMU-CS-06-140
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-06-140

Multi-Splay Trees

Chengwen Chris Wang

July 2006

Ph.D. Thesis

CMU-CS-06-140.ps
CMU-CS-06-140.pdf

Keywords: Binary search tree, competitive algorithm, dynamic finger, deque, dynamic optimality, splay tree, Tango

In this thesis, we introduce a new binary search tree data structure called multi-splay tree and prove that multi-splay trees have most of the useful properties different binary search trees (BSTs) have. First, we demonstrate a close variant of the splay tree access lemma [ST85] for multi-splay trees, a lemma that implies multi-splay trees have the O(log n) runtime property, the static finger property, and the static optimality property. Then, we extend the access lemma by showing the remassing lemma, which is similar to the reweighting lemma for splay trees. The remassing lemma shows that multi-splay trees satisfy the working set property and key-independent optimality, and multi-splay trees are competitive to parametrically balanced trees, as defined in [Geo04]. Furthermore, we also prove that multi-splay trees achieve the O(log log n)-competitiveness and that sequential access in multi-splay trees costs O(n).

Then we naturally extend the static model to allow insertions and deletions and show how to carry out these operations in multi-splay trees to achieve O(log log n)-competitiveness, a result no other BST scheme has been proved to have. In addition, we prove that multi-splay trees satisfy the deque property, which is still an open problem for splay trees since it was conjectured in 1985. While it is easy to construct a BST that satisfies the deque property trivially, no other BST scheme satisfying other useful properties has been proved to have deque property. In summary, these results show that multisplay trees have most of the important properties satisfied by different binary search trees.

98 pages


Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu