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


GNU libavl 2.0.1

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

6.5.4 Step 4: Rebalance

Now we have to write code to rebalance when it becomes necessary. We'll use rotations to do this, as before. Again, we'll distinguish the cases on the basis of x's balance factor, where x is y's right child:

 
struct avl_node *x = y-&#62;avl_link[1];
if (x-&#62;avl_balance == -1)
  { 
&#60;@xref{\NODE\, , Left-side rebalancing case 1 in AVL deletion.&#62;,174}
} else
{
&#60;@xref{\NODE\, , Left-side rebalancing case 2 in AVL deletion.&#62;,175}
}
This code is included in @refalso{172

Case 1: x has - balance factor

If x has a - balance factor, we handle rebalancing in a manner analogous to case 2 for insertion. In fact, we reuse the code. We rotate right at x, then left at y. w is the left child of x. The two rotations look like this:

avldel1

 
struct avl_node *w;
&#60;@xref{\NODE\, , Rotate right at x.&#62; then left at y in AVL tree,159}
pa[k - 1]-&#62;avl_link[da[k - 1]] = w;
This code is included in @refalso{173

Case 2: x has + or 0 balance factor

When x's balance factor is +, the needed treatment is analogous to Case 1 for insertion. We simply rotate left at y and update the pointer to the subtree, then update balance factors. The deletion and rebalancing then look like this:

avldel2

When x's balance factor is 0, we perform the same rotation, but the height of the overall subtree does not change, so we're done and can exit the loop with break. Here's what the deletion and rebalancing look like for this subcase:

avldel3

 
y-&#62;avl_link[1] = x-&#62;avl_link[0];
x-&#62;avl_link[0] = y;
pa[k - 1]-&#62;avl_link[da[k - 1]] = x;
if (x-&#62;avl_balance == 0) 
{ x-&#62;avl_balance = -1; y-&#62;avl_balance = +1; break; } else
x-&#62;avl_balance = y-&#62;avl_balance = 0;
This code is included in @refalso{173

Exercises:

1. In &#60;@xref{\NODE\, , Step 4: Rebalance after AVL deletion.&#62;,173}, we refer to fields in x, the right child of y, without checking that y has a non-null right child. Why can we assume that node x is non-null? [answer]

2. Describe the shape of a tree that might require rebalancing at every level above a particular node. Give an example. [answer]


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

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