Rotation distances measure the difference in shape in rooted binary trees. We construct sharp bounds on maximal right-arm rotation distance and restricted right-arm rotation distance for trees of size n. These bounds sharpen the results of Cleary and Taback and incorporate the lengths of the right side of the trees to improve the bounds.
Refined upper bounds for right-arm rotation distance
LUCCIO, FABRIZIO;PAGLI, LINDA
2007-01-01
Abstract
Rotation distances measure the difference in shape in rooted binary trees. We construct sharp bounds on maximal right-arm rotation distance and restricted right-arm rotation distance for trees of size n. These bounds sharpen the results of Cleary and Taback and incorporate the lengths of the right side of the trees to improve the bounds.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.