Rotations and the In-Order Sequence They Preserve

A rotation is the smallest edit that changes the shape of a binary tree without changing the sequence of keys it stores. Everything else in this cluster — AVL repair, red-black repair, the split and join operations of weight-balanced trees — is built from rotations plus constant-time bookkeeping. The operation is worth understanding at the pointer level, because the distinction between the two rotation directions and the two-step “double rotation” is where most implementations of balanced trees go wrong.

The invariant a rotation must not disturb

A binary search tree encodes two things at once: an ordered sequence, recoverable by in-order traversal, and a shape, which determines search cost. The shape is what balancing manipulates, and the sequence is what must be preserved exactly. Any transformation that alters the in-order sequence has changed the set of keys or their order and is not a rebalancing operation at all.

Consider a node x with left child y. Suppose y has a right child β. The subtrees in in-order are α (left of y), β (right of y), and γ (right of x). Reading in-order gives α, y, β, x, γ. A right rotation about x makes y the parent and x its right child, with β reparented from y’s right to x’s left. The in-order reading is now α, y, β, x, γ — identical. The three subtrees α, β, γ keep their internal structure and their relative order; only the two keys x and y swap levels, and the subtree β moves from one parent to the other.

That is the entire content of the operation. A rotation moves one subtree between two adjacent nodes and reverses the parent-child relationship of those two nodes. Nothing else changes, which is why a rotation costs constant time regardless of subtree size: three pointer assignments, and the subtrees are never touched.

typedef struct node {
    int key;
    struct node *left, *right;
} node;

/* Right rotation about x; y must be x->left and non-null. Returns the new subtree root. */
node *rotate_right(node *x) {
    node *y = x->left;
    x->left = y->right;   /* β moves from y's right to x's left */
    y->right = x;
    return y;
}

A left rotation is the mirror image, and applying a right rotation followed by a left rotation to the same pair restores the original tree exactly. Rotations are invertible, which matters for the analysis of splay trees, where an access performs rotations that are later partially undone by other accesses, and for the amortized argument that a sequence of accesses costs O(log n) despite individual operations doing Θ(n) work.

What a rotation does to height

A rotation preserves the in-order sequence but generally changes heights. Take x at height h with left subtree of height h − 1 and right subtree of height h − 3. A right rotation makes y the parent. The new left subtree α has height h − 2; the new right subtree rooted at x has height max(h − 3, height(β)) + 1. If β is a single node, that is max(h − 3, 0) + 1, which for large h is h − 2. So the subtree rooted at the new parent has height h − 1, one less than before, and the whole tree may drop by one level.

The direction of the change is not guaranteed in general. A rotation can increase the height of a subtree as easily as decrease it; what a rotation guarantees is that the in-order sequence is unchanged and that the two nodes involved exchange a level. Balancing algorithms choose rotations that move height in the needed direction, and the choice is dictated by which side is too tall.

This asymmetry is why a single rotation sometimes fails to repair a violation. Consider an AVL node whose left subtree is two levels taller than its right. If the left child’s own left subtree is the taller one, a right rotation about the node fixes it. If instead the left child’s right subtree is taller, the right rotation leaves the new right subtree still too tall, because the offending height moved from one side of y to the other side of x without being reduced. The fix is a left rotation about y first, converting the shape into the first case, then the right rotation about x. This is the double rotation, and the pair of rotations is not equivalent to any single rotation.

The four cases have standard names. An insertion into the left subtree of the left child of an AVL node is repaired by one right rotation; into the right subtree of the left child, by a left-then-right double rotation; and the two mirror cases symmetrically. The classification depends only on the path taken from the unbalanced node to the newly inserted key, which is why the repair can be decided in constant time once the path back to the root is available.

Repairing upward, and where the repair stops

Insertion into an AVL tree appends a leaf, then walks back up the path to the root updating heights. Only nodes on that path can change height, and the walk stops at the first node whose height is unchanged. That stopping condition is the reason insertion costs O(log n) rather than O(log² n): the walk is at most as long as the tree is tall, and the rotation work is constant per node visited.

The subtlety is that after a rotation, the height of the repaired subtree returns to its pre-insertion value, so no ancestor can have been disturbed. Insertion therefore needs at most one rebalancing operation, of one or two rotations. Deletion is different: removing a node can reduce the height of a subtree without any rotation restoring it, so the height decrease propagates to the root and the repair may occur at every level. Deletion in an AVL tree can require O(log n) rotations, while insertion requires at most two.

Red-black trees exploit the same asymmetry differently. Their insertion repair can recolour without rotating and, once a rotation occurs, the violation is resolved and the walk stops. Their deletion repair can propagate recolouring all the way to the root and performs at most three rotations. The counts are documented properties of the algorithms rather than implementation choices, and they are the concrete reason red-black trees are preferred for write-heavy ordered maps.

What rotations cannot do

Rotations preserve the in-order sequence and the set of nodes. They cannot change the number of nodes, cannot alter a key, and cannot fix an imbalance that is not local to the rotated pair. Three consequences are worth stating because they bound the design space.

A rotation cannot restore balance in a tree whose imbalance is spread across many levels. If a chain of n nodes has been built, repairing it requires Θ(n) rotations, not a constant number, and any algorithm that does so is doing linear work per operation. This is exactly what splay trees accept: a splay operation performs rotations along an access path and is Θ(n) in the worst case, buying amortized O(log n) with no per-node metadata at all. The trade is analysed in splaying as an amortized alternative to stored balance metadata.

A rotation cannot move a key between subtrees in a way that changes the key ranges. Because the in-order sequence is fixed, the set of keys in any subtree that is not β remains the same set. This is what allows an augmented tree to maintain subtree aggregates: if a rotation moves β from y to x, only the aggregates of x and y need recomputation, and they can be recomputed from their children in constant time. Order-statistic trees and interval trees rely on exactly this property, which is why augmenting a balanced tree with subtree counts is feasible at all.

A rotation cannot be applied to an arbitrary pair of nodes. It requires a parent-child relationship, and in the usual formulation it requires the child on the correct side. Rotating “about” a node with no left child is undefined. Implementations that maintain parent pointers must update four links rather than three, and the extra link is where bugs concentrate: a rotation that forgets to update the parent pointer of β leaves a node whose parent field points into a subtree it no longer belongs to, and the tree passes every in-order check while failing on the next upward walk.

Why the primitive is shared across schemes

The schemes in this cluster differ in what they store and when they rotate, not in how a rotation works. AVL trees rotate as soon as a height difference of two appears. Red-black trees rotate only when recolouring cannot resolve a violation, and the colour rules correspond to a 2-3-4 tree whose node splits and merges are the real operation being simulated. Weight-balanced trees rotate when subtree sizes fall outside a ratio. Treaps rotate to restore heap order on random priorities. All four use the same three-pointer rewiring.

That commonality is what makes a generic rotation routine worth writing once and reusing, and it is also why the choice between schemes comes down to metadata size, rotation counts per update, and the height constant — not to the cost of the primitive itself.