AVL Trees: Detecting Imbalance and Choosing the Right Rotation

An AVL tree is a binary search tree that actively maintains a height-balance rule. The central idea is simple: at every node, the heights of the left and right subtrees must remain close. When one side becomes taller than the other by two levels, the tree is out of balance and a rotation restores the required shape.

The title question, “Heights off by two? Rotate,” summarizes the main visual test. The difference is measured with a balance factor, and the direction of the imbalance determines which of four cases is present: left-left, right-right, left-right, or right-left. The first two cases use one rotation. The latter two use two rotations.

Deletion matters because removing a node can change the heights of several ancestors, not just the node where the deletion occurs. After a delete, the tree must be checked on the path back toward the root, and each newly unbalanced node may need to be repaired.

1. The shape an AVL tree is trying to preserve​

An AVL tree has the same ordering rule as a binary search tree. Values smaller than a node are placed in its left subtree, and values larger than a node are placed in its right subtree. The AVL rule adds a structural restriction: the two child subtrees of every node differ in height by at most one.

Let the height of a node be written as $h$. A leaf has no children, so its height is determined by the height convention used by the implementation. Some implementations assign a leaf height of $0$ and an empty subtree height of $-1$. Others assign a leaf height of $1$ and an empty subtree height of $0$. Either convention works if it is used consistently.

For a node $v$, let $h_L$ be the height of its left subtree and $h_R$ be the height of its right subtree. The AVL condition is

The tree becomes unbalanced when the difference reaches two. That means one child subtree is at least two levels taller than the other:

In a correctly maintained AVL tree, a larger difference should not remain after the relevant update has been repaired. The rotation is a local restructuring that preserves the binary-search-tree ordering while changing the heights of selected subtrees.

A small visual example​

Consider a node whose left subtree has height $3$ and whose right subtree has height $1$. Its balance difference is

That node is unbalanced. The left side is too tall, so the repair must move some of the left-side structure upward or rearrange it. If the extra height is concentrated in the left child’s left subtree, the case is LL. If it is concentrated in the left child’s right subtree, the case is LR.

The same reasoning applies symmetrically when the right side is too tall. A right-heavy node may be an RR case or an RL case, depending on which side of its right child contains the extra height.

2. Balance factors make the imbalance visible​

The balance factor is a signed version of the height difference. A common definition is

With this definition:

• $BF(v)=0$ means the two child subtrees have equal height.
• $BF(v)=1$ means the left subtree is one level taller.
• $BF(v)=-1$ means the right subtree is one level taller.
• $BF(v)=2$ means the node is left-heavy and needs repair.
• $BF(v)=-2$ means the node is right-heavy and needs repair.

The AVL invariant can therefore be written compactly as

for every node $v$.

The sign convention is not universal. Some descriptions define the balance factor as right height minus left height, which reverses all the signs. The important point is not the sign by itself. The important points are that the factor compares the two subtree heights, that magnitude two signals the imbalance described in the video, and that the direction identifies which side is too tall.

Why height is the right quantity to track​

The balance rule concerns the vertical shape of the tree. A subtree can contain many nodes while still having a small height, or contain fewer nodes but extend deeply. Since search paths follow child links from the root downward, height controls the maximum number of levels that a search may need to inspect.

If the tree is kept balanced, its height grows logarithmically with the number of nodes. In asymptotic notation, the height is $O(\log n)$ for $n$ stored nodes. As a result, search, insertion, and deletion have logarithmic worst-case behavior when the balancing work is correctly maintained.

The exact height convention changes constants and base cases, but not the key conclusion. The AVL rule prevents a long one-sided chain from developing through repeated updates.

3. What a rotation changes—and what it preserves​

A rotation changes parent-child relationships among a small connected group of nodes. It does not sort the keys again, and it does not change the in-order sequence of the tree.

That preservation is essential. If the keys in a binary search tree are visited in in-order, they appear in sorted order. A valid rotation must leave that order unchanged. The operation changes the shape, not the ordering.

Suppose a node $z$ is unbalanced and its child is $y$. A rotation can move $y$ above $z$, making $y$ the new root of that local subtree. The old parent of $z$ must then point to $y$, and the affected middle subtree must be attached in the only position that preserves the search-tree ordering.

