Editing Tree rotation (section)

==Inorder invariance==
The tree rotation renders the [[inorder traversal]] of the binary tree [[Invariant (computer science)|invariant]]. 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:

<pre>
Left tree: ((A, P, B), Q, C)        Right tree: (A, P, (B, Q, C))
</pre>

Computing one from the other is very simple. The following is example [[Python (programming language)|Python]] code that performs that computation:

<syntaxhighlight lang="python">
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))
</syntaxhighlight>

Another way of looking at it is:

Right rotation of node Q:

<pre>
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]
</pre>

Left rotation of node P:

<pre>
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]
</pre>

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 [[data structures]] such as [[AVL tree]]s, [[red–black tree]]s, [[WAVL tree|WAVL trees]], [[splay tree]]s, and [[treap]]s. 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.