Speaker: Maverick Woo
Title: Finger Search on Balanced Search Trees
Date: 2006-04-14, Friday
Time: 15:30
Place: Wean 5409
Committee:
Guy E. Blelloch, Carnegie Mellon University, co-chair
Richard Cole, New York University
Bruce M. Maggs, Carnegie Mellon University, co-chair
Daniel Dominic Kaplan Sleator, Carnegie Mellon University
Abstract:
This thesis introduces the concept of a heterogeneous decomposition of a balanced search tree and apply it to the following problems:
* How can finger search be implemented without changing the representation of a Red-Black Tree, such as introducing extra storage to the nodes?
(Answer: Any degree-balanced search tree can support finger search without modification in its representation by maintaining an auxiliary data structure of logarithmic size and suitably modifying the search algorithm to make use of this auxiliary data structure.)
* Do MultiSplay Trees, which is known to be O(log log n)-competitive to the optimal binary search trees, have the Dynamic Finger property?
(Answer: This is work in progress. We believe the answer is yes.)
