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


GNU libavl 2.0.1

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

16.4.1 Step 2: Delete

The goal of this step is to remove p from the tree and set up f as the node where rebalancing should start. Secondarily, we set dir as the side of f from which the node was deleted. Together, f and dir fill the role that the top-of-stack entries in pa[] and da[] took in ordinary RB deletion.

 
if (p-&#62;prb_link[1] == NULL)
  { 
&#60;@xref{\NODE\, , Case 1 in PRB deletion.&#62;,568}
} else
{ enum prb_color t; struct prb_node *r = p-&#62;prb_link[1]; if (r-&#62;prb_link[0] == NULL) {
&#60;@xref{\NODE\, , Case 2 in PRB deletion.&#62;,569}
} else
{
&#60;@xref{\NODE\, , Case 3 in PRB deletion.&#62;,570}
} }
This code is included in @refalso{566

Case 1: p has no right child

If p has no right child, then rebalancing should start at its parent, q, and dir is already the side that p is on. The rest is the same as PBST deletion (@pageref{pbstdel1}).

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

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

In case 2, we swap the colors of p and r as for ordinary RB deletion (@pageref{rbcolorswap}). We set up f and dir in the same way that &#60;@xref{\NODE\, , Case 2 in RB deletion.&#62;,223} set up the top of stack. The rest is the same as PBST deletion (@pageref{pbstdel2}).

 
&#60;@xref{\NODE\, , Case 2 in PBST deletion; pbst =>.&#62; prb,498}
t = p-&#62;prb_color;
p-&#62;prb_color = r-&#62;prb_color;
r-&#62;prb_color = t;
f = r;
dir = 1;
This code is included in @refalso{567

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

Case 2 swaps the colors of p and s the same way as in ordinary RB deletion (@pageref{rbcolorswap}), and sets up f and dir in the same way that &#60;@xref{\NODE\, , Case 3 in RB deletion.&#62;,224} set up the stack. The rest is borrowed from PBST deletion (@pageref{pbstdel3}).

 
&#60;@xref{\NODE\, , Case 3 in PBST deletion; pbst =>.&#62; prb,499}
t = p-&#62;prb_color;
p-&#62;prb_color = s-&#62;prb_color;
s-&#62;prb_color = t;
f = r;
dir = 0;
This code is included in @refalso{567


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

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