5.4.5 Symmetric Case

Finally, we need to write code for the case that we chose not to discuss earlier, where the insertion occurs in the right subtree of y. All we have to do is invert the signs of balance factors and switch avl_link[] indexes between 0 and 1. The results are this:

159. <Rebalance AVL tree after insertion in right subtree 159> =
struct avl_node *x = y->avl_link[1];
if (x->avl_balance == +1)
  { 
    <Rotate left at y in AVL tree 160> 
  }
else 
  { 
    <Rotate right at x then left at y in AVL tree 161> 
  }

This code is included in 153 and 164.

160. <Rotate left at y in AVL tree 160> =
w = x;
y->avl_link[1] = x->avl_link[0];
x->avl_link[0] = y;
x->avl_balance = y->avl_balance = 0;

This code is included in 159 and 534.

161. <Rotate right at x then left at y in AVL tree 161> =
assert (x->avl_balance == -1);
w = x->avl_link[0];
x->avl_link[0] = w->avl_link[1];
w->avl_link[1] = x;
y->avl_link[1] = w->avl_link[0];
w->avl_link[0] = y;
if (w->avl_balance == +1) 
  x->avl_balance = 0, y->avl_balance = -1;
else if (w->avl_balance == 0) 
  x->avl_balance = y->avl_balance = 0;
else /* w->avl_balance == -1 */ 
  x->avl_balance = +1, y->avl_balance = 0;
w->avl_balance = 0;

This code is included in 159, 176, 312, 430, and 535.