rotation

A small local rearrangement of a search tree that lifts a child above its parent while keeping the keys in order.

In more detail

A left rotation fixes a right-heavy node and a right rotation a left-heavy one; a double rotation is two single ones in opposite directions, for zig-zag shapes. Each rotation rewires a constant number of pointers, so it is O(1). The in-order sequence of keys is unchanged, so the BST property survives.

Related terms

Taught in

References