5.5.3 Step 3: Update Balance Factors

When we updated balance factors in insertion, we were lucky enough to know in advance which ones we'd need to update. Moreover, we never needed to rebalance at more than one level in the tree for any one insertion. These two factors conspired in our favor to let us do all the updating of balance factors at once from the top down.

Everything is not quite so simple in AVL deletion. We don't have any easy way to figure out during the search process which balance factors will need to be updated, and for that matter we may need to perform rebalancing at multiple levels. Our strategy must change.

This new approach is not fundamentally different from the previous one. We work from the bottom up instead of from the top down. We potentially look at each of the nodes along the direct path from the deleted node to the tree's root, starting at pa[k - 1], the parent of the deleted node. For each of these nodes, we adjust its balance factor and possibly perform rebalancing. After that, if we're lucky, this was enough to restore the tree's balancing rule, and we are finished with updating balance factors and rebalancing. Otherwise, we look at the next node, repeating the process.

Here is the loop itself with the details abstracted out:

173. <Steps 3–4: Update balance factors and rebalance after AVL deletion 173> =
assert (k > 0);
while (--k > 0) 
  {
    struct avl_node *y = pa[k];

    if (da[k] == 0)
      { 
        <Update y's balance factor after left-side AVL deletion 174> 
      }
    else 
      { 
        <Update y's balance factor after right-side AVL deletion 179> 
      }
  }

This code is included in 166.

The reason this works is the loop invariants. That is, because each time we look at a node in order to update its balance factor, the situation is the same. In particular, if we're looking at a node pa[k], then we know that it's because the height of its subtree on side da[k] decreased, so that the balance factor of node pa[k] needs to be updated. The rebalancing operations we choose reflect this invariant: there are sometimes multiple valid ways to rebalance at a given node and propagate the results up the tree, but only one way to do this while maintaining the invariant. (This is especially true in red-black trees, for which we will develop code for two possible invariants under insertion and deletion.)

Updating the balance factor of a node after deletion from its left side and right side are symmetric, so we'll discuss only the left-side case here and construct the code for the right-side case later. Suppose we have a node y whose left subtree has decreased in height. In general, this increases its balance factor, because the balance factor of a node is the height of its right subtree minus the height of its left subtree. More specifically, there are three cases, treated individually below.

Case 1: y has - balance factor

If y started with a - balance factor, then its left subtree was taller than its right subtree. Its left subtree has decreased in height, so the two subtrees must now be the same height and we set y's balance factor to 0. This is between -1 and +1, so there is no need to rebalance at y. However, binary tree y has itself decreased in height, so that means that we must rebalance the AVL tree above y as well, so we continue to the next iteration of the loop.

The diagram below may help in visualization. On the left is shown the original configuration of a subtree, where subtree a has height h and subtree b has height h - 1. The height of a nonempty binary tree is one plus the larger of its subtrees' heights, so tree y has height h + 1. The diagram on the right shows the situation after a node has been deleted from a, reducing that subtree's height. The new height of tree y is (h - 1) + 1 == h.

Case 2: y has 0 balance factor

If y started with a 0 balance factor, and its left subtree decreased in height, then the result is that its right subtree is now taller than its left subtree, so the new balance factor is +. However, the overall height of binary tree y has not changed, so no balance factors above y need to be changed, and we are done, hence we break to exit the loop.

Here's the corresponding diagram, similar to the one for the previous case. The height of tree y on both sides of the diagram is h + 1, since y's taller subtree in both cases has height h.

Case 3: y has + balance factor

Otherwise, y started with a + balance factor, so the decrease in height of its left subtree, which was already shorter than its right subtree, causes a violation of the AVL constraint with a +2 balance factor. We need to rebalance. After rebalancing, we may or may not have to rebalance further up the tree.

Here's a diagram of what happens to forcing rebalancing:

Implementation

The implementation is straightforward:

174. <Update y's balance factor after left-side AVL deletion 174> =
y->avl_balance++;
if (y->avl_balance == +1)
  break;
else if (y->avl_balance == +2)
  { 
    <Step 4: Rebalance after AVL deletion 175> 
  }

This code is included in 173.