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)

{structavl_node*y=pa[k];if(da[k] == 0) {

<Updatey's balance factor after left-side AVL deletion 174>

}else

{

<Updatey'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.

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*.

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*.

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:

The implementation is straightforward:

174. <Updatey's balance factor after left-side AVL deletion 174> =y->avl_balance++;if(y->avl_balance== +1)break;elseif(y->avl_balance== +2) {

<Step 4: Rebalance after AVL deletion 175>

}

This code is included in 173.