Bounding restricted rotation distance
Restricted rotation distance between pairs of rooted binary trees quantifies differences in tree shape. Cleary exhibited a linear upper bound of 12n for the restricted rotation distance between two trees with n interior nodes, and a lower bound of (n - 1)/3 if the two trees satisfy a reduction condition. We obtain a significantly improved sharp upper bound of 4n - 8 for restricted rotation distance between two rooted binary trees with n interior nodes, and a significantly improved sharp lower bound of n - 2, again with the requirement that the trees satisfy a reduction condition. These improvements use work of Fordham to compute the word metric in Thompson's group F. (C) 2003 Elsevier B.V. All rights reserved.
rotation distance binary trees algorithms data structures