left rotation

(algorithm)

Definition: (1) In a binary search tree, pushing a node N down and to the left to balance the tree. N's right child replaces N, and the right child's left child becomes N's right child. (2) In an array, moving all items to the next lower location. The first item is moved to the last location, which is now vacant. (3) In a list, removing the head and inserting it at the tail.

Also known as rotate left.

Note: Also known as left single rotation, in contrast to double left rotation.

Author: BB

Implementation

(Pascal), (C). A great series of animations explaining rotations with code (Java).

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 14 December 2020.
HTML page formatted Mon Dec 14 10:59:03 2020.

Cite this as:
Bob Bockholt, "left rotation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 14 December 2020. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/leftrotation.html