1
$\begingroup$

In the 1988 paper Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan and Thurston show that for any pair of $n$-node binary trees, the maximum rotation distance between them is $2n-6$ for all $n \ge 11$.

They also claim that this bound is tight for sufficiently large $n$. I see how they achieved the upper bound of $2n-6$ rotations but I am now trying to understand their proof of the lower bound. To the best of my understanding, their argument relies on triangulating a polyhedron and looking at volumes in hyperbolic space.

I'm having trouble connecting these fairly technical mathematical claims back to actual binary trees. In particular, what would be a concrete example of two binary trees (or families of binary trees) which meet this lower bound and actually require $2n-6$ rotations to transform one tree into the other?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.