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 , 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.

### A Rotation Algortihm based on induced Equivalent Edges

#### Abstract

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 , 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2014
Del Tessandoro, E.; Luccio, Fabrizio; Pagli, Linda
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11568/463670`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

##### Citazioni
• ND
• 0
• 0