Misplaced Pages

Right rotation refers to the following:

• In an array, moving all items to the next higher location. The last item is moved to the first location, which has been vacated.
• In a list, removing the tail and inserting it at the head.
• In machine code (and assembly language) moving all bits in a register to the right, with the rightmost (least significant bit) becoming the leftmost.

Tree rotation

In a binary search tree, a right rotation is the movement of a node, X, down to the right. This rotation assumes that X has a left child (or subtree). X's left child, R, becomes X's parent node and R's right child becomes X's new left child. This rotation is done to balance the tree; specifically when the left subtree of node X has a significantly (depending on the type of tree) greater height than its right subtree.

Right rotations (and left) are order preserving in a binary search tree; it preserves the binary search tree property (an in-order traversal of the tree will yield the keys of the nodes in proper order). AVL trees and red–black trees are two examples of binary search trees that use a right rotation.

A single right rotation is done in O(1) time but is often integrated within the node insertion and deletion of binary search trees. The rotations are done to keep the cost of other methods and tree height at a minimum.

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 16 July 2001, Introduction to Algorithms, second edition. McGraw-Hill, ISBN 0-07-013151-1. Chapter 13.

• Trees (data structures)