Generalizing a Theorem of Wilber on Rotations in Binary Search Trees to Encompass Unordered Binary Trees

摘要

Wilber's logarithmic lower bound, concerning off-line binary search tree access costs, is generalized to encompass binary trees that are not constrained to satisfy the search tree property. Rotation operations in this extended model can be preceded by subtree swaps. A separation between the power of processing with search trees versus unordered trees is demonstrated.