Tree rotation

<h2 id="illustration">Illustration</h2>
 
The right rotation operation as shown in the adjacent image is performed with Q as the root and hence is a right rotation on, or rooted at, Q. This operation results in a rotation of the tree in the clockwise direction. The inverse operation is the left rotation, which results in a movement in a counter-clockwise direction (the left rotation shown above is rooted at P). The key to understanding how a rotation functions is to understand its constraints. In particular the order of the leaves of the tree (when read left to right for example) cannot change (another way to think of it is that the order that the leaves would be visited in an in-order traversal must be the same after the operation as before). Another constraint is the main property of a binary search tree, namely that all nodes in the right subtree are greater than the parent and all nodes in the left subtree are less than the <a href="/facts/Parent_node/RcXz9noF">parent</a>. Notice that the <a href="/facts/Right_child/TDV7GMpu">right child</a> of a left child of the root of a sub-tree (for example node B in the diagram for the tree rooted at Q) can become the left child of the root, that itself becomes the right child of the "new" root in the rotated sub-tree, without violating either of those constraints. As seen in the diagram, the order of the leaves doesn't change. The opposite operation also preserves the order and is the second kind of rotation.
Assuming this is a <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree</a>, as stated above, the elements must be interpreted as variables that can be compared to each other. The alphabetic characters to the left are used as placeholders for these variables. In the animation to the right, capital alphabetic characters are used as variable placeholders while lowercase Greek letters are placeholders for an entire set of variables. The circles represent individual nodes and the triangles represent subtrees. Each subtree could be empty, consist of a single node, or consist of any number of nodes.

<h2 id="detailed-illustration">Detailed illustration</h2>

When a subtree is rotated, the subtree side upon which it is rotated increases its height by one node while the other subtree decreases its height. This makes tree rotations useful for rebalancing a tree.
Consider the terminology of Root for the parent node of the subtrees to rotate, Pivot for the node which will become the new parent node, RS for the side of rotation and OS for the opposite side of rotation. For the root Q in the diagram above, RS is C and OS is P. Using these terms, the pseudo code for the rotation is:

let Pivot = Root.OS
Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot

This is a constant time operation.
The programmer must also make sure that the root's parent points to the pivot after the rotation. Also, the programmer should note that this operation may result in a new root for the entire tree and take care to update pointers accordingly.

<h2 id="inorder-invariance">Inorder invariance</h2>
The tree rotation renders the <a href="/facts/Inorder_traversal/Dkch34pz">inorder traversal</a> of the binary tree <a href="/facts/Invariant_(computer_science)/9TeNN2ed">invariant</a>. This implies the order of the elements is not affected when a rotation is performed in any part of the tree. Here are the inorder traversals of the trees shown above:

Left tree: ((A, P, B), Q, C) Right tree: (A, P, (B, Q, C))

Computing one from the other is very simple. The following is example <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a> code that performs that computation:

def right_rotation(treenode):
 """Rotate the specified tree to the right."""
 left, Q, C = treenode
 A, P, B = left
 return (A, P, (B, Q, C))

Another way of looking at it is:
Right rotation of node Q:

