AVL Trees Explained: The Rotation Patterns Most People Memorise Wrong

Question

The first time an interviewer asked me to walk through an LR rotation on a whiteboard, the four-case table was memorised cold. LL, RR, LR, RL. The interviewer drew three nodes, asked which case it was, and the answer came out fast. Then they asked: "predict what a single right rotation would do to that tree, and tell me why it fails." That part hadn't been drilled. The grade went out as "knows the table, didn't internalise the invariant."

What I figured out

• The four rotation cases are not four things. They're two atomic moves applied once or twice.
• The balance factor is the rule being protected, not a check. Every rotation is a local repair on the rule |left_height - right_height| <= 1.
• Insertion needs at most one rotation. Deletion can need O(log n). That asymmetry is the answer to every "what's the tradeoff" question.
• The double-rotation cases exist because a single rotation on an "inside" imbalance shifts the heavy side without reducing the depth.
• Knowing the two atomic moves is enough to derive both LR and RL cases. Memorising the table on top is the wrong study target.

Where my approach was breaking

Three failure modes showed up on those rounds, and they show up in most engineers preparing for the same kind of question.

The four-case table got memorised without anyone tracing why each fix works. The table is a lookup. Interviewers test for the derivation. When a tree shows up on the board and the question is "what's the imbalance shape here," pattern matching against a remembered picture fails when the tree is rotated or relabelled.

Insertion got drilled, deletion didn't. Insertion is the cleaner operation. Almost every textbook walks insertion. Few walk deletion with the upward rebalance loop. Knowing "deletion is harder" as a phrase is not the same as knowing what concretely makes it harder.

Wrong rotations never got sketched. When an interviewer asks "what happens if you apply a single right rotation to an LR case," the answer has to come from a drawing, not a memory. Engineers who've never traced a failed rotation can't answer this on the spot.

What I started doing differently

Then	Now
Memorise LL / RR / LR / RL as four rotations	Internalise two atomic rotations and derive the four cases from balance factor signs
Practice insertion only	Practice deletion with the upward loop, including the worst-case O(log n) rotation chain
Treat balance factor as a check	Treat balance factor as the invariant being protected, with rotations as the local repair
Draw rotated trees from memory	Draw the pointer assignments explicitly and recompute heights before moving on
Skip wrong-rotation traces	Sketch what each wrong rotation does on an LR case, so the trap is recognisable under pressure

The "now" column is what interviewers actually probe. The "then" column is what most prep material asks you to drill.

The first rule that locks in is this. If you see a node with balance factor +2, the next look is at the left child's balance factor, not at the rotation table. If the left child is +1 or 0, single right rotate the parent. If the left child is -1, left rotate the left child first, then right rotate the parent. The decision is two questions, not a memorised table.

What that looked like on the next problem

Six months later, a different round asked for AVL insertion implementation. The sequence used to motivate the walk-through was [5, 3, 4], which fires an LR rotation. Here's the primitive:

def right_rotate(z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(height(z.left), height(z.right))
    y.height = 1 + max(height(y.left), height(y.right))
    return y

And the insertion function:

def insert(node, key):
    if not node:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    node.height = 1 + max(height(node.left), height(node.right))
    bf = balance_factor(node)

    if bf > 1 and key < node.left.key:
        return right_rotate(node)
    if bf < -1 and key > node.right.key:
        return left_rotate(node)
    if bf > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)
    if bf < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

Tracing [5, 3, 4]:

1. Insert 5. Single node, balance factor 0.
2. Insert 3. Goes left of 5. Node 5's balance factor is +1. Within the rule.
3. Insert 4. 4 < 5, go left. 4 > 3, go right of 3. Node 4 lands as 3's right child.

Walking back up: node 4 is balance factor 0, node 3 is -1, node 5 is +2. Rule broken at node 5, with its left child right-heavy. That's LR.

First rotation: left rotation on node 3. Node 4 moves up, node 3 becomes 4's left child. Node 5 still has balance factor +2, but its left subtree is now left-heavy. That's LL.

Second rotation: right rotation on node 5. Node 4 becomes the root, node 3 is 4's left child, node 5 is 4's right child. All balance factors back to 0. Height is 1.

The interviewer asked what a single right rotation would have done to the original tree. Sketched it out: node 3 becomes the root, node 5 is 3's right child, but node 4 ends up as 3's right child too, with node 5 displaced. The tree depth does not decrease. That's why the double rotation exists.

Why this works (the height theory behind it)

The choice of ±1 as the balance factor cap is not arbitrary. It's the tightest constraint that's still cheap to maintain locally.

An AVL tree with n nodes has height at most about 1.44 * log2(n). For a million nodes that's roughly 29 levels. A perfectly balanced tree would be 20 levels. The constant factor is small enough that you get the lookup speed of a balanced tree without paying the cost of full rebalancing on every insert.

Red-Black trees relax the constraint to allow heights up to about 2 log(n). That's roughly 40 levels for a million nodes. In exchange, at most 2 rotations per insertion or deletion. Looser balance, fewer rotations, faster writes.

When Adelson-Velsky and Landis named the AVL tree in 1962, the workload they had in mind was read-heavy. Lookups dominated. The strict balance was worth the rebalancing cost because every lookup was faster. Modern systems insert and delete more than they search-only, which is why Java's TreeMap, C++'s std::map, and Linux's CFS process scheduler all picked Red-Black instead. Different workload, different tradeoff. Neither tree is "better."

That's the answer the OS interviewer was looking for. AVL is read-optimised. Red-Black is tuned for mixed workloads. Picking between them is a workload question, not a theory question.

What I'd tell someone in the same spot

Three things to drill before either interview round:

1. Master the two atomic moves. Write left_rotate and right_rotate from memory, with the height updates in the right order. Three pointer reassignments, two height updates. Everything else builds on these.
2. Trace deletion at least three times. Pick at least one trace where the rebalance propagates two levels up. That's the answer to every "what's the tradeoff of stricter balance" question.
3. Sketch what a wrong rotation does on an LR case. Once you've drawn the broken tree, the LR / RL trap stops being a memory test.

Codeintuition's Binary Search Tree course is structured this way. The balance invariant comes before the rotation code, and the rotation code comes before the four-case table. Doing it in that order is what made the table feel mechanical instead of memorised.

I originally posted this on my own blog, a slightly longer version with the worked example for the original [3, 2, 1, 4, 5] insertion sequence and the AVL vs Red-Black tradeoff matrix.

What's the AVL or rotation question that finally made the rule click for you, where the textbook explanation had not?