Editing Tree rotation (section)

==Detailed illustration==
[[Image:Tree Rotations.gif|thumb|upright=1.3|Pictorial description of how rotations are made.]]

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.