There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of a rotation depends on the side which the tree nodes are shifted upon whilst others say that it depends on which child takes the root's place (opposite of the former). This article takes the approach of the side where the nodes get shifted to.
The right rotation operation as shown in the image above 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 symmetric operation is the left rotation which results in a movement in an anti-clockwise direction (the left rotation shown above is rooted at P).
Assuming this is a binary search tree, as stated above, the elements must be interpreted as variables and not as alphabetic characters.
What happens when a subtree is rotated is that the subtree side upon which it is rotated decreases its height by one node whilst the other subtree increases its height. This makes it useful to rebalance a tree.
Using 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 rotation side upon to rotate and OS for opposite side of rotation. In the above diagram for the root Q, the RS is C and the OS is P. The pseudo code for the rotation is:
Pivot = Root.OS
Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot
This is thus a constant time operation. The programmer must also make sure that the root's parent points to the pivot afterwards.
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 Python code that performs that computation:
def right_rotation(treenode):left, Q, C = treenodeA, P, B = leftreturn (A, P, (B, Q, C))
Another way of looking at it is:
Left Rotation of node P:
Let Q be P's right child. Set Q to be the new root. Set P's right child to be Q's left child. Set Q's left child to be P.
Right Rotation of node Q:
Let P be Q's left child. Set P to be the new root. Set Q's left child to be P's right child. Set P's right child to be 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 data structures such as AVL trees, red-black trees, splay trees, and treaps. 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.
A tree can be rebalanced using rotations. A type of tree which uses this rebalancing technique is the AVL tree. The reason why rotations can result in a change in balance is because after a rotation, the side of the rotation will decrease in height by 1 whilst the other side will increase in height by 1. Therefore the heights can be arranged to form a balanced tree.
It is an open problem whether there exists a polynomial time algorithm for calculating rotation distance. However, 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.