Chain Rotations: a New Look at Tree Distance

Details Chain Rotations: a New Look at Tree Distance Chain Rotations: a New Look at Tree Distance

2012-04-26

arxiv.org/abs/1204.5929v1

Computer Science

Data Structures and Algorithms

Scientific paper

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. In terms of n 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 5n/3-4 respectively.

Affiliated with

Also associated with

No associations

Rating

Chain Rotations: a New Look at Tree Distance does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Chain Rotations: a New Look at Tree Distance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chain Rotations: a New Look at Tree Distance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-314478