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


GNU libavl 2.0.1

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

12.4.2 Step 4: Rebalance

Unlike all of the AVL rebalancing algorithms we've seen so far, rebalancing of a right-threaded AVL tree is not symmetric. This means that we cannot single out left-side rebalancing or right-side rebalancing as we did before, hand-waving the rest of it as a symmetric case. But both cases are very similar, if not exactly symmetric, so we will present the corresponding cases together. The theory is exactly the same as before (see section 6.4.4 Step 4: Rebalance). Here is the code to choose between left-side and right-side rebalancing:

 
if (y-&#62;rtavl_balance == -2)
  { 
&#60;@xref{\NODE\, , Step 4: Rebalance RTAVL tree after insertion to left.&#62;,423}
} else if (y-&#62;rtavl_balance == +2) {
&#60;@xref{\NODE\, , Step 4: Rebalance RTAVL tree after insertion to right.&#62;,424}
} else
return &n-&#62;rtavl_data; z-&#62;rtavl_link[y != z-&#62;rtavl_link[0]] = w; return &n-&#62;rtavl_data;
This code is included in @refalso{419

The code to choose between the two subcases within the left-side and right-side rebalancing cases follows below. As usual during rebalancing, y is the node at which rebalancing occurs, x is its child on the same side as the inserted node, and cases are distinguished on the basis of x's balance factor:

 
struct rtavl_node *x = y-&#62;rtavl_link[0];
if (x-&#62;rtavl_balance == -1)
  { 
&#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor in RTAVL insertion in left subtree,425}
} else
{
&#60;@xref{\NODE\, , Rebalance for +.&#62; balance factor in RTAVL insertion in left subtree,427}
}
This code is included in @refalso{422

 
struct rtavl_node *x = y-&#62;rtavl_link[1];
if (x-&#62;rtavl_balance == +1)
  { 
&#60;@xref{\NODE\, , Rebalance for +.&#62; balance factor in RTAVL insertion in right subtree,426}
} else
{
&#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor in RTAVL insertion in right subtree,428}
}
This code is included in @refalso{422

Case 1: x has taller subtree on side of insertion

If node x's taller subtree is on the same side as the inserted node, then we perform a rotation at y in the opposite direction. That is, if the insertion occurred in the left subtree of y and x has a - balance factor, we rotate right at y, and if the insertion was to the right and x has a + balance factor, we rotate left at y. This changes the balance of both x and y to zero. None of this is a change from unthreaded or fully threaded rebalancing. The difference is in the handling of empty subtrees, that is, in the rotation itself (see section 12.3 Rotations).

Here is a diagram of left-side rebalancing for the interesting case where x has a right thread. Taken along with x's - balance factor, this means that n, the newly inserted node, must be x's left child. Therefore, subtree x has height 2, so y has no right child (because it has a -2 balance factor). This chain of logic means that we know exactly what the tree looks like in this particular subcase:

rtavlins1

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

Here is the diagram and code for the similar right-side case:

rtavlins2

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

Case 2: x has taller subtree on side opposite insertion

If node x's taller subtree is on the side opposite the newly inserted node, then we perform a double rotation: first rotate at x in the same direction as the inserted node, then in the opposite direction at y. This is the same as in a threaded or unthreaded tree, and indeed we can reuse much of the code.

The case where the details differ is, as usual, where threads or null child pointers are moved around. In the most extreme case for insertion to the left, where w is a leaf, we know that x has no left child and s no right child, and the situation looks like the diagram below before and after the rebalancing step:

rtavlins3

 
&#60;@xref{\NODE\, , Rotate left at x.&#62; then right at y in AVL tree; avl => rtavl,156}
if (x-&#62;rtavl_link[1] == NULL) 
{ x-&#62;rtavl_rtag = RTAVL_THREAD; x-&#62;rtavl_link[1] = w; } if (w-&#62;rtavl_rtag == RTAVL_THREAD)
{ y-&#62;rtavl_link[0] = NULL; w-&#62;rtavl_rtag = RTAVL_CHILD; }
This code is included in @refalso{423

Here is the code and diagram for right-side insertion rebalancing:

rtavlins4

 
&#60;@xref{\NODE\, , Rotate right at x.&#62; then left at y in AVL tree; avl => rtavl,159}
if (y-&#62;rtavl_link[1] == NULL) 
{ y-&#62;rtavl_rtag = RTAVL_THREAD; y-&#62;rtavl_link[1] = w; } if (w-&#62;rtavl_rtag == RTAVL_THREAD)
{ x-&#62;rtavl_link[0] = NULL; w-&#62;rtavl_rtag = RTAVL_CHILD; }
This code is included in @refalso{424


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

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