如果兩棵二元樹分別為S和T，皆具有相同的節點個數，我們可以利用旋轉的方式，將S轉到T，或者將T轉到S，其中所花的旋轉次數即為S轉到T，或T轉到S的旋轉距離。並且S轉到T，或T轉到S，所花費的旋轉距離次數是最小的。由於樹中的每一個點皆可做旋轉，到目前為止的參考文獻中，尚未找到評估旋轉距離的好方法和得到較佳的時間複雜度。所以我們做一些限制，限制可旋轉的節點必須位於二元樹的邊界上，因此對於任意兩棵具有相同節點個數n的二元樹作轉換，只需要花費線性的時間。並且最多只需花2n-3次數的旋轉距離就可將任意二棵樹作轉換。

In this thesis, we consider a transformation on binary trees, named border rotation, which is a special instance of the well-known rotation transformation. Only rotations at nodes on the border of a binary tree are allowed. Consequently, we develop a linear time algorithm for computing the border rotation distances between any two binary trees, i.e., the minimum number of border rotations necessary to transform one tree into the other. Further, we obtain an upper bound of 2n-3 for the border rotation distance between two binary trees with n interior nodes.

[1] G. M. Adelson-Velsky and E, M. Landis, “An algorithm for organization of information,” Soviet Mathematics Doklady 3 (1962) 1259-1263.
[2] A. Andersson, “General balanced trees,” Journal of Algorithms 30 (1999) 1-18.
[3] R. Bayer, “Symmetric binary B-trees: data structure and maintenance algorithms,” Acta Informatica 1 (1972) 290-306.
[4] S. Cleary, “Restricted rotation distance between binary trees,” Information Processing Letters 84 (2002) 333-338.
[5] S. Cleary and J. Taback, “Bounding restricted rotation distance,” Information Processing Letters 88 (5) (2003) 251-256.
[6] K. Culik and D. Wood, “A note on some tree similarity measures.” Informational Processing Letters 15 (1982) 39-42
[7] D. E. Knuth, Sorting and Searching, in: The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.
[8] J. M. Lucas, “Untangling binary trees via rotations,” The Computer Journal 47 (2004) 259-269.
[9] F. Luccio and L. Pagli, “On the upper bound on the rotation distance of binary tree,” Informational Processing Letters 31 (2) (1989) 57-60.
[10] E. M¨akinen, “On the rotation distance of binary trees,” Information Processing Letters 26 (1987/88) 271-272.
[11] J. Pallo, “An efficient upper bound of the rotation distance of binary trees,” Information Processing Letters 73 (2000) 87-92.

[12] J. Pallo, “Right-arm rotation distance between binary trees,” Information Processing Letters 87 (2003) 173-177.
[13] R. O. Rogers, “On finding shortest paths in the rotation graph of binary trees,” Congressus Numerantium 137 (1999) 77-95.
[14] A. A. Ruiz, F. Luccio, A. M. Enriquez, and L. Pagli, “k-Restricted Rotation with an Application to Search Tree Rebalancing,” WADS 2005, LNCS 3608, pp. 2-13, 2005.
[15] D. D. Sleator and R. E. Tarjan, “Self-adjusting binary search trees,” Journal of the ACM 32 (1985) 652-686.
[16] D. D. Sleator, R. E. Tarjan, and W. R. Thurston, “Rotation distance, in: T.M. Cover, B. Gopinath (Eds.),” Open Problems in Communication and Computation, Springer, Berlin, 1987, pp. 130-137.
[17] D. D. Sleator, R. E. Tarjan and W. R. Thurston, “Rotation distance, triangulations, and hyperbolic geometry,” J. Amer. Math. Soc. 1 (3) (1988) 647-681.
[18] R. Sundar, “On the deque conjecture for the splay algorithm,” Combinatorica 12 (1992) 95-124.