For example, in a right rotation around $z$, the left child of $z$ rises. A subtree that lies between the rising child and $z$ moves from one side of the rising child to the other side of $z$. That middle subtree is not discarded; it is reattached.

A rotation therefore has three important responsibilities:

1. Change the local shape so the tall path is shortened.
2. Preserve the binary-search-tree ordering.
3. Update the links and heights consistently.

The visual transformation is local, but its height effect can repair the balance of the entire ancestor path. After a rotation, the new root of the local subtree may be shorter than the previous root, allowing higher ancestors to become balanced as well.

4. The four imbalance cases​

The four names describe a path from the unbalanced node to the side containing the extra height. Let $z$ be the first unbalanced node encountered while moving upward from an update. Let $y$ be its taller child. The case depends on whether the heavy direction at $z$ and the heavy direction at $y$ point in the same direction or in opposite directions.

The four cases are:

• LL: left-heavy at $z$, with the extra height in the left subtree of $y$.
• RR: right-heavy at $z$, with the extra height in the right subtree of $y$.
• LR: left-heavy at $z$, with the extra height in the right subtree of $y$.
• RL: right-heavy at $z$, with the extra height in the left subtree of $y$.

The names are path descriptions. For LL, the path from $z$ goes left and then left again. For LR, it goes left and then right. The same interpretation applies to RR and RL.

The LL case: one right rotation​

In an LL case, the left side of $z$ is too tall, and the left child’s left side contains the extra height. The shape is conceptually like this:

        z
       /
      y
     /
    x

The repair is a right rotation around $z$:

       y
      / \\
     x   z

The node $y$ rises to become the root of this local subtree. The node $z$ moves down to the right. Any middle subtree belonging between $y$ and $z$ must remain between them after the rotation.

Why does this help? Before the operation, the path to the extra height descends left twice. After the operation, that path is distributed across the two sides of $y$. The tall chain is shortened, while the sorted order remains intact.

A common way to recognize LL is that the unbalanced node has a positive balance factor under the left-height-minus-right-height convention, and its left child is also left-heavy or at least not right-heavy in the relevant update situation. The structural path is safer to remember than a sign-only rule: left, then left means a right rotation at the unbalanced node.

The RR case: one left rotation​

The RR case is the mirror image of LL. The right side of $z$ is too tall, and the right child’s right side contains the extra height:

    z
     \\
      y
       \\
        x

A left rotation around $z$ produces:

      y
     / \\
    z   x

Here, $y$ rises and $z$ moves down to the left. Again, an intermediate subtree is moved to the appropriate side without changing the in-order key sequence.

Under the left-height-minus-right-height convention, an RR imbalance is associated with a negative balance factor at $z$, while the right child points toward the right-heavy side. The operational memory aid is direct: right, then right means rotate left at the unbalanced node.

The LR case: two rotations​

The LR case begins with a left-heavy unbalanced node $z$, but the extra height is in the right subtree of its left child $y$:

        z
       /
      y
       \\
        x

A single right rotation around $z$ does not directly solve the zigzag shape. The first step is to rotate left around $y$:

        z
       /
      x
     /
    y

The shape has now been converted from a left-right path into a left-left path. The second step is a right rotation around $z$:

       x
      / \\
     y   z

This is why LR is called a double rotation. It is not a fundamentally different primitive from the single rotations; it is a composition of two local rotations that first straightens the zigzag and then repairs the resulting straight-line imbalance.

The order matters. Rotating around $z$ first would not align the heavy path in the intended way. The child-side rotation comes first, followed by the rotation at the original unbalanced node.

The RL case: two rotations​

The RL case is the mirror image of LR. The right side of $z$ is too tall, but the extra height is in the left subtree of the right child $y$:

    z
     \\
      y
     /
    x

First rotate right around $y$:

    z
     \\
      x
       \\
        y

Then rotate left around $z$:

      x
     / \\
    z   y

The path right then left becomes a straight right-heavy path before the final repair. The memory aid is: right, then left means rotate right at the child, followed by rotate left at the unbalanced node.

5. A reliable way to identify the case​

When the balance factor reports an imbalance, avoid choosing a rotation based only on the first sign you see. Use a two-level inspection.

First, identify the unbalanced node $z$. If $BF(z)=2$, the left side is too tall under the chosen convention. If $BF(z)=-2$, the right side is too tall.

Second, inspect the child on the heavy side. For a left-heavy node, inspect the left child. For a right-heavy node, inspect the right child. The direction from that child toward the extra height distinguishes a straight path from a zigzag path.

The decision table is:

This table is a structural description rather than a replacement for checking actual heights. The child may have a balance factor of zero in some deletion situations, so the exact sign test can depend on whether the update came from insertion or deletion. The path and the relative subtree heights remain the underlying idea.

6. Rebalancing after an update​

An update changes the shape of a tree. An insertion adds a new leaf position, while a deletion removes a node or replaces its position according to the binary-search-tree deletion process. In both situations, the heights of ancestors on the path back to the root may change.

The general maintenance pattern is:

1. Perform the ordinary binary-search-tree update.
2. Move upward through the affected ancestor path.
3. Recompute each node’s height from its children.
4. Compute its balance factor.
5. If the magnitude of the balance factor reaches two, apply the matching rotation or double rotation.
6. Continue checking ancestors when the update is a deletion, because a repaired subtree may still have a height effect above it.

The exact implementation can store parent links or use recursive return values to carry the changed subtree root upward. Those are implementation choices. The invariant is the same: each affected node must end with a correct height, and each node must satisfy the AVL balance rule after repair.

Why checking ancestors is necessary​

Suppose a node is deleted from the lower part of the tree. The immediate parent may become shorter. That height decrease can make the parent unbalanced, and repairing the parent can change the height of the parent’s parent. The effect can continue upward.

This is different from thinking of deletion as a single local event. The removed node is local, but height is a property inherited by every ancestor on the route to the root. Therefore, a correct delete-rebalance process does not stop merely because one rotation has been performed. It checks whether higher nodes remain valid.

The description specifically highlights rebalancing after a delete because deletion can expose imbalances that were not visible before the removal. A tree that was valid immediately before deletion is not automatically valid afterward.

7. Heights and balance factors after rotation​

A rotation changes the children of the nodes involved, so their heights must be recomputed. The safe conceptual order is bottom-up: update the node that moved downward first, then update the node that moved upward.

For any node $v$, its height is based on the larger child height plus one. Using an empty-subtree height denoted by $h_{\emptyset}$, the recurrence is

The base value for $h_{\emptyset}$ depends on the chosen convention. What matters is that the same value is used in height calculations and balance-factor calculations.

Consider a right rotation around $z$ with left child $y$. After the rotation, $z$ has a new left child, possibly the middle subtree, and $y$ has a new right child, namely $z$. The height of $z$ must be updated before the height of $y$, because $y$ now depends on the new height of $z$.

A stale height can cause a later balance-factor calculation to choose the wrong case. Thus, pointer changes and metadata changes are part of one logical operation. A rotation is not complete merely when the visual links look correct; the stored heights must describe that new shape.

8. Complexity of AVL operations​

The principal benefit of the AVL invariant is logarithmic height. For $n$ nodes, the height is $O(\log n)$. A search follows one root-to-leaf path, so its time is $O(\log n)$.

An insertion or deletion first follows a binary-search-tree path and then checks or repairs ancestors. The number of affected ancestors is bounded by the tree height, and each individual rotation changes only a constant-size local configuration. Therefore, the overall time for an update is $O(\log n)$.

The balancing work at one node is constant time once child heights are available. A single rotation or a double rotation performs a bounded number of link changes and height updates. The logarithmic total comes from walking through the height of the tree, not from the local rotation itself.

The extra storage for the tree is $O(n)$ for $n$ nodes. If every node stores its height or balance factor, the metadata adds constant extra information per node, so the asymptotic space remains $O(n)$. An implementation that uses recursion may also use a call stack whose depth is $O(\log n)$ in a balanced tree.

9. Worked structural examples​

Example A: LL imbalance​

Imagine a local path in which a new or retained heavy portion lies on the left of the left child:

        30
       /
      20
     /
    10

At node $30$, the left subtree is taller by two relative levels in the simplified picture. The path is left then left, so this is LL. Rotate right around $30$:

      20
     /  \\
    10   30

