As well known the rotation distance D(S,T) between two binary trees S, T of n vertices is the minimum number of rotations of pairs of vertices to transform S into T. We introduce the new operation of chain rotation on a tree, involving two chains of vertices, that requires changing exactly three pointers in the data structure as for a standard rotation, and define the corresponding chain distance C(S,T). As for D(S,T), no polynomial time algorithm to compute C(S,T) is known. We prove a constructive upper bound and an analytical lower bound on C(S,T) based on the number of maximal chains in the two trees. More precisely we prove the general upper bound C(S,T)≤n-1 and we show that there are pairs of trees for which this bound is tight. No similar result is known for D(S,T) where the best upper and lower bounds are 2n-6 and 53n-4 respectively.

Chain Rotations: a New Look at Tree Distance

LUCCIO, FABRIZIO;PAGLI, LINDA
2013

Abstract

As well known the rotation distance D(S,T) between two binary trees S, T of n vertices is the minimum number of rotations of pairs of vertices to transform S into T. We introduce the new operation of chain rotation on a tree, involving two chains of vertices, that requires changing exactly three pointers in the data structure as for a standard rotation, and define the corresponding chain distance C(S,T). As for D(S,T), no polynomial time algorithm to compute C(S,T) is known. We prove a constructive upper bound and an analytical lower bound on C(S,T) based on the number of maximal chains in the two trees. More precisely we prove the general upper bound C(S,T)≤n-1 and we show that there are pairs of trees for which this bound is tight. No similar result is known for D(S,T) where the best upper and lower bounds are 2n-6 and 53n-4 respectively.
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/229337
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact