AVL Tree: The Self-Balancing BST

An AVL tree is a self-balancing binary search tree, or BST. It preserves the ordinary BST ordering rule while enforcing an additional height constraint: at every node, the left and right subtrees must have nearly equal heights.

That extra invariant prevents the tree from gradually becoming a long, one-sided chain. When an insertion or deletion makes a node too heavy on one side, the AVL tree repairs its shape using one or two local rotations.

The main ideas are:

• Keys smaller than a node's key belong in its left subtree.
• Keys larger than a node's key belong in its right subtree.
• Each node has a balance factor based on the heights of its two child subtrees.
• A balance factor of -1, 0, or +1 is valid under the standard convention.
• A balance factor of +2 or -2 indicates that rebalancing is required.
• The four repair patterns are left-left, right-right, left-right, and right-left.
• Insertion and deletion both require upward height and balance updates, but deletion can require fix-up at several ancestors.

This article explains the AVL invariant, balance factors, height maintenance, rotations, insertion, deletion, implementation structure, testing, and complexity. The goal is to make the tree's shape and update behavior easy to reason about rather than treating rotations as disconnected diagrams to memorize.

1. Why an ordinary BST can become inefficient​

A binary search tree uses ordering to guide operations. At a node, compare the target key with the node's key:

• If the target is smaller, continue in the left subtree.
• If the target is larger, continue in the right subtree.
• If the keys match, the target has been found.

This directed search is efficient when the tree has a reasonably small height. However, the ordinary BST ordering rule does not guarantee a good shape.

For example, insert the keys 10, 20, and 30 in that order into an ordinary BST:

10
  \\
   20
     \\
      30

This is still a valid BST. Every key on the right is greater than the key above it. The problem is the shape: the tree resembles a linked list. A search for 30 must visit 10, then 20, then 30. If more keys arrive in sorted order, the chain becomes longer.

An AVL tree detects the imbalance created by this update sequence and restructures the local region:

   20
  /  \\
10    30

The keys have not changed, and their sorted order has not changed. Only the parent-child relationships have changed. This is the essential role of a rotation: preserve the BST ordering while producing a shorter, more balanced shape.

The cost of searching, inserting, or deleting in a tree is closely related to its height. A balanced tree keeps root-to-leaf paths short; a highly skewed tree can force operations to follow nearly every node.

2. The AVL balance invariant​

The defining AVL condition is local. At every node, the heights of the left and right subtrees may differ by at most one.

A common balance-factor definition is:

balance factor = height(left subtree) - height(right subtree)

With this convention, the valid balance factors are:

-1, 0, +1

Their meanings are:

• 0: the left and right subtrees have equal height.
• +1: the left subtree is one level taller.
• -1: the right subtree is one level taller.
• +2: the node is too heavy on the left.
• -2: the node is too heavy on the right.

A factor outside the range [-1, +1] means that the node needs a rotation-based repair. The signs depend on the convention. Some implementations calculate height(right) - height(left) instead. That reverses the signs but not the underlying structure or algorithm.

The condition must hold at every node, not only at the root. A root can have two subtrees with similar heights while a node several levels below is already unbalanced. Therefore, insertion and deletion must inspect the ancestors along the path affected by the update.

This local invariant has a global effect. If every node keeps its two child heights close, the tree cannot grow into an arbitrarily long one-sided chain. Its height remains logarithmic in the number of stored nodes.

3. Heights and stored metadata​

To calculate a balance factor, an implementation needs the heights of the child subtrees. A node's height can be defined as:

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

The height of an empty subtree must also be defined. One implementation may use 0; another may use -1. Both choices are valid as long as the same convention is used everywhere.

For example, under a convention where an empty subtree has height 0, a leaf has height 1. Under a convention where an empty subtree has height -1, a leaf has height 0. The numerical values differ, but the balance comparisons work the same way if the implementation is consistent.

Many AVL implementations store a height field in each node:

Node:
    key
    left child reference
    right child reference
    height

Storing the height avoids repeatedly traversing entire subtrees just to calculate metadata. Whenever a child link changes, the node's height must be updated. That update can change the balance factor, which may affect the node's parent. This creates the upward propagation pattern used by both insertion and deletion.

A typical ancestor update follows this sequence:

1. Recompute the current node's height from its children.
2. Compute its balance factor.
3. Determine whether the node is balanced.
4. If it is unbalanced, perform the appropriate rotation or double rotation.
5. Return the resulting root of this local subtree to the caller.

Returning the local root is essential because a rotation can change which node represents a subtree.

4. Rotations preserve BST ordering​

A rotation is a local restructuring operation. It changes a small number of links, but it preserves the in-order sequence of keys.

Consider five ordered regions or keys arranged as:

A < x < B < y < C

A rotation may change whether x or y is the root of the local region. However, an in-order traversal still visits the elements in this order:

A, x, B, y, C

That property makes rotations safe for binary search trees. They change shape without changing the sorted arrangement.

There are two primitive operations:

• A right rotation moves a left child upward.
• A left rotation moves a right child upward.

The four AVL cases are combinations of those operations:

1. Left-left: one right rotation.
2. Right-right: one left rotation.
3. Left-right: left rotation followed by right rotation.
4. Right-left: right rotation followed by left rotation.

The names describe the direction of the heavy path from the unbalanced node toward the changed subtree.

5. Right rotation​

A right rotation is used when a node is too heavy on the left and its left child leans left or is balanced.

Before the rotation:

        y
       / \\
      x   C
     / \\
    A   B

After rotating right around y:

        x
       / \\
      A   y
         / \\
        B   C

The link changes are:

1. Save x, the left child of y.
2. Move x's right subtree, represented by B, to become y's left subtree.
3. Make y the right child of x.
4. Attach x to the former parent of y, or make x the tree root if y was the root.
5. Update heights from the lower node upward.

The subtree B is the important middle piece. It is larger than x but smaller than y, so it can move from x's right side to y's left side without breaking ordering.

Left-left example​

Insert 30, then 20, then 10:

    30
   /
  20
 /
10

At node 30, the left subtree is too tall. Its left child, 20, is also left-heavy. This is the left-left case. A right rotation at 30 gives:

   20
  /  \\
10    30

The local height is reduced, and the in-order sequence remains 10, 20, 30.

6. Left rotation​

A left rotation is the mirror image of a right rotation. It is used when a node is too heavy on the right and its right child leans right or is balanced.

Before the rotation:

    x
   / \\
  A   y
     / \\
    B   C

After rotating left around x:

        y
       / \\
      x   C
     / \\
    A   B

The steps are:

1. Save y, the right child of x.
2. Move y's left subtree, B, to become x's right subtree.
3. Make x the left child of y.
4. Attach y to the former parent of x, or make y the tree root if x was the root.
5. Update heights from the lower node upward.

Right-right example​

Insert 10, then 20, then 30:

10
  \\
   20
     \\
      30

Node 10 is right-heavy, and its right child 20 is also right-heavy. This is the right-right case. A left rotation at 10 produces:

   20
  /  \\
10    30

The rotation preserves the sorted sequence while preventing the tree from remaining a chain.

7. The four imbalance cases​

The balance factor of the unbalanced node identifies the heavy side. The balance factor of the heavy child identifies whether the path continues straight or turns.

7.1 Left-left case​

The node is left-heavy, and its left child is left-heavy or balanced:

      z
     /
    y
   /
  x

Repair with one right rotation at z.

7.2 Right-right case​

The node is right-heavy, and its right child is right-heavy or balanced:

  z
   \\
    y
     \\
      x

Repair with one left rotation at z.

7.3 Left-right case​

The node is left-heavy, but its left child is right-heavy:

      z
     /
    y
     \\
      x

The heavy path turns. Repair it in two stages:

1. Left-rotate at y.
2. Right-rotate at z.

The first rotation changes the local shape into a left-left case. The second rotation completes the repair.

7.4 Right-left case​

The node is right-heavy, but its right child is left-heavy:

  z
   \\
    y
   /
  x

Repair it in two stages:

1. Right-rotate at y.
2. Left-rotate at z.

The first rotation converts the shape into a right-right case, after which the second rotation restores balance.

8. Insertion process​

AVL insertion begins with ordinary BST insertion. Compare the new key with each node and move left or right until an empty child position is found. The new key is attached as a leaf.

The new leaf itself is balanced. The possible imbalance occurs at its ancestors because the height of one descendant path may have increased. The algorithm therefore travels back toward the root, updating heights and checking balance factors.

A high-level recursive structure is:

insert(node, key):
    if node is empty:
        return new leaf containing key

    if key < node.key:
        node.left = insert(node.left, key)
    else if key > node.key:
        node.right = insert(node.right, key)
    else:
        handle the duplicate according to the chosen policy

    update node.height
    return rebalance(node)

The recursive call returns the possibly changed root of the child subtree. The current node assigns that returned value back to node.left or node.right. Then the current node itself is updated and potentially rotated.

This return value is particularly important when a rotation occurs below the root. Suppose a left rotation changes the root of a subtree from x to y. The parent must reconnect its child reference to y, not continue pointing to x.

Left-right insertion example​

Insert 30, then 10, then 20:

    30
   /
  10
    \\
     20

At 30, the tree is left-heavy. The left child 10, however, is right-heavy. Therefore, the pattern is left-right.

First rotate left around 10:

    30
   /
  20
  /
10

Then rotate right around 30:

   20
  /  \\
10    30

The two rotations are not arbitrary. The first removes the turn in the heavy path, and the second corrects the remaining left-heavy root.

9. Deletion and why it needs special care​

AVL deletion also begins as an ordinary BST deletion. The target node can have three structural forms:

• No children: remove the leaf.
• One child: replace the node with its only child.
• Two children: replace its key or position using an ordered neighboring node, then remove that replacement node from its original location.

The structural deletion can decrease the height of a subtree. That decrease may make the parent unbalanced. After a rotation, the repaired subtree may still be shorter than it was before deletion, so the height change can continue upward and affect additional ancestors.

This is the important difference between insertion and deletion fix-up:

• Insertion can make a path taller.
• Deletion can make a path shorter.
• A deletion-related height decrease may cause more than one ancestor to become unbalanced.

A deletion algorithm therefore continues checking ancestors toward the root. At every node it recomputes the height, calculates the balance factor, applies a suitable rotation if necessary, and then continues upward.

A high-level structure is:

delete(node, key):
    perform ordinary BST deletion
    if node is now empty:
        return empty

    update node.height
    return rebalance(node)

In a recursive implementation, the return from the child deletion carries the changed subtree root upward. The caller then updates its own link, height, and balance. The recursion naturally provides the path on which fix-up is performed.

10. Deleting a node with two children​

When the target has two children, the replacement must preserve BST order. A common approach is to choose an ordered neighboring key from one of the child subtrees. For example, an implementation can copy a suitable key from the right subtree into the target node, then delete the original node containing that copied key.

The balancing path begins where the actual node was physically removed. This point matters because copying a key does not change subtree height at the original target position. The height change occurs where the replacement node is removed.

For example, suppose a node has a left subtree and a right subtree, and a replacement key is selected from the right subtree. The key can be copied into the target node, but the original replacement node still exists lower in the right subtree until it is removed. The fix-up must begin from that lower location and travel back toward the root.

Different implementations may use different ordered replacement choices. The essential requirements are the same:

1. The replacement maintains the BST ordering property.
2. The original replacement node is physically removed.
3. Heights are updated from the removal point upward.
4. Every affected ancestor is checked for balance.

11. Deletion fix-up decisions​

The same four rotation families are used during deletion. The child balance factor can sometimes be zero in a single-rotation case, so the deletion conditions should account for balanced heavy children as well.

Using:

balance = height(left subtree) - height(right subtree)

If the current node has balance +2, it is too heavy on the left:

• If its left child has a nonnegative balance, perform a right rotation.
• If its left child has a negative balance, left-rotate the left child and then right-rotate the current node.

If the current node has balance -2, it is too heavy on the right:

• If its right child has a nonpositive balance, perform a left rotation.
• If its right child has a positive balance, right-rotate the right child and then left-rotate the current node.

After each rotation, update heights and keep moving toward the root. Do not automatically stop after the first repair. A deletion can have changed the height of a large part of the path.

12. Rebalancing decision table​

The following table summarizes the cases under the standard balance-factor convention:

This table is compact, but it depends on consistent metadata. If the implementation uses the opposite balance-factor sign convention, the comparisons must be reversed accordingly.

A useful mental shortcut is:

• Find the side that is too tall.
• Look at whether the heavy child leans in the same direction or turns inward.
• A straight path needs one rotation.
• A turning path needs two rotations.