The smallest value remains at the far left, the largest remains at the far right, and the in-order sequence is unchanged.

Example B: RR imbalance​

Now consider the mirror image:

    10
      \\
       20
         \\
          30

The path is right then right, so this is RR. Rotate left around $10$:

      20
     /  \\
    10   30

The final local shape matches the previous example, even though the original imbalance developed in the opposite direction.

Example C: LR imbalance​

Consider a left-right path:

        30
       /
      10
        \\
         20

The first direction from $30$ is left, and the next direction is right. This is LR. Rotate left around $10$ to straighten the path, then rotate right around $30$:

      20
     /  \\
    10   30

The middle key becomes the local root because it was located at the bend in the path.

Example D: RL imbalance​

For a right-left path:

    10
      \\
       30
      /
     20

The path from $10$ goes right and then left. This is RL. Rotate right around $30$, then rotate left around $10$:

      20
     /  \\
    10   30

The two double-rotation cases therefore produce the same balanced three-key shape when their keys occupy corresponding positions. What differs is the direction in which the imbalance developed and the order of the two rotations needed to repair it.

10. Common mistakes when reasoning about AVL rotations​

Mistake 1: Treating any height difference as an immediate rotation​

The AVL rule permits a difference of one. A node with $BF(v)=1$ or $BF(v)=-1$ is still valid. Rotation is required when the magnitude reaches two, not merely when the two subtree heights are unequal.

Mistake 2: Choosing a rotation from the parent alone​

Knowing that a node is left-heavy does not distinguish LL from LR. The child’s heavy direction is also needed. A left-heavy node can have a straight left-left path or a bent left-right path, and the repairs differ.

Mistake 3: Forgetting the middle subtree​

A rotation does not simply swap two nodes. The subtree between the rising child and the falling node must be reattached. Omitting it can lose nodes or violate the binary-search-tree ordering.

Mistake 4: Updating heights in the wrong order​

The node that moves downward usually depends on fewer or newly changed links and should be updated before the node that moves upward. If heights remain stale, later balance factors become unreliable.

Mistake 5: Stopping after the first delete repair​

Deletion can shorten a subtree and affect multiple ancestors. A rotation may repair one node while leaving a higher ancestor needing examination. The upward check must continue as required by the implementation’s update process.

Mistake 6: Confusing a rotation with a complete update​

A rotation repairs shape locally, but a full update also requires correct parent links or returned subtree roots, updated height metadata, and continued invariant checks. All of these pieces are part of maintaining an AVL tree.

11. A practical mental checklist​

When viewing an AVL animation or debugging an implementation, use this sequence:

1. Find the node whose two child-subtree heights differ by two.
2. Decide which side is taller.
3. Follow the heavy side to the relevant child.
4. Decide whether the path is straight or bent.
5. Match the path to LL, RR, LR, or RL.
6. Apply one rotation for a straight path and two for a bent path.
7. Reattach every middle subtree in its order-preserving position.
8. Recompute the affected heights.
9. Continue upward after deletion and verify higher ancestors.
10. Confirm that every balance factor is in the interval from $-1$ through $1$.

This checklist separates diagnosis from repair. First understand the shape; then choose the operation. Memorizing isolated pictures is less reliable than reading the direction sequence.

12. Final perspective​

An AVL tree is a binary search tree with a strict local height invariant. At each node, the left and right subtree heights may be equal or differ by one, but a difference of two indicates that the local shape must be repaired. The balance factor turns that visual rule into a measurable condition.

The four cases describe where the extra height lies. LL and RR are straight-line cases repaired by one rotation. LR and RL are zigzag cases repaired by two rotations: first rotate the child to straighten the path, then rotate the unbalanced node to restore balance.

The rotations preserve the sorted order of the keys while redistributing the local height. Correct height updates and continued ancestor checks are especially important after deletion, because removing a node can shorten a subtree and affect balance all the way toward the root.

The essential idea can be summarized mathematically as follows:

Once the balance factor identifies the heavy side and the path identifies the case, the rotation choice becomes systematic rather than mysterious. That is the practical lesson behind “heights off by two? Rotate.”