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


GNU libavl 2.0.1

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

9.5.4 Step 4: Rebalance

Rebalancing after deletion in a TAVL tree divides into three cases. The first of these is analogous to case 1 in unthreaded AVL deletion, the other two to case 2 (see section 8.6 Insertion). The cases are distinguished, as usual, based on the balance factor of right child x of the node y at which rebalancing occurs:

 
struct tavl_node *x = y-&#62;tavl_link[1];
assert (x != NULL);
if (x-&#62;tavl_balance == -1) 
{ &#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor after TAVL deletion in left subtree,320} }
else
{ q-&#62;tavl_link[dir] = x; if (x-&#62;tavl_balance == 0)
{ &#60;@xref{\NODE\, , Rebalance for 0 balance factor after TAVL deletion in left subtree.&#62;,321} break; }
else /* x-&#62;tavl_balance == +1 */
{ &#60;@xref{\NODE\, , Rebalance for +.&#62; balance factor after TAVL deletion in left subtree,322} } }
This code is included in @refalso{318

Case 1: x has - balance factor

This case is just like case 2 in TAVL insertion. In fact, we can even reuse the code:

 
struct tavl_node *w;
&#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor in TAVL insertion in right subtree,310}
q-&#62;tavl_link[dir] = w;
This code is included in @refalso{319

Case 2: x has 0 balance factor

If x has a 0 balance factor, then we perform a left rotation at y. The transformation looks like this, with subtree heights listed under their labels:

tavldel

Subtree b is taller than subtree a, so even if h takes its minimum value of 1, then subtree b has height h == 1 and, therefore, it must contain at least one node and there is no need to do any checking for threads. The code is simple:

 
y-&#62;tavl_link[1] = x-&#62;tavl_link[0];
x-&#62;tavl_link[0] = y;
x-&#62;tavl_balance = -1;
y-&#62;tavl_balance = +1;
This code is included in @refalso{319

Case 3: x has + balance factor

If x has a + balance factor, we perform a left rotation at y, same as for case 2, and the transformation looks like this:

tavldel2

One difference from case 2 is in the resulting balance factors. The other is that if h == 1, then subtrees a and b have height h - 1 == 0, so a and b may actually be threads. In that case, the transformation must be done this way:

tavldel3

This code handles both possibilities:

 
if (x-&#62;tavl_tag[0] == TAVL_CHILD)
  y-&#62;tavl_link[1] = x-&#62;tavl_link[0];
else 
{ y-&#62;tavl_tag[1] = TAVL_THREAD; x-&#62;tavl_tag[0] = TAVL_CHILD; } x-&#62;tavl_link[0] = y; y-&#62;tavl_balance = x-&#62;tavl_balance = 0;
This code is included in @refalso{319


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

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