A Linear-Time Approximation Algorithm for Rotation Distance
Sean Cleary, Katherine St. John · DOAJ (DOAJ: Directory of Open Access Journals) · 2010
Rotation distance between rooted binary trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. In this short note, we give an efficient, linear-time approximation algorithm, which estimates the rotation distance, within a provable factor of 2, between ordered rooted binary trees.