www.delorie.com/gnu/docs/avl/libavl_98.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.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:

 
struct avl_node *x = y-&#62;avl_link[1];
if (x-&#62;avl_balance == +1)
  { 
&#60;@xref{\NODE\, , Rotate left at y.&#62; in AVL tree,158}
} else
{
&#60;@xref{\NODE\, , Rotate right at x.&#62; then left at y in AVL tree,159}
}
This code is included in @refalso{151

 
w = x;
y-&#62;avl_link[1] = x-&#62;avl_link[0];
x-&#62;avl_link[0] = y;
x-&#62;avl_balance = y-&#62;avl_balance = 0;
This code is included in @refalso{157

 
assert (x-&#62;avl_balance == -1);
w = x-&#62;avl_link[0];
x-&#62;avl_link[0] = w-&#62;avl_link[1];
w-&#62;avl_link[1] = x;
y-&#62;avl_link[1] = w-&#62;avl_link[0];
w-&#62;avl_link[0] = y;
if (w-&#62;avl_balance == +1) 
x-&#62;avl_balance = 0, y-&#62;avl_balance = -1; else if (w-&#62;avl_balance == 0)
x-&#62;avl_balance = y-&#62;avl_balance = 0; else /* w-&#62;avl_balance == -1 */
x-&#62;avl_balance = +1, y-&#62;avl_balance = 0; w-&#62;avl_balance = 0;
This code is included in @refalso{157


  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003