An efficient algorithm for estimating rotation distance between two binary trees
Yen-Ju Chen, Jou–Ming Chang, Yue-Li Wang · International Journal of Computer Mathematics · 2005
There are a number of ways of measuring the difference in shape between two rooted binary trees with the same number of leaves. Pallo (Computer Journal, 9, 171–175, 1986) introduced a left weight sequence, which is a sequence of positive integers, to characterize the structure of a binary tree. By applying the AVL tree transformation on binary trees, we develop an algorithm for the efficient transformation of the left weight sequences between two binary trees.