A Rotation Algortihm based on induced Equivalent Edges

The rotation distance d(S,T) between two rooted binary trees S, T of n vertices is the minimum number of rotations to transform S into T. A basic upper bound of 2n−6 valid for n ≥ 11 has been established in [10], but no efficient algorithm has been found thus far to compute the rotation distance exactly. Let the vertices of S,T be identified with the integers from 1 to n in infix order. Two edges, one in S and one in T, are equivalent if they lead to subtrees containing the same subsets of integers. As known, if equivalent edges exist any optimal rotation algorithm cuts S, T into pieces by deleting such edges and treats the pieces separately. We show that the possibility of forming new equivalent edges with just one rotation is highly beneficial due to the factor 2 applied to n in the upper bound on d(S,T) and prove that such a feature can be detected in linear time. As a consequence we reformulate the upper bound on d(S, T ) and give new lines for designing a rotation algorithm.