14.4.2 Step 3: Update Balance Factors

Until now, in step 3 of insertion into AVL trees we've always updated balance factors from the top down, starting at y and working our way down to n (see, e.g., <Step 3: Update balance factors after AVL insertion 150>). This approach was somewhat unnatural, but it worked. The original reason we did it this way was that it was either impossible, as for AVL and RTAVL trees, or slow, as for TAVL trees, to efficiently move upward in a tree. That's not a consideration anymore, so we can do it from the bottom up and in the process eliminate the cache used before.

At each step, we need to know the node to update and, for that node, on which side of its parent it is a child. In the code below, q is the node and dir is the side.

526. <Step 3: Update balance factors after PAVL insertion 526> =
for (p = n; p != y; p = q) 
  {
    q = p->pavl_parent;
    dir = q->pavl_link[0] != p;
    if (dir == 0)
      q->pavl_balance–;
    else 
      q->pavl_balance++;
  }

This code is included in 523.

Exercises:

1. Does this step 3 update the same set of balance factors as would a literal adaptation of <Step 3: Update balance factors after AVL insertion 150>? [answer]

2. Would it be acceptable to substitute q->pavl_link[1] == p for q->pavl_link[0] != p in the code segment above? [answer]