Effective splaying with restricted rotations

References

• Adelson-Velskii , G. M. and Landis , E. M. 1962 . An algorithm for the organization of information . Soviet Mathematics - Doklady , 3 : 1259 – 1262 .
   Google Scholar
• Andersson , A. 1999 . General balanced trees . Journal of Algorithms , 30 : 1 – 18 .
   Web of Science ®Google Scholar
• Bayer , R. 1972 . Symmetric binary B-trees: data structure and maintenance algorithms . Acta Informatica , 1 : 290 – 306 .
   Google Scholar
• Guibas , L. J. and Sedgewick , R. A dichromatic framework for balanced trees . New York. Proceedings of the 19th Annual Symposium on Foundations of Computer Scienc , pp. 8 – 21 . IEEE Computer Society Press .
   Google Scholar
• Larsen , K. S. , Soisalon-Soininen , E. and Widmayer , P. 2001 . Relaxed balance using standard rotations . Algorithmica , 31 : 501 – 512 .
   Google Scholar
• Mahmoud , H. 1998 . On rotations in fringe-balanced binary trees . Information Processing Letters , 65 : 41 – 46 .
   Google Scholar
• Mehlhorn , K. 1979 . Dynamic binary search trees . SIAM Journal on Computing , 8 : 175 – 198 .
   Google Scholar
• Nievergelt , J. and Reingold , E. M. 1973 . Binary search trees of bounded balance . SIAM Journal on Computing , 2 : 33 – 43 .
   Google Scholar
• Sleator , D. D. and Tarjan , R. E. 1985 . Self-adjusting binary search trees . Journal of the ACM , 32 : 652 – 686 .
   Web of Science ®Google Scholar
• Sleator , D. D. , Tarjan , R. E. and Thurston , W. 1988 . Rotation distance, triangulations and hyperbolic geometry . Journal of the American Mathematical Society , 1 : 647 – 681 . 3
   Google Scholar
• Pallo , J. M. 1986 . Enumerating, ranking and unranking binary trees . The Computer Journal , 29 : 171 – 175 .
   Web of Science ®Google Scholar
• Pallo , J. M. 1987 . On the rotation distance in the lattice of binary trees . Information Processing Letters , 25 : 369 – 373 .
   Google Scholar
• Pallo , J. M. 1988 . Some properties of the rotation lattice of binary trees . The Computer Journal , 31 : 564 – 565 .
   Google Scholar
• Sundar , R. 1992 . On the deque conjecture for the splay algorithm . Combinatorica , 12 : 95124
   Google Scholar
• Bonnin , A. and Pallo , J. M. 1992 . A shortest path metric on unlabeled binary trees . Pattern Recognition Letters , 13 : 411 – 415 .
   Google Scholar
• Pallo , J. M. 2003 . Right-arm rotation distance between binary trees . Information Processing Letters , 87 : 173 – 177 .
   Google Scholar
• Ruiz , A. , Luccio , F. , Enriquez , A. and Pagli , L. 2005 . k-restricted Rotation with an Application to Search Tree Rebalancing. Proceedings of the 9th International Workshop on Algorithms and Data Structures . Lecture Notes in Comptuer Science , 3608 : 2 – 13 .
   Google Scholar
• Chen , Y. , Chang , J. and Wang , Y. 2005 . An efficient algorithm for estimating rotation distance between two binary trees . International Journal of Computer Mathematics , 82 : 1095 – 1106 . 9
   Web of Science ®Google Scholar
• Wu , R. , Chang , J. and Wang , Y. 2006 . A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations . Theoretical Computer Science , 355 : 303 – 314 .
   Google Scholar
• Cleary , S. 2002 . Restricted rotation distance between binary trees . Information Processing Letters , 84 : 333 – 338 .
   Google Scholar
• Cleary , S. and Taback , J. 2003 . Bounding restricted rotation distance . Information Processing Letters , 88 : 251 – 256 .
   Google Scholar
• Lucas , J. M. 2004 . A direct algorithm for restricted rotation distance . Information Processing Letters , 90 ( 3 ) : 129 – 134 .
   Google Scholar