LOWER BOUNDS FOR ACCESSING BINARY SEARCH TREES WITH ROTATIONS.

Abstract

Two methods are described for obtaining lower bounds on the cost of accessing a sequence of nodes of a symmetrically ordered binary search tree, where rotations can be done on the tree. The bounds apply to offline as well as online algorithms.