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


GNU libavl 2.0.1

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

15.5.3 Step 4: Rebalance

The two cases for PAVL deletion are distinguished based on x's balance factor, as always:

 
struct pavl_node *x = y-&#62;pavl_link[1];
if (x-&#62;pavl_balance == -1)
  { 
&#60;@xref{\NODE\, , Left-side rebalancing case 1 in PAVL deletion.&#62;,541}
} else
{
&#60;@xref{\NODE\, , Left-side rebalancing case 2 in PAVL deletion.&#62;,542}
}
This code is included in @refalso{539

Case 1: x has - balance factor

The same rebalancing is needed here as for a - balance factor in PAVL insertion, and the same code is used.

 
struct pavl_node *w;
&#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor in PAVL insertion in right subtree,533}
q-&#62;pavl_link[dir] = w;
This code is included in @refalso{540

Case 2: x has + or 0 balance factor

If x has a + or 0 balance factor, we rotate left at y and update parent pointers as for any left rotation (see section 15.2 Rotations). We also update balance factors. If x started with balance factor 0, then we're done. Otherwise, x becomes the new y for the next loop iteration, and rebalancing continues. See avldel2, for details on this rebalancing case.

 
y-&#62;pavl_link[1] = x-&#62;pavl_link[0];
x-&#62;pavl_link[0] = y;
x-&#62;pavl_parent = y-&#62;pavl_parent;
y-&#62;pavl_parent = x;
if (y-&#62;pavl_link[1] != NULL)
  y-&#62;pavl_link[1]-&#62;pavl_parent = y;
q-&#62;pavl_link[dir] = x;
if (x-&#62;pavl_balance == 0) 
{ x-&#62;pavl_balance = -1; y-&#62;pavl_balance = +1; break; }
else
{ x-&#62;pavl_balance = y-&#62;pavl_balance = 0; y = x; }
This code is included in @refalso{540


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