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


GNU libavl 2.0.1

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

9.4.2 Step 4: Rebalance

Now we're finally to the interesting part, the rebalancing step. We can tell whether rebalancing is necessary based on the balance factor of y, the same as in unthreaded AVL insertion:

 
if (y-&#62;tavl_balance == -2)
  { 
&#60;@xref{\NODE\, , Rebalance TAVL tree after insertion in left subtree.&#62;,305}
} else if (y-&#62;tavl_balance == +2) {
&#60;@xref{\NODE\, , Rebalance TAVL tree after insertion in right subtree.&#62;,308}
} else
return &n-&#62;tavl_data; z-&#62;tavl_link[y != z-&#62;tavl_link[0]] = w; return &n-&#62;tavl_data;
This code is included in @refalso{301

We will examine the case of insertion in the left subtree of y, the node at which we must rebalance. We take x as y's child on the side of the new node, then, as for unthreaded AVL insertion, we distinguish two cases based on the balance factor of x:

 
struct tavl_node *x = y-&#62;tavl_link[0];
if (x-&#62;tavl_balance == -1)
  { 
&#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor in TAVL insertion in left subtree,306}
} else
{
&#60;@xref{\NODE\, , Rebalance for +.&#62; balance factor in TAVL insertion in left subtree,307}
}
This code is included in @refalso{304

Case 1: x has - balance factor

As for unthreaded insertion, we rotate right at y (see section 6.4.4 Step 4: Rebalance). Notice the resemblance of the following code to rotate_right() in the solution to Exercise 8.2-1.

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

Case 2: x has + balance factor

When x has a + balance factor, we perform the transformation shown below, which consists of a left rotation at x followed by a right rotation at y. This is the same transformation used in unthreaded insertion:

tavlins1

We could simply apply the standard code from Exercise 8.2-1 in each rotation (see Exercise 1), but it is just as straightforward to do both of the rotations together, then clean up any threads. Subtrees a and d cannot cause thread-related trouble, because they are not disturbed during the transformation: a remains x's left child and d remains y's right child. The children of w, subtrees b and c, do require handling. If subtree b is a thread, then after the rotation and before fix-up x's right link points to itself, and, similarly, if c is a thread then y's left link points to itself. These links must be changed into threads to w instead, and w's links must be tagged as child pointers.

If both b and c are threads then the transformation looks like the diagram below, showing pre-rebalancing and post-rebalancing, post-fix-up views. The AVL balance rule implies that if b and c are threads then a and d are also:

tavlins2

The required code is heavily based on the corresponding code for unthreaded AVL rebalancing:

 
&#60;@xref{\NODE\, , Rotate left at x.&#62; then right at y in AVL tree; avl => tavl,156}
if (w-&#62;tavl_tag[0] == TAVL_THREAD) 
{ x-&#62;tavl_tag[1] = TAVL_THREAD; x-&#62;tavl_link[1] = w; w-&#62;tavl_tag[0] = TAVL_CHILD; } if (w-&#62;tavl_tag[1] == TAVL_THREAD)
{ y-&#62;tavl_tag[0] = TAVL_THREAD; y-&#62;tavl_link[0] = w; w-&#62;tavl_tag[1] = TAVL_CHILD; }
This code is included in @refalso{305

Exercises:

1. Rewrite &#60;@ref{\NODE\, , Rebalance for +.&#62; balance factor in TAVL insertion in left subtree,307} in terms of the routines from Exercise 8.2-1. [answer]


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

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