A rotation algorithm based on induced equivalent edges
Emilio Del Tessandoro, Fabrizio Luccio, Linda Pagli · Applied Mathematical Sciences · 2014
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 [11], but no efficient algorithm has been found thus far to compute the rotation distance exactly, nor it is known if the problem is NPhard. 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 lines for designing a new rotation algorithm. An extensive set of experiments on trees up to 18 vertices shows that this algorithm gives almost optimal values for the number of rotations. On average such values coincide with the optimum if approximated to the closest integer.