Left rotation
Encyclopedia
Left rotation refers to the following
, 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 tree
s 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.
- In an array, moving all items to the next lower location. The first item is moved to the last location, which is now vacant.
- In a list, removing the headHeadIn anatomy, the head of an animal is the rostral part that usually comprises the brain, eyes, ears, nose and mouth . Some very simple animals may not have a head, but many bilaterally symmetric forms do....
and inserting it at the tailTailThe tail is the section at the rear end of an animal's body; in general, the term refers to a distinct, flexible appendage to the torso. It is the part of the body that corresponds roughly to the sacrum and coccyx in mammals, reptiles, and birds...
.
Tree Rotation
In a binary search treeBinary search tree
In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...
, 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
Binary search tree
In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...
; 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
AVL
AVL may refer to:*Acadèmia Valenciana de la Llengua *Approved Vendor List*The United Nations Audiovisual Library of International Law*Aroostook Valley Railroad...
trees and red-black tree
Red-black tree
A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...
s 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.