Left rotation refers to the following * 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

head A head is the part of an organism which usually includes the ears, brain, forehead, cheeks, chin, eyes, nose, and mouth, each of which aid in various sensory functions such as sight, hearing, smell, and taste. Some very simple animals may ...

and inserting it at the

tail The tail is the section at the rear end of certain kinds of animals’ bodies; 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, r ...

. * In machine code (and

assembly language In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...

) moving all bits in a register to the left, with the leftmost ( most significant bit) becoming the rightmost.

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) greater 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 In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. S ...

of the tree will yield the keys of the nodes in proper order). AVL trees and

red–black tree In computer science, a red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions. When the ...

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 In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...

. The rotations are done to keep the cost of other methods and tree height at a minimum.

References

Thomas H. Cormen Thomas H. Cormen is the co-author of ''Introduction to Algorithms'', along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled '' Algorithms Unlocked''. He is a professor of computer science at Dartmout ...

, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 16 July 2001, ''Introduction to Algorithms'', second edition. McGraw-Hill, . Chapter 13. {{Use dmy dates, date=July 2019 Trees (data structures)