Tree Rotation
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 (or subtree). 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 (depends on the type of tree) greather height than its left subtree.
Left rotations (and right) 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 the left rotation.
A single left 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.
Read more about this topic: Left Rotation
Famous quotes containing the words tree and/or rotation:
“Some say that happiness is not good for mortals, & they ought to be answered that sorrow is not fit for immortals & is utterly useless to any one; a blight never does good to a tree, & if a blight kill not a tree but it still bear fruit, let none say that the fruit was in consequence of the blight.”
—William Blake (1757–1827)
“The lazy manage to keep up with the earth’s rotation just as well as the industrious.”
—Mason Cooley (b. 1927)