An efficient algorithm for estimating rotation distance between two binary trees

Abstract

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.

Keywords:

• Binary trees
• Rotation distance
• AVL trees
• Algorithms