8.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:

304. <Step 4: Rebalance after TAVL insertion 304> =
if (y->tavl_balance == -2)
  { 
    <Rebalance TAVL tree after insertion in left subtree 305> 
  }
else if (y->tavl_balance == +2)
  { 
    <Rebalance TAVL tree after insertion in right subtree 308> 
  }
else 
  return &n->tavl_data;
z->tavl_link[y != z->tavl_link[0]] = w;

return &n->tavl_data;

This code is included in 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:

305. <Rebalance TAVL tree after insertion in left subtree 305> =
struct tavl_node *x = y->tavl_link[0];
if (x->tavl_balance == -1)
  { 
    <Rebalance for - balance factor in TAVL insertion in left subtree 306> 
  } 
else 
  { 
    <Rebalance for + balance factor in TAVL insertion in left subtree 307> 
  }

This code is included in 304.

Case 1: x has - balance factor

As for unthreaded insertion, we rotate right at y (see Rebalancing AVL Trees). Notice the resemblance of the following code to rotate_right() in the solution to Exercise 8.2-1.

306. <Rebalance for - balance factor in TAVL insertion in left subtree 306> =
w = x;
if (x->tavl_tag[1] == TAVL_THREAD) 
  {
    x->tavl_tag[1] = TAVL_CHILD;
    y->tavl_tag[0] = TAVL_THREAD;
    y->tavl_link[0] = x;
  }
else 
  y->tavl_link[0] = x->tavl_link[1];
x->tavl_link[1] = y;
x->tavl_balance = y->tavl_balance = 0;

This code is included in 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:

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:

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

307. <Rebalance for + balance factor in TAVL insertion in left subtree 307> =
<Rotate left at x then right at y in AVL tree; avl => tavl 156>
if (w->tavl_tag[0] == TAVL_THREAD) 
  {
    x->tavl_tag[1] = TAVL_THREAD;
    x->tavl_link[1] = w;
    w->tavl_tag[0] = TAVL_CHILD;
  }
if (w->tavl_tag[1] == TAVL_THREAD) 
  {
    y->tavl_tag[0] = TAVL_THREAD;
    y->tavl_link[0] = w;
    w->tavl_tag[1] = TAVL_CHILD;
  }

This code is included in 305, 324, and 667.

Exercises:

1. Rewrite <Rebalance for + balance factor in TAVL insertion in left subtree 307> in terms of the routines from Exercise 8.2-1. [answer]