NIST

right rotation

(algorithm)

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

Also known as rotate right.

See also left rotation, double right rotation, rotation.

Note: Also known as right single rotation, in contrast with a double right rotation.

Author: BB

Implementation

(C and Pascal). 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 12 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Bob Bockholt, "right rotation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/rightrotatn.html