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 primar- ily 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.

197 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu