Balance Factors, and Why AVL Deletion Cascades

An AVL tree stores, for every node, the difference between the heights of its right and left subtrees. That difference is called the balance factor and the invariant is that it lies in {−1, 0, +1}. The obvious implementation stores a height per node and recomputes it on the way back up; the actual implementation stores nothing but the factor, because the factor can be updated incrementally by a rule that needs no heights at all. That choice reduces the per-node metadata from a machine word to two bits, and it changes the shape of the repair code, since the update rule has to be derived rather than computed.

The second thing the factor buys is a clean account of the asymmetry between insertion and deletion. Insertion needs at most one rebalancing operation. Deletion may need one at every level of the path back to the root. Both facts follow from a single observation about when a subtree’s height changes, and that observation is the subject here.

Updating a factor without knowing any height

Let bf(x) = height(x->right) − height(x->left). After an insertion or deletion inside one subtree of x, the height of that subtree either stays the same or changes by exactly one. Nothing else is possible, because the operation touched one leaf or removed one node, and every rotation applied below restores the height of the rotated subtree to what it was before the operation reached it.

So the update rule is arithmetic on the factor. If the left subtree grew, bf(x) decreases by one. If the right subtree grew, it increases by one. If the left subtree shrank, bf(x) increases by one. If the right subtree shrank, it decreases by one. In each case the caller knows which side it descended into, so the rule is a function of the descent direction and of whether the operation was an insertion or a deletion.

The rule is only valid because heights change by at most one per level. That property is what makes the factor sufficient, and it is worth checking that rotations do not violate it: a rotation rearranges two nodes and one subtree, and the height of the resulting subtree is either the old height or one less, never more. So the invariant “each level changes height by at most one” survives repair.

The insertion walk stops at the first rotation

Insertion attaches a new leaf, which raises the height of that leaf’s subtree from zero to one, and the walk proceeds upward. At each ancestor the factor is updated, and three outcomes are possible.

If the updated factor is 0, the subtree’s height is unchanged — it had a taller side before, and the insertion filled in the shorter side. The walk stops immediately, because no ancestor can have been affected. If the factor becomes ±1, the subtree grew by one, so the walk continues. If the factor becomes ±2, the node violates the invariant and a rotation is required.

The key point is what happens after the rotation. In every one of the four cases, the repaired subtree has exactly the height it had before the insertion. A single rotation about x produces a subtree whose height is the height x had before the insertion. A double rotation does the same. So after the repair, the parent’s subtree height is unchanged, no ancestor’s factor is affected, and the walk terminates. An insertion therefore performs at most one repair, consisting of one or two rotations, and visits at most O(log n) nodes on the way.

typedef struct node {
    int key;
    int bf;                 /* height(right) - height(left), in {-1,0,1} */
    struct node *left, *right;
} node;

/* Rebalance a node x whose factor is -2 (left subtree too tall).
   Returns the new root of the repaired subtree. */
node *fix_left_heavy(node *x) {
    node *y = x->left;
    if (y->bf <= 0) {              /* LL: single right rotation */
        x->left = y->right;
        y->right = x;
        if (y->bf == 0) {          /* deletion only: repaired height is unchanged */
            x->bf = -1;
            y->bf = 1;
        } else {                   /* insertion: repaired height drops by one */
            x->bf = 0;
            y->bf = 0;
        }
        return y;
    }
    node *z = y->right;            /* LR: double rotation */
    y->right = z->left;
    x->left = z->right;
    z->left = y;
    z->right = x;
    /* Factors follow from z's original factor; the cases are -1, 0, +1. */
    x->bf = (z->bf == -1) ? 1 : 0;
    y->bf = (z->bf == 1) ? -1 : 0;
    z->bf = 0;
    return z;
}

The y->bf == 0 branch deserves attention because it only arises on deletion. When a node is inserted, the child of an over-heavy node always has a factor of ±1 pointing the same way or the opposite way; it can never be 0, because the insertion grew one of its subtrees. When a node is deleted, the child may have a factor of 0, and that case behaves differently: the rotation leaves the subtree height unchanged rather than reducing it.

Deletion propagates because the subtree shrank

