Title :
Lower bounds for accessing binary search trees with rotations
Abstract :
We describe two methods 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.
Keywords :
Binary search trees; Binary trees; Costs; Heuristic algorithms; Mirrors;
Conference_Titel :
Foundations of Computer Science, 1986., 27th Annual Symposium on
Conference_Location :
Toronto, ON, Canada
Print_ISBN :
0-8186-0740-8
DOI :
10.1109/SFCS.1986.28
