8.5.5 Symmetric Case [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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.