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


GNU libavl 2.0.1

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

12.5.4 Step 4: Rebalance

Rebalancing in an RTAVL tree after deletion is not completely symmetric between left-side and right-side rebalancing, but there are pairs of similar subcases on each side. The outlines are similar, too. Either way, rebalancing occurs at node y, and cases are distinguished based on the balance factor of x, the child of y on the side opposite the deletion.

 
struct rtavl_node *x = y-&#62;rtavl_link[1];
assert (x != NULL);
if (x-&#62;rtavl_balance == -1) 
{ &#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor after left-side RTAVL deletion,441} }
else
{ pa[k - 1]-&#62;rtavl_link[da[k - 1]] = x; if (x-&#62;rtavl_balance == 0)
{ &#60;@xref{\NODE\, , Rebalance for 0 balance factor after left-side RTAVL deletion.&#62;,443} break; } else /* x-&#62;rtavl_balance == +1 */
{ &#60;@xref{\NODE\, , Rebalance for +.&#62; balance factor after left-side RTAVL deletion,445} } }
This code is included in @refalso{438

 
struct rtavl_node *x = y-&#62;rtavl_link[0];
assert (x != NULL);
if (x-&#62;rtavl_balance == +1) 
{ &#60;@xref{\NODE\, , Rebalance for +.&#62; balance factor after right-side RTAVL deletion,442} }
else
{ pa[k - 1]-&#62;rtavl_link[da[k - 1]] = x; if (x-&#62;rtavl_balance == 0)
{ &#60;@xref{\NODE\, , Rebalance for 0 balance factor after right-side RTAVL deletion.&#62;,444} break; } else /* x-&#62;rtavl_balance == -1 */
{ &#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor after right-side RTAVL deletion,446} } }
This code is included in @refalso{438

Case 1: x has taller subtree on same side as deletion

If the taller subtree of x is on the same side as the deletion, then we rotate at x in the opposite direction from the deletion, then at y in the same direction as the deletion. This is the same as case 2 for RTAVL insertion (@pageref{rtavlinscase2}), which in turn performs the general transformation described for AVL deletion case 1 (@pageref{avldelcase1}), and we can reuse the code.

 
struct rtavl_node *w;
&#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor in RTAVL insertion in right subtree,428}
pa[k - 1]-&#62;rtavl_link[da[k - 1]] = w;
This code is included in @refalso{439

 
struct rtavl_node *w;
&#60;@xref{\NODE\, , Rebalance for +.&#62; balance factor in RTAVL insertion in left subtree,427}
pa[k - 1]-&#62;rtavl_link[da[k - 1]] = w;
This code is included in @refalso{440

Case 2: x's subtrees are equal height

If x's two subtrees are of equal height, then we perform a rotation at y toward the deletion. This rotation cannot be troublesome, for the same reason discussed for rebalancing in TAVL trees (@pageref{tavldelcase2}). We can even reuse the code:

 
&#60;@xref{\NODE\, , Rebalance for 0 balance factor after TAVL deletion in left subtree; tavl =>.&#62; rtavl,321}
This code is included in @refalso{439

 
&#60;@xref{\NODE\, , Rebalance for 0 balance factor after TAVL deletion in right subtree; tavl =>.&#62; rtavl,325}
This code is included in @refalso{440

Case 3: x has taller subtree on side opposite deletion

When x's taller subtree is on the side opposite the deletion, we rotate at y toward the deletion, same as case 2. If the deletion was on the left side of y, then the general form is the same as for TAVL deletion (@pageref{tavldelcase3}). The special case for left-side deletion, where x lacks a left child, and the general form of the code, are shown here:

rtavldel1

 
if (x-&#62;rtavl_link[0] != NULL)
  y-&#62;rtavl_link[1] = x-&#62;rtavl_link[0];
else 
y-&#62;rtavl_rtag = RTAVL_THREAD; x-&#62;rtavl_link[0] = y; y-&#62;rtavl_balance = x-&#62;rtavl_balance = 0;
This code is included in @refalso{439

The special case for right-side deletion, where x lacks a right child, and the general form of the code, are shown here:

rtavldel2

 
if (x-&#62;rtavl_rtag == RTAVL_CHILD)
  y-&#62;rtavl_link[0] = x-&#62;rtavl_link[1];
else 
{ y-&#62;rtavl_link[0] = NULL; x-&#62;rtavl_rtag = RTAVL_CHILD; } x-&#62;rtavl_link[1] = y; y-&#62;rtavl_balance = x-&#62;rtavl_balance = 0;
This code is included in @refalso{440

Exercises:

1. In the chapter about TAVL deletion, we offered two implementations of deletion: one using a stack (&#60;@xref{\NODE\, , \TITLE\}.&#62;{TAVL item deletion function, with stack,659}) and one using an algorithm to find node parents (&#60;@xref{\NODE\, , \TITLE\}.&#62;{TAVL item deletion function,311}). For RTAVL deletion, we offer only a stack-based implementation. Why? [answer]

2. The introduction to this section states that left-looking deletion is more efficient than right-looking deletion in an RTAVL tree. Confirm this by writing a right-looking alternate implementation of &#60;@xref{\NODE\, , \TITLE\}.&#62;{Step 2: Delete RTAVL node,431} and comparing the two sets of code. [answer]

3. Rewrite &#60;@xref{\NODE\, , Case 4 in RTAVL deletion.&#62;,435} to replace the deleted node's rtavl_data by its successor, then delete the successor, instead of shuffling pointers. (Refer back to Exercise 4.8-3 for an explanation of why this approach cannot be used in libavl.) [answer]


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

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