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 do believe that the outward and the inward life correspond; that if any should succeed to live a higher life, others would not know of it; that difference and distance are one. To set about living a true life is to go on a journey to a distant country, gradually to find ourselves surrounded by new scenes and men; and as long as the old are around me, I know that I am not in any true sense living a new or a better life.”
—Henry David Thoreau (1817–1862)