Lower bounds on the rotation distance of binary trees |
| |
Authors: | Fabrizio Luccio Antonio Mesa Enriquez |
| |
Affiliation: | a Dipartimento di Informatica, Università di Pisa, Italy b Facultad de Matemàtica y Computación, Universidad de la Habana, Cuba |
| |
Abstract: | The rotation distanced(S,T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T. While it is known that d(S,T)?2n−6, a well-known conjecture states that there are trees for which this bound is sharp for any value of n?11. We are unable to prove the conjecture, but we give here some simple criteria for lower bound evaluation, leading for example to individuate some “regular” tree structures for which d(S,T)=3n/2−O(1), or d(S,T)=5n/3−O(1). |
| |
Keywords: | Rotation distance Lower bound Binary tree Design of algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|