8.5.2 Step 2: Delete

The cases for deletion are the same as for a TBST (see Deleting from a TBST). The difference is that we have to copy around balance factors and keep track of where balancing needs to start. After the deletion, q is the node at which balance factors must be updated and possible rebalancing occurs and dir is the side of q from which the node was deleted. For cases 1 and 2, q need not change from its current value as the parent of the deleted node. For cases 3 and 4, q will need to be changed.

315. <Step 2: Delete item from TAVL tree 315> =
if (p->tavl_tag[1] == TAVL_THREAD) 
  {
    if (p->tavl_tag[0] == TAVL_CHILD)
      { 
        <Case 1 in TAVL deletion 316> 
      }
    else 
      { 
        <Case 2 in TAVL deletion 317> 
      }
  } 
else 
  {
    struct tavl_node *r = p->tavl_link[1];
    if (r->tavl_tag[0] == TAVL_THREAD)
      { 
        <Case 3 in TAVL deletion 318> 
      }
    else 
      { 
        <Case 4 in TAVL deletion 319> 
      }
  }

tree->tavl_alloc->libavl_free (tree->tavl_alloc, p);

This code is included in 313.

Case 1: p has a right thread and a left child

If p has a right thread and a left child, then we replace it by its left child. Rebalancing must begin right above p, which is already set as q. There's no need to change the TBST code:

316. <Case 1 in TAVL deletion 316> =
<Case 1 in TBST deletion; tbst => tavl 262>

This code is included in 315.

Case 2: p has a right thread and a left thread

If p is a leaf, then we change q's pointer to p into a thread. Again, rebalancing must begin at the node that's already set up as q and there's no need to change the TBST code:

317. <Case 2 in TAVL deletion 317> =
<Case 2 in TBST deletion; tbst => tavl 263>

This code is included in 315.

Case 3: p's right child has a left thread

If p has a right child r, which in turn has no left child, then we move r in place of p. In this case r, having replaced p, acquires p's former balance factor and rebalancing must start from there. The deletion in this case is always on the right side of the node.

318. <Case 3 in TAVL deletion 318> =
<Case 3 in TBST deletion; tbst => tavl 264>
r->tavl_balance = p->tavl_balance;
q = r;
dir = 1;

This code is included in 315.

Case 4: p's right child has a left child

The most general case comes up when p's right child has a left child, where we replace p by its successor s. In that case s acquires p's former balance factor and rebalancing begins from s's parent r. Node s is always the left child of r.

319. <Case 4 in TAVL deletion 319> =
<Case 4 in TBST deletion; tbst => tavl 265>
s->tavl_balance = p->tavl_balance;
q = r;
dir = 0;

This code is included in 315.

Exercises:

1. Rewrite <Case 4 in TAVL deletion 319> to replace the deleted node's tavl_data by its successor, then delete the successor, instead of shuffling pointers. (Refer back to Exercise 4.8-3 for an explanation of why this approach cannot be used in libavl.) [answer]