8.5.3 Step 3: Update Balance Factors

Rebalancing begins from node q, from whose side dir a node was deleted. Node q at the beginning of the iteration becomes node y, the root of the balance factor update and rebalancing, and dir at the beginning of the iteration is used to separate the left-side and right-side deletion cases.

The loop also updates the values of q and dir for rebalancing and for use in the next iteration of the loop, if any. These new values can only be assigned after the old ones are no longer needed, but must be assigned before any rebalancing so that the parent link to y can be changed. For q this is after y receives q's old value and before rebalancing. For dir, it is after the branch point that separates the left-side and right-side deletion cases, so the dir assignment is duplicated in each branch. The code used to update q is discussed later.

320. <Steps 3 and 4: Update balance factors and rebalance after TAVL deletion 320> =
while (q != (struct tavl_node *) &tree->tavl_root) 
  {
    struct tavl_node *y = q;

    q = find_parent (tree, y);

    if (dir == 0) 
      {
        dir = q->tavl_link[0] != y;
        y->tavl_balance++;
        if (y->tavl_balance == +1)
          break;
        else if (y->tavl_balance == +2)
          { 
            <Step 4: Rebalance after TAVL deletion 321> 
          }
      }
    else 
      { 
        <Steps 3 and 4: Symmetric case in TAVL deletion 325> 
      }
  }

tree->tavl_count--;
return (void *) item;

This code is included in 313.