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
CMU-CS-05-187.ps
CMU-CS-05-187.pdf
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 This page maintained by reports@cs.cmu.edu
School of Computer Science homepage