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.

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 14 December 2020.
HTML page formatted Mon Dec 14 11:38:56 2020.

Cite this as:
Bob Bockholt, "right 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/rightrotatn.html