Chengwen Chris Wang

Multi-Splay Trees Degree Type: Ph.D. in Computer Science
Advisor(s): Daniel Sleator
Graduated: August 2006

Abstract:

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.

Thesis Committee:
Daniel Sleator (Chair)
Manuel Blum
Gary Miller
Robert Tarjan (Princeton University)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

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