An efficient algorithm for estimating rotation distance between two binary trees

References

• Adelson-Velsky , G. M. and Landis , E. M. 1962 . An algorithm for organization of information . Soviet Mathematics—Doklady , 3 : 1259 – 1263 .
   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
• 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
• Culik , K. and Wood , D. 1982 . A note on some tree similarity measures . Information Processing Letters , 15 : 39 – 42 .
   Google Scholar
• Germain , C. and Pallo , J. 1996 . The number of coverings in four Catalan lattices . International Journal of Computer Mathematics , 61 : 19 – 28 .
   Web of Science ®Google Scholar
• Lucas , J. M. 1987 . The rotation graph of binary trees is hamiltonian . Journal of Algorithms , 8 : 503 – 535 .
   Web of Science ®Google Scholar
• Lucas , J. M. , Roelants van Baronaigien , D. and Ruskey , F. 1993 . On rotations and the generation of binary trees . Journal of Algorithms , 15 : 343 – 366 .
   Web of Science ®Google Scholar
• Vajnovszki , V. 1998 . On the loopless generation of binary tree sequences . Information Processing Letters , 68 : 113 – 117 .
   Google Scholar
• Sleator , D. D. , Tarjan , R. E. and Thurston , W. R. 1988 . Rotation distance, triangulations and hyperbolic geometry . Journal of the American Mathematical Society , 1 : 647 – 681 .
   Google Scholar
• Hurtado , F. and Noy , N. 1999 . Graph of triangulations of a convex polygon and tree of triangulations . Computational Geometry , 13 : 179 – 188 .
   Web of Science ®Google Scholar
• Pallo , J. 1986 . Enumerating, ranking and unranking binary trees . Computer Journal , 29 : 171 – 175 .
   Web of Science ®Google Scholar
• Pallo , J. 1987 . On the rotation distance in the lattice of binary trees . Information Processing Letters , 25 : 369 – 373 .
   Google Scholar
• Pallo , J. 1988 . Some properties of the rotation lattice of binary trees . Computer Journal , 31 : 564 – 565 .
   Google Scholar
• Pallo , J. 2003 . Generating binary trees by Glivenko classes on Tamari lattices . Information Processing Letters , 85 : 235 – 238 .
   Google Scholar
• Sleator , D. D. , Tarjan , R. E. and Thurston , W. R. 1987 . “ Rotation distance ” . In Open Problems in Communication and Computation , Edited by: Cover , T. M. and Gopinath , B. 130 – 137 . Berlin : Springer .
   Google Scholar
• Pallo , J. 2000 . An efficient upper bound of the rotation distance of binary trees . Information Processing Letters , 73 : 87 – 92 .
   Web of Science ®Google Scholar
• Rogers , R. O. 1999 . On finding shortest paths in the rotation graph of binary trees . Congressus Numerantium , 137 : 77 – 95 .
   Google Scholar
• Luccio , F. and Pagli , L. 1989 . On the upper bound on the rotation distance of binary trees . Information Processing Letters , 31 : 57 – 60 .
   Google Scholar
• Mäkinen , E. 1987/88 . On the rotation distance of binary trees . Information Processing Letters , 26 : 271 – 272 .
   Google Scholar
• Hanke , S. , Ottmann , T. and Schuierer , S. 1996 . The edge-flipping distance of triangulations . Journal of Universal Computer Science , 2 : 570 – 579 .
   Google Scholar
• Hurtado , F. , Noy , M. and Urrutia , J. 1999 . Flipping edges in triangulations . Discrete Computational Geometry , 22 : 333 – 346 .
   Google Scholar
• Rogers , R. O. and Dutton , R. D. 1995 . Properties of the rotation graph of binary trees . Congressus Numerantium , 109 : 51 – 63 .
   Google Scholar
• Rogers , R. O. and Dutton , R. D. 1996 . On distance in the rotation graph of binary trees . Congressus Numerantium , 120 : 103 – 113 .
   Google Scholar
• Bonnin , A. and Pallo , J. 1992 . A shortest path metric on unlabeled binary trees . Pattern Recognition Letters , 13 : 411 – 415 .
   Google Scholar
• Sundar , R. 1992 . On the deque conjecture for the splay algorithm . Combinatorica , 12 : 95 – 124 .
   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 : 129 – 134 .
   Google Scholar
• Pallo , J. 2003 . Right-arm rotation distance between binary trees . Information Processing Letters , 87 : 173 – 177 .
   Google Scholar
• Lucas , J. M. 2004 . Untangling binary trees via rotations . Computer Journal , 47 : 259 – 269 .
   Google Scholar
• Knuth , D. E. 1973 . “ Sorting and searching ” . In The Art of Computer Programming , Vol. 3 , Reading, MA : Addison-Wesley .
   Google Scholar