5.5.2 Step 2: Delete |

At this point, we've identified *p* as the node to delete. The node
on the top of the stack, *da*[*k* - 1], is *p*'s parent node. There are the same
three cases we saw in deletion from an ordinary BST (see Deleting from a BST), with the addition of code to copy balance factors and
update the stack.

The code for selecting cases is the same as for BSTs:

168. <Step 2: Delete item from AVL tree 168> =if(p->avl_link[1] ==NULL) { <Case 1 in AVL deletion 170> }else

{structavl_node*r=p->avl_link[1];if(r->avl_link[0] ==NULL) {

<Case 2 in AVL deletion 171>

}else

{

<Case 3 in AVL deletion 172>

} }

See also 169.

This code is included in 166.

Regardless of the case, we are in the same situation after the
deletion: node *p* has been removed from the tree and the stack
contains *k* nodes at which rebalancing may be necessary. Later code
may change *p* to point elsewhere, so we free the node immediately. A
pointer to the item data has already been saved in *item*
(see avldelsaveitem):

169. <Step 2: Delete item from AVL tree 168> +=tree->avl_alloc->libavl_free(tree->avl_alloc,p);

If *p* has no right child, then we can replace it with its left child,
the same as for BSTs (see bstdelcase1).

170. <Case 1 in AVL deletion 170> =pa[k- 1]->avl_link[da[k- 1]] =p->avl_link[0];

This code is included in 168.

If *p* has a right child *r*, which in turn has no left child, then we
replace *p* by *r*, attaching *p*'s left child to *r*, as we would in
an unbalanced BST (see bstdelcase2). In addition, *r* acquires
*p*'s balance factor, and *r* must be added to the stack of nodes
above the deleted node.

171. <Case 2 in AVL deletion 171> =r->avl_link[0] =p->avl_link[0];r->avl_balance=p->avl_balance;pa[k- 1]->avl_link[da[k- 1]] =r;da[k] = 1;pa[k++] =r;

This code is included in 168.

If *p*'s right child has a left child, then this is the third and most
complicated case. On the other hand, as a modification from the third
case in an ordinary BST deletion (see bstdelcase3), it is rather
simple. We're deleting the inorder successor of *p*, so we push the
nodes above it onto the stack. The only trickery is that we do not
know in advance the node that will replace *p*, so we reserve a spot
on the stack for it (*da*[*j*]) and fill it in later:

172. <Case 3 in AVL deletion 172> =structavl_node*s;intj=k++;for(;;)

{da[k] = 0;pa[k++] =r;s=r->avl_link[0];if(s->avl_link[0] ==NULL)break;r=s; }s->avl_link[0] =p->avl_link[0];r->avl_link[0] =s->avl_link[1];s->avl_link[1] =p->avl_link[1];s->avl_balance=p->avl_balance;pa[j- 1]->avl_link[da[j- 1]] =s;da[j] = 1;pa[j] =s;

This code is included in 168.

**Exercises:**

**1.** Write an alternate version of <Case 3 in AVL deletion 172> that moves data
instead of pointers, as in Exercise 4.8-2.
[answer]

**2.** Why is it important that the item data was saved earlier? (Why
couldn't we save it just before freeing the node?)
[answer]