The rotation distance d(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). Rotation distance, Lower bound, Binary tree, Design of algorithms.
Lower Bounds on the Rotation Distance of Binary Trees
LUCCIO, FABRIZIO;PAGLI, LINDA
2010-01-01
Abstract
The rotation distance d(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). Rotation distance, Lower bound, Binary tree, Design of algorithms.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
