The rotation distance between any two binary trees with the same number of nodes is the minimum number of rotations needed to transform one into the other. With this distance, the set of n-node binary trees becomes a metric space: the distance is symmetric, positive when given two different trees, and satisfies the triangle inequality.
It is an open problem whether there exists a polynomial time algorithm for calculating rotation distance.
Daniel Sleator, Robert Tarjan and William Thurston showed that the rotation distance between any two n-node trees (for n ≥ 11) is at most 2n − 6, and that infinitely many pairs of trees are this far apart.
Read more about this topic: Tree Rotation
Famous quotes containing the words rotation and/or distance:
“The lazy manage to keep up with the earth’s rotation just as well as the industrious.”
—Mason Cooley (b. 1927)
““I see nobody on the road,” said Alice.
“I only wish I had such eyes,” the King remarked in a fretful tone. “To be able to see Nobody! And at that distance too! Why, it’s as much as I can do to see real people, by this light!””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)