Rotations

A rotation is the basic repair tool of a balanced tree. It changes three links, lifts one node and lowers another, and keeps every key in order. AVL trees and red-black trees are both built on it.

What a rotation does

Take a node y and its left child x. A right rotation at y lifts x into y’s place and puts y below x, on its right. A left rotation is the mirror image: it lifts the right child. Each rotation undoes the other.

Below x and y hang three subtrees (some may be empty). In a right rotation, call them A (left of x), B (right of x) and C (right of y). A stays with x and C stays with y. Only B changes parent: it moves from x to y. So the nodes in A go up one level, the nodes in C go down one level, and B stays at the same depth. That is how a rotation shortens a tall side.

def rotate_right(y):
    x = y.left           # x will come up
    y.left = x.right     # x's right subtree moves across
    x.right = y          # y goes down to the right
    return x             # the new top of this part

The code

The rotation itself is three assignments. Here are both directions, for nodes with left and right fields:

def rotate_right(y):
    x = y.left
    y.left = x.right  # B moves across
    x.right = y
    return x  # the new top of this part

def rotate_left(y):
    x = y.right
    y.right = x.left  # B moves across
    x.left = y
    return x

The function returns the new top, and the caller must link it in where y was: as the root, or as the left or right child of y’s parent. Forgetting that link is the most common rotation bug: the parent still points at y, and x with all of A is lost from the tree. In recursive code the fix is natural, because the caller writes node.left = rotate_right(node.left). Practice BALT-P2 asks you to rotate deep inside a tree and fix the parent’s link.

A rotation reads and writes a fixed number of fields, whatever the size of the subtrees, so it costs O(1). If nodes store extra data that depends on their subtree (a height, a count of nodes), only x and y need updating, and y must be updated first, because it is now below x.

Why the order survives

Before a right rotation, the in-order list is A, x, B, y, C: every key of A is smaller than x, B lies between x and y, and C is bigger than y. After the rotation, in-order lists x’s left subtree (A), then x, then x’s right subtree, which is y with B on its left and C on its right: A, x, B, y, C. The same list.

The rest of the tree does not notice either. Keys outside this part relate to it only through the whole range of keys it holds, and the rotation keeps the same keys in the same part.

Double rotations

One rotation fixes a tree that is tall on the outside: the left child’s left subtree, or the right child’s right subtree. It does not fix a tree that is tall on the inside: the left child’s right subtree. A right rotation moves that inside subtree (B) across without lifting it, so the tree just leans the other way. The third variant of the figure shows the fix: first rotate left at the child, which turns the inside case into the outside case, then rotate right at the top.

def rotate_left_right(z):
    z.left = rotate_left(z.left)
    return rotate_right(z)

def rotate_right_left(z):  # the mirror image
    z.right = rotate_right(z.right)
    return rotate_left(z)

The result puts the middle key of the three on top, with the smaller one on its left and the bigger one on its right. It is still O(1): six links.