13. Why rotations preserve search order​

Consider the right-rotation pattern:

        y
       / \\
      x   C
     / \\
    A   B

The ordering relationships are:

all keys in A < x < all keys in B < y < all keys in C

After the rotation:

        x
       / \\
      A   y
         / \\
        B   C

The relationships remain exactly the same. The keys in A are still below x; the keys in B are still between x and y; and the keys in C are still greater than y.

Therefore, an in-order traversal produces the same sorted sequence before and after the rotation. A left rotation follows the mirror-image argument, and a double rotation is simply two ordering-preserving rotations performed in sequence.

This gives a practical debugging rule: if a rotation changes the in-order sequence, some pointer was connected incorrectly.

14. Complexity and the importance of height​

A BST operation usually follows a root-to-leaf path. Its running time is therefore related to the tree's height.

An AVL tree maintains a strict local balance condition: the two child subtree heights differ by at most one at every node. That condition keeps the overall height logarithmic in the number of nodes. As a result, search, insertion, and deletion have logarithmic height-based complexity.

A single rotation changes only a constant number of links, so the repair at one node takes constant time. An update may inspect the ancestors on the affected path, but the path length is bounded by the AVL tree's height rather than by the total number of nodes.

Insertion typically follows the search path down and then updates ancestors on the way back up. Deletion follows a similar path but may perform several local repairs because a height decrease can propagate. The presence of multiple possible repairs does not turn deletion into a full-tree scan; the work remains associated with the height of the tree.

The central performance benefit of AVL balancing is therefore structural. The tree does not need to rebuild or sort all keys after an update. It makes local changes that preserve ordering and keep the height controlled.

15. A clean implementation structure​

An AVL implementation is easier to verify when its responsibilities are divided into small helpers.

Node metadata​

Each node should contain its key and references to its left and right children. If heights are stored, each node should also contain its current height.

Height helper​

Use one helper to return the height of an empty subtree and the stored height of a nonempty node. Choose the empty-subtree convention once and use it consistently.

Balance helper​

Use one balance function, such as:

balance(node) = height(node.left) - height(node.right)

Centralizing this calculation reduces the chance that one branch of the update algorithm will accidentally use the opposite sign.

Rotation helpers​

Implement rotateLeft and rotateRight independently. Each helper should:

1. Save the pivot child.
2. Move the pivot's inner subtree.
3. Reconnect the two main nodes.
4. Update heights in bottom-up order.
5. Return the new root of the local subtree.

The inner subtree must not be discarded. In the right-rotation diagram, B moves from the right side of x to the left side of y. In the left-rotation diagram, the mirror-image subtree moves in the opposite direction.

Rebalance helper​

A rebalance routine can update the current height, calculate the balance factor, choose the appropriate case, perform the needed rotation or double rotation, and return the new local root.

With this structure, insertion and deletion can focus on locating and changing keys. The shared rebalancing logic handles the invariant.

16. Common implementation mistakes​

Forgetting to return the new subtree root​

A rotation changes the root of a local subtree. If the caller does not receive that new root and reconnect it, the rotation may appear ineffective or may disconnect part of the tree.

Losing the external root reference​

If the root itself is rotated, the tree's root pointer must be replaced with the returned root. This is a common error because rotations below the root may appear to work while root rotations silently leave the external reference pointing to the wrong node.

Updating heights in the wrong order​

After a left rotation, the node that moves downward should have its height updated before the node that moves upward. The same rule applies to a right rotation. The upper node's height depends on the already-correct height of the lower node.

Checking only the root​

The AVL invariant applies to every node. A root-only check can miss an unbalanced node deeper in the tree.

Looking at only one balance factor​

The balance of the unbalanced node identifies the heavy side, but the balance of the heavy child identifies whether the case is straight or turning. Both pieces of information are needed to distinguish a single rotation from a double rotation.

Stopping deletion repair too early​

Deletion can reduce subtree height and affect multiple ancestors. A fix-up routine should continue toward the root after a local repair.

Mishandling duplicates​

A BST needs a clear policy for equal keys. An implementation may reject duplicates, store a count in one node, or place equal keys consistently on one side. Search, insertion, deletion, and validation must all follow the same policy.

Discarding the middle subtree during rotation​

