8.5.5 Symmetric Case

Here's the code for the symmetric case.

325. <Steps 3 and 4: Symmetric case in TAVL deletion 325> =
dir = q->tavl_link[0] != y;
y->tavl_balance--;
if (y->tavl_balance == -1) 
  break;
else if (y->tavl_balance == -2) 
  {
    struct tavl_node *x = y->tavl_link[0];
    assert (x != NULL);
    if (x->tavl_balance == +1) 
      {
        <Rebalance for + balance factor after TAVL deletion in right subtree 326>
      } 
    else 
      {
        q->tavl_link[dir] = x;

        if (x->tavl_balance == 0) 
          {
            <Rebalance for 0 balance factor after TAVL deletion in right subtree 327>
            break;
          } 
        else /* x->tavl_balance == -1 */ 
          {
            <Rebalance for - balance factor after TAVL deletion in right subtree 328>
          }
      }
  }

This code is included in 320.

326. <Rebalance for + balance factor after TAVL deletion in right subtree 326> =
struct tavl_node *w;

<Rebalance for + balance factor in TAVL insertion in left subtree 309>
q->tavl_link[dir] = w;

This code is included in 325.

327. <Rebalance for 0 balance factor after TAVL deletion in right subtree 327> =
y->tavl_link[0] = x->tavl_link[1];
x->tavl_link[1] = y;
x->tavl_balance = +1;
y->tavl_balance = -1;

This code is included in 325 and 446.

328. <Rebalance for - balance factor after TAVL deletion in right subtree 328> =
if (x->tavl_tag[1] == TAVL_CHILD)
  y->tavl_link[0] = x->tavl_link[1];
else 
  {
    y->tavl_tag[0] = TAVL_THREAD;
    x->tavl_tag[1] = TAVL_CHILD;
  }
x->tavl_link[1] = y;  
y->tavl_balance = x->tavl_balance = 0;

This code is included in 325.