5.5.6 Symmetric Case [ToC] [Index]     [Skip Back]     [Prev] [Up] [Next]

Here's the code for the symmetric case, where the deleted node was in the right subtree of its parent.

177. <Update y's balance factor after right-side AVL deletion 177> =
y->avl_balance–;
if (y->avl_balance == -1)
  break;
else if (y->avl_balance == -2) 
  { struct avl_node *x = y->avl_link[0]; if (x->avl_balance == +1)
      { struct avl_node *w; <Rotate left at x then right at y in AVL tree 156> pa[k - 1]->avl_link[da[k - 1]] = w; }
    else
      { y->avl_link[0] = x->avl_link[1]; x->avl_link[1] = y; pa[k - 1]->avl_link[da[k - 1]] = x; if (x->avl_balance == 0)
          { x->avl_balance = +1; y->avl_balance = -1; break; } else
          x->avl_balance = y->avl_balance = 0; } }

This code is included in 171.