Left rotation


Left rotation refers to the following
In a binary search tree, a left rotation is the movement of a node, X, down to the left. This rotation assumes that X has a right child. X's right child, R, becomes X's parent node and R's left child becomes X's new right child. This rotation is done to balance the tree; specifically when the right subtree of node X has a significantly greather height than its left subtree.
Left rotations are order preserving in a binary search tree; it preserves the binary search tree property. AVL trees and red-black trees are two examples of binary search trees that use the left rotation.
A single left rotation is done in O 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.