Right rotation

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Right rotation

A right rotation is a transformation that moves elements to the right and wraps the end around to the beginning. It happens in arrays, lists, machine code, and binary search trees (BSTs).

- In arrays: every item shifts one position to the right; the last item moves to the first position.

- In lists: the tail is removed and inserted at the head.

- In machine code/assembly: the bits in a register are moved to the right; the least significant bit becomes the most significant bit (rotation, not a simple shift).

- In binary search trees: for a node X with a left child R, a right rotation makes R the parent of X, X becomes the right child of R, and R’s right subtree becomes X’s left subtree. This balances the tree when the left side is too tall, while preserving the in-order order of keys.

Right rotations, like left rotations, are order-preserving for BSTs and are used in trees such as AVL trees and red-black trees. A single right rotation runs in O(1) time and is usually performed during insertion or deletion to keep the tree height small.