13
$\begingroup$

Two binary search trees are said to be linearly equivalent when they agree in their in-order traversals. The following theorem explains why tree rotations are so fundamental:

Let A and B be binary search trees. Then A and B are linearly equivalent if and only if they are connected by a sequence of tree rotations.

I noticed this result when I was first learning about data structures long ago and wanted to understand the special status of tree rotations more deeply.

The proof is simple and intuitive: Rotate the least element up to the root position along the leftward spine. By the order invariant, this rearranged tree cannot have a left subtree. Now recurse on the right subtree. The result is a normal form for testing linear equivalence.

While it's a basic theorem, I've never come across it in the literature. I would greatly appreciate a reference for the next time I need to use this result.

(Bonus brain teaser: What's the best algorithm for finding the shortest sequence of tree rotations that connect two linearly equivalent binary search trees?)

Improve this question
$\endgroup$
1
  • $\begingroup$ Another place to look might be for a reference that equivalence modulo an associative operator is decidable, as this amounts to the same thing. However, all the references that I'm aware of take this fact for granted. $\endgroup$
    – Rob Simmons
    Oct 29, 2010 at 13:38

4 Answers 4

Reset to default
10
$\begingroup$

As David Eppstein points out here, even finding the shortest path for binary trees is not known to be in P. In the comments to that answer he links to the best current bounds

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm accepting this answer since I learned something from it. However, I'd still love to find a reference for the structure theorem if anyone knows one. $\endgroup$
    – Per Vognsen
    Sep 26, 2010 at 11:58
11
$\begingroup$

An early paper that made this observation explicitly -- that rotations preserve inorder traversals -- is (in Figure 2 of) Sleator and Tarjan's 1983 Self-adjusting binary search trees. The move-to-root heuristic was studied in Allen and Munro's 1978 Self-Organizing Binary Search Trees paper.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The interesting direction in Per's equivalence is not that rotations preserve in-order, but that you can travel in-between any two trees that have the same in-order using rotations. $\endgroup$
    – Radu GRIGore
    Sep 23, 2010 at 14:39
  • $\begingroup$ Yes - that's why I included the move-to root. There's also another paper by Sleator, Tarjan, & Thurston (Rotation Distance, Triangulations, and Hyperbolic Geometry) computing the distances between any two trees, which I didn't include in my answer. I don't think that Per's observation appears in any one paper as is, but I'd love to be proven wrong. $\endgroup$
    – Lev Reyzin ♦
    Sep 23, 2010 at 14:52
  • $\begingroup$ Right, the easy direction is a necessary part of the proofs of correctness for AVL trees, 2-3 trees, etc. The opposite direction is deeper. It says that you don't need any structure-preserving transformations other than tree rotations for completeness. $\endgroup$
    – Per Vognsen
    Sep 23, 2010 at 14:55
5
$\begingroup$

Since you are interested in the structure of tree rotations, I think you may also be interested in the following paper, which shows that the rotation graph of binary trees of a fixed number of nodes has a Hamiltonian cycle. In fact Lucas showed that the cycle can be traversed with constant delay per tree. (A rotation can be performed in $O(1)$ time of course, but it is not obvious a priori that we should be able to decide which rotation to perform along the Hamiltonian cycle in $O(1)$ time.) Naturally, you may also be interested in the references within.

Joan M. Lucas, The rotation graph of binary trees is Hamiltonian, Journal of Algorithms, Volume 8, Issue 4, December 1987, Pages 503-535, ISSN 0196-6774, DOI: 10.1016/0196-6774(87)90048-4.

A simpler proof, also constructive, of the simpler fact that a Hamiltonian path exists in the rotation graph can be found in this later paper coauthored by Lucas and her collaborators.

Lucas J. M., Vanbaronaigien D. R., Ruskey F., On Rotations and the Generation of Binary Trees, Journal of Algorithms, Volume 15, Issue 3, November 1993, Pages 343-366, ISSN 0196-6774, DOI: 10.1006/jagm.1993.1045.

Improve this answer
$\endgroup$
-2
$\begingroup$

A simpler proof ,also constructive ,of the simpler fact that a Hamiltonian path exits in the rotation graph can be found in this latter .

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Your answer seems incomplete? $\endgroup$
    – J..y B..y
    Jun 21, 2013 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.