7.13 Tree Rotations

Tree rotations are the primitive operation behind many balanced binary search trees.

AVL trees, red-black trees, treaps, splay trees, and several other ordered structures all use rotations to repair shape while preserving key order. A rotation changes parent-child relationships among a small number of nodes. It does not change the sorted order of the keys.

This distinction is critical. A rotation modifies structure, not meaning.

The tree may look different afterward, but an in-order traversal produces the same sequence as before. That is why rotations can rebalance a tree without corrupting the binary search tree invariant.

Problem

You have a binary search tree that has become locally unbalanced.

Example:

    10
      \\n       20
         \\n          30

The values are still ordered correctly.

An in-order traversal gives:

10 20 30

But the tree shape is poor. Search for 30 requires following a chain.

We want to reshape the tree into:

      20
     /  \\n   10    30

while keeping the same sorted order.

Solution

Use a rotation.

A left rotation moves a right child upward.

Before:

    x
     \\n      y
     / \\n    B   C

After:

      y
     / \\n    x   C
     \\n      B

A right rotation moves a left child upward.

Before:

      y
     /
    x
   / \\n  A   B

After:

    x
   / \\n  A   y
     /
    B

Both operations preserve the binary search tree property.

Why Rotations Preserve Order

Consider the left rotation:

    x
   / \\n  A   y
     / \\n    B   C

The BST ordering before rotation is:

A < x < B < y < C

After rotation:

      y
     / \\n    x   C
   / \\n  A   B

The ordering is still:

A < x < B < y < C

No key crosses an invalid boundary.

The subtree B moves from being the left child of y to the right child of x. This is safe because every key in B is greater than x and less than y.

That local ordering fact is the entire reason rotations work.

Node Definition

A minimal Go node is enough to demonstrate rotations.

type Node struct {
	Key   int
	Left  *Node
	Right *Node
}

In production implementations, a node may also store:

Height int
Color  bool
Size   int
Parent *Node
Value  any

Those fields support AVL balancing, red-black balancing, order statistics, parent traversal, or map values. The rotation logic still revolves around the same pointer changes.

Left Rotation

A left rotation requires a right child.

func RotateLeft(x *Node) *Node {
	y := x.Right
	b := y.Left

	y.Left = x
	x.Right = b

	return y
}

The returned node is the new root of the rotated subtree.

Example:

Before:

10
  \\n   20
     \\n      30

Call:

root = RotateLeft(root)

After:

    20
   /  \\n 10    30

The subtree is shorter and better shaped.

Right Rotation

A right rotation is symmetric.

func RotateRight(y *Node) *Node {
	x := y.Left
	b := x.Right

	x.Right = y
	y.Left = b

	return x
}

Example:

Before:

      30
     /
   20
  /
10

Call:

root = RotateRight(root)

After:

    20
   /  \\n 10    30

Again, the ordering is unchanged.

Updating Parent Links

If your tree stores parent pointers, rotations must update them too.

Without parent pointers, the caller reconnects the returned subtree root. With parent pointers, every affected node must be repaired.

A simplified left rotation with parent links looks like this:

type ParentNode struct {
	Key    int
	Left   *ParentNode
	Right  *ParentNode
	Parent *ParentNode
}

func RotateLeftWithParent(x *ParentNode) *ParentNode {
	y := x.Right
	b := y.Left

	y.Left = x
	x.Right = b

	y.Parent = x.Parent
	x.Parent = y

	if b != nil {
		b.Parent = x
	}

	return y
}

This is still incomplete for a full tree because the old parent must also be updated to point to y instead of x. Many bugs in tree implementations come from forgetting one of these parent-link assignments.

Double Rotations

Some imbalances cannot be fixed with one rotation.

Consider:

    30
   /
 10
   \\n    20

A single right rotation gives:

  10
    \\n     30
    /
   20

This is still poorly shaped.

The fix is a left rotation on the child, followed by a right rotation on the root.

Step 1: rotate left at 10

    30
   /
 20
 /
10

Step 2: rotate right at 30

    20
   /  \\n 10    30

This is called a left-right rotation.

The mirror case is a right-left rotation.

Left-Right Rotation

Implementation:

func RotateLeftRight(root *Node) *Node {
	root.Left = RotateLeft(root.Left)
	return RotateRight(root)
}

Use this when the left subtree is heavy, but its right child is the source of the imbalance.

Shape:

      z
     /
    x
     \\n      y

After rotation:

      y
     / \\n    x   z

Right-Left Rotation

Implementation:

func RotateRightLeft(root *Node) *Node {
	root.Right = RotateRight(root.Right)
	return RotateLeft(root)
}

Use this when the right subtree is heavy, but its left child is the source of the imbalance.

Shape:

    z
     \\n      x
     /
    y

After rotation:

      y
     / \\n    z   x

Rotation as a Local Rewrite

A rotation is a local rewrite rule.

It changes a small subtree and leaves the rest of the tree untouched.

Before:

        P
       /
      x
       \\n        y
       / \\n      B   C

After left rotation at x:

        P
       /
      y
     / \\n    x   C
     \\n      B

The parent P must now point to y.

This local nature is what makes balanced trees efficient. Rebalancing does not rebuild the whole tree. It performs a bounded number of local corrections along the update path.

Rotations During Insertion

Suppose values arrive in increasing order:

10, 20, 30

A plain BST becomes:

10
  \\n   20
     \\n      30

A balanced tree detects the right-right imbalance and applies a left rotation.

Result:

    20
   /  \\n 10    30

The insertion still follows ordinary BST logic. The rotation happens afterward to restore the tree’s shape constraint.

Rotations During Deletion

Deletion can also create imbalance.

Suppose removing a node makes the left subtree much taller than the right. A balanced tree may apply a right rotation, left-right rotation, or another local correction depending on the exact shape.

Deletion rebalancing is usually more subtle than insertion rebalancing because height changes can propagate farther up the tree. The rotation operations themselves remain the same.

Testing Rotations

Rotations are easy to get almost right and difficult to debug after the tree grows large.

A good test checks two things:

1. The in-order traversal stays the same.
2. The new root has the expected shape.

Example:

func Collect(root *Node, out *[]int) {
	if root == nil {
		return
	}

	Collect(root.Left, out)
	*out = append(*out, root.Key)
	Collect(root.Right, out)
}

For a left rotation, test that:

before in-order == after in-order

and verify the root changed from 10 to 20.

The first check validates ordering. The second check validates structure.

Complexity Analysis

A single rotation touches only a constant number of pointers.

Operation	Complexity
Left rotation	O(1)
Right rotation	O(1)
Double rotation	O(1)
Extra memory	O(1)

Rotations are cheap. The cost of balanced tree operations comes mostly from searching the path from the root to the update point, which costs O(log n) when the tree remains balanced.

Common Mistakes

A common mistake is losing the middle subtree.

In a left rotation:

B

must become the right child of x. If you overwrite pointers in the wrong order, B may become unreachable.

Another mistake is forgetting that the rotated subtree has a new root. Rotation functions should return that root, and callers must reconnect it.

With parent pointers, missing a parent update can create cycles or disconnected subtrees.

A final mistake is thinking rotations sort the tree. They do not. Rotations preserve an ordering that must already be valid.

Takeaway

Tree rotations are constant-time structural rewrites that preserve the binary search tree ordering while improving shape. They are the mechanical basis of most self-balancing trees. Once rotations are understood as local transformations that preserve in-order traversal, AVL trees, red-black trees, treaps, and splay trees become much easier to reason about.