首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号