The inner subtree, such as B in the rotation diagrams, contains keys that must remain in the tree. It needs to be moved, not overwritten or ignored.

17. Testing an AVL implementation​

Testing should verify both properties that define the data structure:

1. It is still a valid BST.
2. It is still balanced according to the AVL invariant.

Useful validation checks include:

• An in-order traversal is sorted according to the duplicate-key policy.
• Every stored height agrees with the heights of the child subtrees.
• Every balance factor is in [-1, +1] after a completed update.
• Every inserted key can be found.
• Every removed key is absent.
• The root remains reachable after a root rotation.
• All four rotation cases produce the expected local shape.
• Deletion works for leaves, nodes with one child, and nodes with two children.
• Repeated insertions and deletions do not disconnect nodes.

Small hand-built insertion sequences are particularly useful because the expected result is easy to inspect:

30, 20, 10   -> left-left
10, 20, 30   -> right-right
30, 10, 20   -> left-right
10, 30, 20   -> right-left

For deletion, test removing a leaf from a balanced tree, removing a node with one child, removing a node with two children, and repeatedly removing keys until the tree is empty. Validate the invariants after every operation rather than checking only the final tree.

In-order traversal is especially valuable. If the tree's in-order output is no longer sorted, the BST ordering has been broken. If the order is correct but a stored height or balance factor is wrong, the structural links may be valid while the metadata maintenance is not.

18. Using traversals to inspect shape​

Different traversals reveal different aspects of an AVL tree.

An in-order traversal visits keys in sorted order. It is the best basic check for the BST property.

A pre-order traversal visits each local root before its children. It helps show which node became the root after a rotation.

A level-order traversal visits nodes by depth. It gives an intuitive view of how evenly values are distributed across levels.

For this tree:

   20
  /  \\
10    30

The traversals are:

• In-order: 10, 20, 30
• Pre-order: 20, 10, 30
• Level-order: 20, 10, 30

Before and after a rotation, the in-order traversal can remain identical while the pre-order traversal changes. That is expected: the set and sorted order of keys remain the same, but the root of the local region changes.

19. A mental model for update propagation​

A useful way to understand AVL updates is to imagine a height change traveling upward.

During insertion, a new leaf may make one descendant path taller. The algorithm carries this change toward the root. At each ancestor it asks whether the two child heights still differ by at most one. If the answer is no, it identifies the heavy path and rotates.

During deletion, removing a node may make one descendant path shorter. The algorithm carries that decrease upward. A node that was balanced before deletion may now become heavy on the opposite side. A rotation can repair that node, but the repaired subtree may still be shorter than before, so the change can continue to higher ancestors.

This mental model unifies all four cases. At each unbalanced node, ask:

1. Which side is too tall?
2. Does the heavy child lean in the same direction or toward the inside?
3. Use one rotation for a straight heavy path.
4. Use two rotations for a turning heavy path.
5. Recompute heights and continue checking ancestors.

The diagrams are therefore consequences of the height invariant, not independent tricks.

20. Practical takeaways​

An AVL tree combines two responsibilities:

• The BST ordering rule determines where a key belongs.
• The AVL balance invariant determines when the shape must be repaired.

The balance factor connects these responsibilities. Under the convention height(left) - height(right), factors of -1, 0, and +1 are valid. A factor of +2 means left-heavy imbalance, while -2 means right-heavy imbalance.

The four cases can be remembered as directional paths:

• Left-left: right rotation.
• Right-right: left rotation.
• Left-right: left rotation, then right rotation.
• Right-left: right rotation, then left rotation.

Insertion follows the normal BST search path, adds a leaf, and then rebalances affected ancestors. Deletion performs normal BST removal but requires especially careful upward fix-up because a subtree height can decrease and cause several ancestors to need attention.

The most important implementation practices are:

• Choose one height convention and use it everywhere.
• Choose one balance-factor sign convention and use it everywhere.
• Preserve the middle subtree during every rotation.
• Update heights from lower nodes to higher nodes.
• Return the new root after every local rotation.
• Replace the external tree root when the root rotates.
• Continue deletion fix-up toward the root.
• Validate both sorted order and balance after updates.

When these rules are applied together, an AVL tree preserves the useful search behavior of a BST while preventing the extreme one-sided shapes that make an ordinary BST inefficient.