Shan Leung Woo

Heterogeneous Decomposition of Degree-Balanced Search Trees and Its Applications Degree Type: Ph.D. in Computer Science
Advisor(s): Guy E. Blelloch, Bruce M. Maggs
Graduated: August 2009

Abstract:

This thesis introduces the concept of heterogeneous decompositions of a degree-balanced search tree and applies this concept to establish the following three results.

(1) Any leaf-store or node-store degree-balanced search tree can support a constant number of dynamic fingers in the worst case without storing extra pointers in its nodes nor restructuring after a finger search. Each dynamic finger is represented as a logarithmic-sized data structure that contains pointers pointing into the tree, which is maintained using dictionary algorithms that exploit this representation of dynamic fingers.

(2) By construction, there exists a static binary search tree algorithm with the dynamic finger property in the worst case. This algorithm is primarily intended to serve as an alternate proof that the dynamic optimality conjecture implies the dynamic finger conjecture–in view of the fact that the earlier explicit proof of this implication is the highly-nontrivial proof of the dynamic finger theorem due to Cole.

(3) By construction, there exists a static O(lg lg n)-competitive binary search tree algorithm with the dynamic finger property in the amortized case. As a corollary, if the splay trees of Sleator and Tarjan are O(1)-competitive even in the presence of splits and joins, then the multi-splay trees of Wang, Derryberry, and Sleator have the dynamic finger property in the amortized case.

Thesis Committee:
Guy E. Blelloch (Co-Chair)
Bruce M. Maggs (Co-Chair)
Daniel D. Sleator
Richard Cole (New York University)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science