Computer Science Department
School of Computer Science, Carnegie Mellon University


A Lower Bound Framework for
Binary Search Trees with Rotations

Jonathan Derryberry, Daniel Dominic Sleator, Chengwen Chris Wang

November 2005

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