Bounding restricted rotation distance |
| |
Authors: | Sean Cleary Jennifer Taback |
| |
Affiliation: | a Department of Mathematics, City College of CUNY, New York, NY 10031, USA b Department of Mathematics and Statistics, University at Albany, Albany, NY 12222, USA |
| |
Abstract: | 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. |
| |
Keywords: | Algorithms Data structures Binary trees Rotation distance |
本文献已被 ScienceDirect 等数据库收录! |
|