Tree Rotation - Inorder Invariance

Inorder Invariance

The tree rotation renders the inorder traversal of the binary tree invariant. This implies the order of the elements are 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 Python code that performs that computation:

def right_rotation(treenode): 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 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.

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.

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.