www.delorie.com/gnu/docs/avl/libavl_162.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.5.2 Step 2: Delete

The cases for deletion are the same as for a TBST (see section 8.7 Deletion). 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.

 
if (p-&#62;tavl_tag[1] == TAVL_THREAD) 
{ if (p-&#62;tavl_tag[0] == TAVL_CHILD) {
&#60;@xref{\NODE\, , Case 1 in TAVL deletion.&#62;,314}
} else
{
&#60;@xref{\NODE\, , Case 2 in TAVL deletion.&#62;,315}
} }
else
{ struct tavl_node *r = p-&#62;tavl_link[1]; if (r-&#62;tavl_tag[0] == TAVL_THREAD) {
&#60;@xref{\NODE\, , Case 3 in TAVL deletion.&#62;,316}
} else
{
&#60;@xref{\NODE\, , Case 4 in TAVL deletion.&#62;,317}
} } tree-&#62;tavl_alloc-&#62;libavl_free (tree-&#62;tavl_alloc, p);
This code is included in @refalso{311

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:

 
&#60;@xref{\NODE\, , Case 1 in TBST deletion; tbst =>.&#62; tavl,260}
This code is included in @refalso{313

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:

 
&#60;@xref{\NODE\, , Case 2 in TBST deletion; tbst =>.&#62; tavl,261}
This code is included in @refalso{313

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.

 
&#60;@xref{\NODE\, , Case 3 in TBST deletion; tbst =>.&#62; tavl,262}
r-&#62;tavl_balance = p-&#62;tavl_balance;
q = r;
dir = 1;
This code is included in @refalso{313

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.

 
&#60;@xref{\NODE\, , Case 4 in TBST deletion; tbst =>.&#62; tavl,263}
s-&#62;tavl_balance = p-&#62;tavl_balance;
q = r;
dir = 0;
This code is included in @refalso{313

Exercises:

1. Rewrite &#60;@xref{\NODE\, , Case 4 in TAVL deletion.&#62;,317} 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]


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003