有許多的不同方法去衡量二棵有根且具有葉節點個數一樣的二元樹之間其差異性所在。在一棵二元樹上的任一個內部節點做旋轉動作是重新建構成另一棵二元樹的一種機制，在轉換過程中仍維持二元樹原有的中序順序。給定任意二棵二元樹，透過旋轉的動作可以使用最少的旋轉次數將一棵二元樹轉換成另一二元樹，稱之為旋轉距離。不過，到目前為止，給定任意二棵二元樹上尋找其旋轉距離的方法，仍然沒有一個花費多項式時間內解決的演算法。 Lucas在2004年The Computer Journal的期刊發表一篇僅花費n平方次方時間內給定任意二棵二元樹是有加限制的（起始的二元樹內中每一個內部節點最多只有一個小孩；而目地的二元樹呈現最多一次彎折的形狀）可以找到準確的旋轉距離的演算法，當n是任意一棵二元樹的節點個數。

Pallo在1986年The Computer Journal的期刊發表一篇左權重序列(left weight sequences)，這個序列是一個正整數的序列，用它來表示二元樹的結構特性。

首先，我們提供一個演算法，這個演算法是應用AVL tree的旋轉方法來旋轉二棵二元樹的左權重序列，找出它們之間的旋轉距離。

次之，我們在一群二元樹的集合中找到一個限制集合。在這個限制集合裡任意取二棵二元樹，可以找到準確的旋轉距離，並且我們的演算法僅需花費線性時間。同時，確實告知如何做旋轉的步驟順序。

最後，我們介紹一個限制的二元樹集合是由Lucas (The Computer Journal, 47, 259-269, 2004) 所提出，在這群限制的二元樹集合裡任意取二棵做轉換之。我們提供一個線性時間的演算法，在這限制的二元樹集合任意取二棵二元樹去評估它們之間的旋轉距離，也同時告知如何做旋轉的步驟順序。

There are a number of ways to measure the difference in shape between two rooted binary trees with the same number of leaves. A rotation in a binary tree is a local restructuring that changes the tree into another and preserves the inorder sequence. The rotation distance between two binary trees is the minimum number of rotations needed to transform one into another. However, it is still not found a polynomial-time algorithm for computing rotation distances between any two binary trees.
Lucas (The Computer Journal, 47, 259-269, 2004) presented an O(n^2)-time algorithm for finding the exact rotation distance between two binary trees that are of a restricted form (each node has at most one child in the source tree and there is at most one zig-zag pair in the destination tree) where n is the number of nodes in each binary tree.

Pallo (The Computer Journal, 9, 171-175, 1986) introduced a left weight sequence, which is a sequence of positive integers characterizing the structure of a binary tree.

First, by applying the AVL tree transformation on binary trees, we develop an algorithm to transform the left weight sequences between two binary trees.

Secondly, we find another restricted set of binary trees in which any two of them can be transformed with the exact rotation distance. Our algorithm can be performed in linear time for finding the rotation distance between any two trees in the restricted set. Moreover, actual sequence of transforming rotations can also be built.

Finally, we introduce a restricted set of binary trees proposed by Lucas (The Computer Journal, 47, 259-269, 2004) in which any two of them can be transformed. We propose a linear time algorithm to estimate rotation distance between any two trees in the restricted set. Moreover, actual sequence of transforming rotations can also be built.

[1] G. M. Adelson-Velsky and E, M. Landis, An algorithm for organization of information, Soviet Mathematics Doklady, 3 (1962) 1259-1263.

[2] B. L. Allen and M. Steel, Subtree transfer operations and their induced metrics on evolutionary trees, Annals of Combinatorics, 5 (2001) 1-15.

[3] Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcrof, Data Structures and Algorithms, Addison Wesley, 1983.

[4] A. Andersson, General balanced trees, Journal of Algorithms, 30 (1999) 1-18.

[5] J. L. Baril and J. M. Pallo, Efficient lower and upper bounds of the diagonal-flip distance between triangulations, Information Processing Letters, 100 (2006) 131-136.

[6] R. Bayer, Symmetric binary B-trees: data structure and maintenance algorithms, Acta Informatica, 1 (1972) 290-306.

[7] A. Bonnin and J. Pallo, A shortest path metric on unlabeled binary trees, Pattern Recognition Letters, 13 (1992) 411-415.

