Jonathan Carlyle Derryberry

Adaptive Binary Search Trees Degree Type: Ph.D. in Computer Science
Advisor(s): Daniel Sleator, Chengwen Chris Wang
Graduated: December 2009

Abstract:

A ubiquitous problem in the field of algorithms and data structures is that of searching for an element from an ordered universe. The simple yet powerful binary search tree (BST) model provides a rich family of solutions to this problem. Although BSTs require Ω(lg n) time per operation in the worst case, various adaptive BST algorithms are capable of exploiting patterns in the sequence of queries to achieve tighter, input-sensitive, bounds that can be o(lg n) in many cases. This thesis furthers our understanding of what is achievable in the BST model along two directions.

First, we make progress in improving instance-specific lower bounds in the BST model. In particular, we introduce a framework for generating lower bounds on the cost that any BST algorithm must pay to execute a query sequence, and we show that this framework generalizes previous lower bounds. This suggests that the optimal lower bound in the framework is a good candi- date for being tight to within a constant factor of the optimal BST algorithm for each input. Further, we show that lower bounds in this framework are also valid lower bounds for instances of the partial-sums problem in a restricted model of computation, which suggests that augmented BSTs may be the most efficient way of maintaining sums over ranges of an array when the entries of the array can be updated throughout time.

Second, we improve the input-sensitive upper bounds that are known to be achievable in the BST model by introducing two new BST algorithms, skip-splay and cache-splay. These two algorithms are the first BSTs that are known to have running times that have nontrivial competitiveness to Iacono’s Unified Bound, which is a generalization of the dynamic finger and working set bounds. Skip-splay is a simple algorithm that is nearly identical to splaying, and it achieves a running time that is within additive O(lg lg n) per operation of the Unified Bound. Cache-splay is a slightly more complicated splay-based algorithm that is the first BST to achieve the Unified Bound to within a constant factor.

Thesis Committee:
Daniel Sleator (Chair)
Guy Blelloch
Gary Miller
Seth Pettie (U. Michigan)

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

Keywords:
binary search trees, adaptive algorithms, splay trees, Unified Bound, dynamic optimality, BST model, lower bounds, partial-sums