| Article ID: | iaor2012416 |
| Volume: | 62 |
| Issue: | 3 |
| Start Page Number: | 863 |
| End Page Number: | 878 |
| Publication Date: | Apr 2012 |
| Journal: | Algorithmica |
| Authors: | Fredman Michael |
| Keywords: | search |
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.