[8] S. Cleary, Restricted rotation distance between binary trees, Information Processing Letters, 84 (2002) 333-338.

[9] S. Cleary and J. Taback, Bounding restricted rotation distance, Information Processing Letters, 88 (2003) 251-256.

[10] S. Cleary and J. Taback, Bounding right-arm rotation distances, International Journal of Algebra and Computation, 17 (2007) 369-399.

[11] S. Cleary and K. St. John, Rotation distance is fixed-parameter tractable, Information Processing Letters, 109 (2009) 918-922.

[12] C. A. Crane, Linear lists and priority queues as balanced binary trees, Technical Report STAN-CS-72-259, Department of Computer Science, Stanford University, 1972.

[13] K. Culik and D. Wood, A note on some tree similarity measures, Information Processing Letters, 15 (1982) 39-42.

[14] Jayant V. Deshpande, On Continuity of a Partial Order, Proceedings of the American Mathematical Society, 19, No. 2 (1968) 383-386.

[15] Donnellan, Thomas, Lattice Theory, Pergamon, 1968.

[16] R.G. Downey and M.R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.

[17] M. R. Fellows, The lost continent of polynomial time: preprocessing and kernelization, Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, Springer-Verlag Lecture Notes in Computer Science, 4169 (2006), 276-277.

[18] J. Flum and M. Grohe, Parameterized Complexity Theory, Springer-Verlag, 2006.

[19] C. Germain and J. Pallo, The number of coverings in four Catalan lattices, International Journal of Computer Mathematics, 61 (1996) 19-28.

[20] G. Gratzer, Lattice Theory: First concepts and distributive lattices. W. H. Freeman, 1971.
[21] J. Guo and R. Niedermeier, Invitation to data reduction and problem kernelization, ACM SIGACT NEWS, 38 (2007) 31-45.

[22] S. Hanke, T. Ottmann, and S. Schuierer, The edge-flipping distance of triangulations, Journal of Universal Computer Science, 2 (1996) 570-579.

[23] F. Hurtado and M. Noy, Graph of triangulations of a convex polygon and tree of triangulations, Computational Geometry, 13 (1999) 179-188.

[24] F. Hurtado, M. Noy and J. Urrutia, Flipping edges in triangulations, Discrete Computational Geometry, 22 (1999) 333-346.

[25] Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed, Fundamentals of Data Strucures in C, W. H. Freeman, 1992.

[26] D. E. Knuth, Sorting and Searching, in: The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.

[27] J. M. Lucas, The rotation graph of binary trees is hamiltonian, Journal of Algorithms, 8 (1987) 503-535.

[28] J. M. Lucas, D. Roelants van Baronaigien, and F. Ruskey, On rotations and the generation of binary trees, Journal of Algorithms, 15 (1993) 343-366.

[29] J. M. Lucas, A direct algorithm for restricted rotation distance, Information Processing Letters, 90 (2004) 129-134.

[30] J. M. Lucas, Untangling binary trees via rotations, The Computer Journal, 47 (2004) 259-269.

[48] D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees, Journal of the ACM, 32 (1985) 652-686.

[49] 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) 130-137.

[50] D. D. Sleator, R. E. Tarjan, and W. R. Thurston, Rotation distance, triangulations and hyperbolic geometry, Journal of the American Mathematical Society, 1 (1988) 647-681.

[51] R. Sundar, On the deque conjecture for the splay algorithm, Combinatorica, 12 (1992) 95-124.

[52] V. Vajnovszki, On the loopless generation of binary tree sequences, Information Processing Letters, 68 (1998) 113-117.

[53] D. Wang, X. Wang, and S. Li, Diagonal-flip distance algorithms of three type triangulations, International Conference on Computer Science and Software Engineering, (2008) 980-983.

[54] R. Y. Wu, J. M. Chang, and Y. L. Wang, A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations, Theoretical Computer Science, 355 (2006) 303-314.

[55] R. Y. Wu, J. M. Chang, and Y. L. Wang, The Gray-code graph of t-ary trees using RD-sequence is Hamiltonian, Proceedings of the 24st Workshop on Combinatorial Mathematics and Computation Theory, (2007) 44-51.

[56] R.Y. Wu, J. M. Chang, and C. H. Chang, A Developed Restricted Rotation for Binary Trees Transformation, 2009 Ninth International Conference on Hybrid
Intelligent Systems, 1 (2009) 78-83.