AVL Rotations — LL, RR, LR, RL

How it works

1. Find the lowest unbalanced node z on the way back up (balance factor +2 or −2).
2. Let y be z's taller child: bf(z) = +2 means the left side is taller (case L…), −2 the right side (case R…).
3. Look at y: leaning the same way as z (or even, after a delete) gives LL or RR; leaning the opposite way gives LR or RL.
4. LL: rotate right at z. RR: rotate left at z.
5. LR: rotate left at y, then right at z. RL: rotate right at y, then left at z.
6. Recompute the heights of the moved nodes (the lower one first) and attach the new subtree root to z's old parent.

Anatomy of a single rotation

Take a right rotation at z, whose left child is y. Three subtrees hang off the pair: T1 (y's left), T2 (y's right) and T3 (z's right). In sorted order they read T1 < y < T2 < z < T3. After the rotation y is on top, z is y's right child, T1 stays under y, T3 stays under z — and T2 changes parents, becoming z's left child. The sorted order T1 < y < T2 < z < T3 is untouched, so the tree is still a valid BST; only the heights changed.

That is the entire operation: three pointers change (z.left, y.right and the parent's link to the subtree) and two heights are recomputed, z first because it is now below y. A left rotation is the mirror image. In the visualizer z is drawn red, the pivot y amber and T2 purple; T2's old link is cut before the nodes swing into place, so you can see exactly what moves.

The four cases, with real numbers

• LL — start from 50, 30, 70, 20, 40 and insert 10. Node 50 gets bf +2 and its left child 30 leans left, a straight line. One right rotation at 50 lifts 30 to the root with 20 and 50 as children; 40 (T2) moves from 30's right to 50's left.
• RR — start from 30, 20, 50, 40, 60 and insert 70. Node 30 gets bf −2 and 50 leans right. One left rotation at 30 lifts 50 to the root; 40 moves across to become 30's right child.
• LR — start from 50, 30, 70, 20, 40 and insert 35. Node 50 is left-heavy (+2) but its left child 30 leans right (−1): a zig-zag. A left rotation at 30 lifts 40 and turns the bend into a straight line; a right rotation at 50 then lifts 40 to the top. Result: 40 at the root, 30 (with 20 and 35) on the left, 50 (with 70) on the right.
• RL — start from 30, 20, 60, 50, 70 and insert 55. A right rotation at 60, then a left rotation at 30, leave 50 at the root, 30 (with 20) on the left and 60 (with 55 and 70) on the right.

This page opens on the LR example; the Rotation demos picker plays all four, plus a deletion that triggers a rotation.

How to tell which case you are in

Read two balance factors: the unbalanced node z and its taller child y.

• bf(z) = +2 and bf(y) ≥ 0 → LL → rotate right at z.
• bf(z) = −2 and bf(y) ≤ 0 → RR → rotate left at z.
• bf(z) = +2 and bf(y) = −1 → LR → rotate left at y, then right at z.
• bf(z) = −2 and bf(y) = +1 → RL → rotate right at y, then left at z.

The names describe the path from z to the too-tall grandchild: left then left, right then right, and so on. Memory aid: a straight line needs one rotation; a zig-zag needs two, and the first one straightens it. Be careful with naming conventions — some books label the cases by the rotation that fixes them (an LL imbalance is fixed by a "right rotation", sometimes called an R rotation), so check which one a question uses.

Why the zig-zag needs a double rotation

In the LR case the extra height sits in the middle subtree: the right child of z's left child. A single right rotation at z would hand that middle subtree over to z without lifting it, so the tree would simply lean the other way with balance factor −2. The first rotation, at y, moves the heavy grandchild x up into y's place and turns the zig-zag into a straight line; the second rotation, at z, lifts x to the top with y and z as its children.

So a double rotation always makes the grandchild the new subtree root — the middle key of the three. In the LR example, 40 sits between 30 and 50, and 40 ends up on top. Goodrich and Tamassia describe all four cases this way, as a single "trinode restructuring" of x, y and z.

Rotations after insertion vs after deletion

After an insertion, the first unbalanced node met on the way up is fixed with one single or double rotation, and the subtree gets back exactly its pre-insert height — so nothing above it can be unbalanced and the walk stops.

A deletion is different. The repaired subtree can end up one level shorter than before, which may unbalance its parent, and so on: a delete can rotate at every level, O(log n) rotations of O(1) each. Deletion also creates the case where the taller child is perfectly even (bf 0), which a single rotation handles. The Delete demo shows it: removing 40 from 30, 20, 40, 10, 25 leaves 30 left-heavy with an even left child 20, and one right rotation lifts 20 to the top.

Rotations beyond AVL trees

The same two primitives power most balanced trees. Red-black trees rotate (at most twice per insert, three times per delete) alongside recolouring; splay trees rotate each accessed key up to the root; treaps rotate to restore heap order on random priorities. And because a rotation keeps the in-order sequence intact, any per-node summary that can be recomputed from the two children — height, subtree size, sum, maximum — survives a rotation with an O(1) update, which is what order-statistic and interval trees rely on.

Time and space complexity

AVL Rotations in Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1                # a leaf has height 1
        self.bf = 0                    # balance factor h(left) - h(right)


def h(n):
    return n.height if n else 0        # an empty subtree has height 0


def update(n):
    n.height = 1 + max(h(n.left), h(n.right))
    n.bf = h(n.left) - h(n.right)


def rotate_right(z):
    y = z.left                         # pivot
    T2 = y.right                       # moves over to z
    y.right = z                        # z goes down
    z.left = T2
    update(z)                          # z first: it is now below y
    update(y)
    return y                           # new root of this subtree


def rotate_left(z):
    y = z.right                        # pivot
    T2 = y.left                        # moves over to z
    y.left = z                         # z goes down
    z.right = T2
    update(z)                          # z first: it is now below y
    update(y)
    return y                           # new root of this subtree


def rebalance(z):
    if z.bf > 1:                       # left-heavy
        if z.left.bf < 0:              # LR zig-zag
            z.left = rotate_left(z.left)
        return rotate_right(z)         # LL
    if z.bf < -1:                      # right-heavy
        if z.right.bf > 0:             # RL zig-zag
            z.right = rotate_right(z.right)
        return rotate_left(z)          # RR
    return z                           # balanced

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• AVL Tree VisualizerAVL tree visualizer: insert and delete keys, watch heights and balance factors update and LL, RR, LR, RL rotations keep every operation O(log n).
• Binary Search Tree VisualizerBinary search tree visualizer: insert, search and delete keys step by step, see why every operation costs O(h), and compare a plain BST with AVL and B-trees.
• BST Deletion — All Three CasesHow to delete a node from a binary search tree: the leaf, one-child and two-children cases, in-order successor or predecessor, with an animated example.
• Tree Traversal Visualizer — Inorder, Preorder, Postorder, Level OrderVisualize inorder, preorder, postorder and level-order tree traversal on one tree: the visit order, the call stack or queue, the code, and when to use each.
• B-Tree Insertion & SplittingB-tree insertion step by step: find the leaf, insert in sorted order, split a full node around its median and push it up — even to a new root. Animated.