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


GNU libavl 2.0.1

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

15.5.1 Step 2: Delete

The actual deletion step is derived from that for PBSTs. We add code to modify balance factors and set up for rebalancing. 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. This follows the pattern already seen in TAVL deletion (see section 9.5.2 Step 2: Delete).

 
if (p-&#62;pavl_link[1] == NULL)
  { 
&#60;@xref{\NODE\, , Case 1 in PAVL deletion.&#62;,536}
} else
{ struct pavl_node *r = p-&#62;pavl_link[1]; if (r-&#62;pavl_link[0] == NULL) {
&#60;@xref{\NODE\, , Case 2 in PAVL deletion.&#62;,537}
} else
{
&#60;@xref{\NODE\, , Case 3 in PAVL deletion.&#62;,538}
} } tree-&#62;pavl_alloc-&#62;libavl_free (tree-&#62;pavl_alloc, p);
This code is included in @refalso{534

Case 1: p has no right child

No changes are needed for case 1. No balance factors need change and q and dir are already set up correctly.

 
&#60;@xref{\NODE\, , Case 1 in PBST deletion; pbst =>.&#62; pavl,497}
This code is included in @refalso{535

Case 2: p's right child has no left child

See the commentary on &#60;@xref{\NODE\, , Case 3 in TAVL deletion.&#62;,316} for details.

 
&#60;@xref{\NODE\, , Case 2 in PBST deletion; pbst =>.&#62; pavl,498}
r-&#62;pavl_balance = p-&#62;pavl_balance;
q = r;
dir = 1;
This code is included in @refalso{535

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

See the commentary on &#60;@xref{\NODE\, , Case 4 in TAVL deletion.&#62;,317} for details.

 
&#60;@xref{\NODE\, , Case 3 in PBST deletion; pbst =>.&#62; pavl,499}
s-&#62;pavl_balance = p-&#62;pavl_balance;
q = r;
dir = 0;
This code is included in @refalso{535


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

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