Deletion removes a node. If the removed node had at most one child, it is replaced by that child or by a null pointer, and the subtree’s height drops by one. If it had two children, the standard approach replaces its key with the in-order successor’s key and then deletes the successor, which has no left child, so the physical removal is again of a node with at most one child. Either way, exactly one subtree on the path loses a level.

Now walk upward from the removal point. At each ancestor, update the factor and branch on the result:

• The factor becomes ±1. The shorter side lost a level but the subtree was already heavier on the other side, so the subtree’s height is unchanged. The walk stops.
• The factor becomes 0. The two sides are now equal, so the subtree’s height dropped by one. The walk continues.
• The factor becomes ±2. A rotation is needed, and the walk must continue upward even after it, because the rotation’s effect on the subtree height depends on the child’s factor. If the child’s factor is 0, the rotated subtree keeps its height and the walk can stop; otherwise the height drops by one and the walk continues.

That third branch is the source of the asymmetry. On insertion the repaired subtree always returns to its previous height, so the propagation is cut off. On deletion the repair may return a subtree one level shorter than before, so the parent may in turn become unbalanced, and the process can repeat at every level up to the root. The worst case is O(log n) rotations for a single deletion, against at most two for an insertion.

This is a real cost difference, not a theoretical curiosity. A workload that deletes as often as it inserts pays the deletion price on half its operations, and each deletion may perform a rotation at each of roughly log₂ n levels. For a tree of a million keys that is up to about twenty rotations, each a constant-time pointer update, which is small in absolute terms but an order of magnitude above the insertion cost.

What the child’s factor decides

The repair itself is selected by two bits of information: the sign of the violated node’s factor, and the sign of the heavier child’s factor. Four combinations exist, and each maps to a fixed sequence of rotations.

Node factor	Heavier child’s factor	Rotation	Effect on height
−2	−1	single right	decreases by 1
−2	+1	left then right	decreases by 1
−2	0	single right	unchanged
+2	+1	single left	decreases by 1
+2	−1	right then left	decreases by 1
+2	0	single left	unchanged

The 0 rows are deletion-only. The double-rotation rows are the ones that a naive implementation gets wrong: the first rotation converts the child’s inner-heavy shape into an outer-heavy shape, and the second rotation restores the invariant. Performing only the second rotation leaves the subtree still unbalanced, which is visible immediately if the invariant is checked after every operation.

Why AVL loses to red-black on write-heavy workloads

An AVL tree’s height bound is tighter than a red-black tree’s: about 1.44 log₂ n against 2 log₂(n + 1). A lookup in an AVL tree therefore performs fewer comparisons, by a factor that grows slowly with n — around 28 percent at the asymptote. That is the whole advantage, and it applies only to reads.

The cost is metadata and repair work. The factor must be maintained on every update, and deletion can trigger repairs at every level. Red-black trees store one bit instead of two, and their repair is bounded: at most two rotations for insertion, at most three for deletion, with recolouring doing the rest. Recolouring is cheaper than a rotation because it touches one field and no pointers, and it can be performed during the upward walk without restructuring.

The correspondence that explains why red-black repair is so much more local is covered in red-black colouring as a proxy for height. For trees that fit in cache the difference is small; for trees whose nodes are spread across memory, the pointer chase dominates and the tighter AVL height bound is the only thing that shows up in a measurement. That is the trade, and it is why read-mostly in-memory indexes often use AVL-shaped invariants while general-purpose ordered maps use red-black ones.

The invariant as a maintenance obligation

Two details are easy to get wrong when implementing the factor scheme, and both produce trees that pass an in-order check while violating the balance invariant.

The first is forgetting to update the factor of the node that moved. A single rotation reassigns three pointers and must also assign three factors: the new parent’s, the new child’s, and the rotated subtree’s. The formulas depend on which case fired, and they are not symmetric between insertion and deletion. In the code above, x->bf after a single right rotation is −1 when y->bf was 0, and 0 otherwise — a distinction that only matters on the deletion path.

The second is treating the repair as complete when the rotation is done. On insertion it is; on deletion it is not, and the upward walk must continue unless the rotation was the 0 case. Implementations that stop early after any rotation produce trees whose root is balanced and whose interior is not. The bug is invisible in small tests because the invariant is only violated above the repair point, and it surfaces as a height bound that drifts above the theoretical maximum over a long sequence of updates.