CMU-CS-05-187
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-05-187

A Lower Bound Framework for
Binary Search Trees with Rotations

Jonathan Derryberry, Daniel Dominic Sleator, Chengwen Chris Wang

November 2005

CMU-CS-05-187.ps
CMU-CS-05-187.pdf


Keywords: Dynamic optimality, binary search tree, splay tree, competitive algorithms, lower bound


This paper considers the problem of bounding below the cost of accessing a sequence of keys in a binary search tree. We develop a lower bound framework for this problem that applies to any binary search tree algorithm, including self-adjusting and offline ones. This new framework can be used to derive two previously known lower bounds.

11 pages


Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu