Tree rotation

There exists an inconsistency in different descriptions as to the definition of the direction of rotations.

Assuming this is a binary search tree, as stated above, the elements must be interpreted as variables that can be compared to each other.

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: 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.

This implies the order of the elements is not affected when a rotation is performed in any part of the tree.

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.

Self-balancing binary search trees apply this operation automatically.

It is an open problem whether there exists a polynomial time algorithm for calculating rotation distance, though several variants of the rotation distance problem admit polynomial time algorithms.

Generic tree rotations.
Animation of tree rotations taking place.
Animation of tree rotations taking place.
Pictorial description of how rotations are made.
Pictorial description of how rotations cause rebalancing in an AVL tree.