Let P be Q's left child.
Set Q's left child to be P's right child.
[Set P's right-child's parent to Q]
Set P's right child to be Q.
[Set Q's parent to P]

Left rotation of node P:

Let Q be P's right child.
Set P's right child to be Q's left child.
[Set Q's left-child's parent to P]
Set Q's left child to be P.
[Set P's parent to Q]

All other connections are left as-is.
There are also double rotations, which are combinations of left and right rotations. A double left rotation at X can be defined to be a right rotation at the right child of X followed by a left rotation at X; similarly, a double right rotation at X can be defined to be a left rotation at the left child of X followed by a right rotation at X.
Tree rotations are used in a number of tree <a href="/facts/Data_structures/yNsNvL1I">data structures</a> such as <a href="/facts/AVL_tree/DfexIbS6">AVL trees</a>, <a href="/facts/Red%E2%80%93black_tree/ckgWTV7G">red–black trees</a>, <a href="/facts/WAVL_tree/ooAX5qjp">WAVL trees</a>, <a href="/facts/Splay_tree/DHKCdoST">splay trees</a>, and <a href="/facts/Treap/sNDcxCpE">treaps</a>. They require only constant time because they are local transformations: they only operate on 5 nodes, and need not examine the rest of the tree.

<h2 id="rotations-for-rebalancing">Rotations for rebalancing</h2>

A tree can be rebalanced using rotations. After a rotation, the side of the rotation increases its height by 1 whilst the side opposite the rotation decreases its height similarly. Therefore, one can strategically apply rotations to nodes whose left child and right child differ in height by more than 1. Self-balancing binary search trees apply this operation automatically. A type of tree which uses this rebalancing technique is the <a href="/facts/AVL_tree/DfexIbS6">AVL tree</a>.

<h2 id="rotation-distance">Rotation distance</h2>
Main article: <a href="/facts/Rotation_distance/fl31kBMG">Rotation distance</a>

Unsolved problem in computer science:
Can the rotation distance between two binary trees be computed in polynomial time?
<a href="/facts/List_of_unsolved_problems_in_computer_science/QySnBJ5E">(more unsolved problems in computer science)</a>

The <a href="/facts/Rotation_distance/fl31kBMG">rotation distance</a> 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 <a href="/facts/Metric_space/gnBBRXtc">metric space</a>: the distance is symmetric, positive when given two different trees, and satisfies the <a href="/facts/Triangle_inequality/KubLjkwr">triangle inequality</a>.
It is an <a href="/facts/Open_problem/VuR6yLsW">open problem</a> whether there exists a <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for calculating rotation distance, though several variants of the rotation distance problem admit polynomial time algorithms.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
<a href="/facts/Daniel_Sleator/hLBuUyER">Daniel Sleator</a>, <a href="/facts/Robert_Tarjan/kn1pMCN0">Robert Tarjan</a> and <a href="/facts/William_Thurston/K1Qe8801">William Thurston</a> showed that the rotation distance between any two n-node trees (for n ≥ 11) is at most 2n − 6, and that some pairs of trees are this far apart as soon as n is sufficiently large.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Lionel Pournin showed that, in fact, such pairs exist whenever n ≥ 11.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/AVL_tree/DfexIbS6">AVL tree</a>, <a href="/facts/Red%E2%80%93black_tree/ckgWTV7G">red–black tree</a>, and <a href="/facts/Splay_tree/DHKCdoST">splay tree</a>, kinds of <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree</a> data structures that use rotations to maintain balance.</li>
<li><a href="/facts/Associativity/EQX8lV6r">Associativity</a> of a binary operation means that performing a tree rotation on it does not change the final result.</li>
<li>The <a href="/facts/Day%E2%80%93Stout%E2%80%93Warren_algorithm/CLrJaQql">Day–Stout–Warren algorithm</a> balances an unbalanced BST.</li>
<li><a href="/facts/Tamari_lattice/UtSr0cMH">Tamari lattice</a>, a partially ordered set in which the elements can be defined as binary trees and the ordering between elements is defined by tree rotation.</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://fortheloot.com/public/AVLTreeTutorial.rtf">The AVL Tree Rotations Tutorial</a> (RTF) by John Hargrove</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Fordham, Blake (2003), "Minimal Length Elements of Thompson's Group F", Geometriae Dedicata, 99 (1), Springer Science and Business Media LLC: 179–220, doi:10.1023/a:1024971818319, ISSN 0046-5755 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bonnin, André; Pallo, Jean-Marcel (1992), "A shortest path metric on unlabeled binary trees", Pattern Recognition Letters, 13 (6), Elsevier BV: 411–415, doi:10.1016/0167-8655(92)90047-4, ISSN 0167-8655 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Pallo, Jean Marcel (2003), "Right-arm rotation distance between binary trees", Information Processing Letters, 87 (4), Elsevier BV: 173–177, doi:10.1016/s0020-0190(03)00283-7, ISSN 0020-0190 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988), "Rotation distance, triangulations, and hyperbolic geometry", Journal of the American Mathematical Society, 1 (3): 647–681, doi:10.2307/1990951, JSTOR 1990951, MR 0928904. <a href="/wiki/Daniel_Sleator" target="_blank">/wiki/Daniel_Sleator</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Pournin, Lionel (2014), "The diameter of associahedra", Advances in Mathematics, 259: 13–42, arXiv:1207.6296, doi:10.1016/j.aim.2014.02.035, MR 3197650. <a href="/wiki/Advances_in_Mathematics" target="_blank">/wiki/Advances_in_Mathematics</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
</ol>

Tree rotation open-in-new

Tree rotation