AVL **ptr corruption after rotation

[wulfsdad]

I'm writing an AVL tree package, and keep running into an infinite loop where the root node's parent pointer points to itself.

I'm running it with the simplest case where ->(1)->(2)->(3) should left-rotate to have root of two and structure of: (1)<-(2)->(3). I've commented out the more complex cases for now till I get it working.

Everything looks good until I return from the rotate function, then the root's parent changes. The code is as follows, along with some gdb output showing the change.

TREE_NODE* rotate( TREE_NODE* grandparent, unsigned left )
{
   unsigned right = opposite(left);//Sometimes left is right and vice versa
   
   if( grandparent ){ //should be redundant check
      
      TREE_NODE* yparent = (grandparent->child[right]);
      
      if( yparent ){ //should be redundant check
         TREE_NODE* t1 = (yparent->child[left]);
      /* Update Height */
         grandparent->contents.height -= 2;   
      /* Attach Grandparent As Parent's Child */
         yparent->child[left] = grandparent;
      /* Attach Replaced Child to what was Grandparent */
         grandparent->child[right] = t1;
      /* Update Parents */
         if(t1) t1->parent = grandparent;
         yparent->parent = grandparent->parent;
         grandparent->parent = yparent;
         
      /* Return caller's new Child */ 
         return yparent;
      }/* End Parent Exits If*/
	}/* End grandparent !NULL If */
   return grandparent; //prevent memory leak
}/* End rotate Func */

Is called by:

void balance_tree(TREE_NODE** ptr)
{
    if( *ptr ){
       int bf = balance_factor(*ptr);
       if(  bf < RIGHT_HEAVY  ){
//          if( heavy((*ptr)->child[RIGHT]) == LEFT ){
//             (*ptr)->child[RIGHT] = *(rotate(&((*ptr)->child[RIGHT]), RIGHT));
//             (*ptr)->child[RIGHT]->parent = (*ptr);
//          }/* End Complex Case If */
          *ptr = //Without this (*ptr) becomes NULL
           (rotate((*ptr), LEFT)); //With it (*ptr)->parent becomes (*ptr) !!!
       }else if( bf > LEFT_HEAVY ){
//             if( heavy((*ptr)->child[RIGHT]) == RIGHT ){
//             (*ptr)->child[LEFT] = *(rotate(&((*ptr)->child[LEFT]), LEFT));
//             (*ptr)->child[LEFT]->parent = (*ptr);
//          }/* End Complex Case If */
//          *ptr = *(rotate(&(*ptr), RIGHT));
// //         (*ptr)->child[LEFT]->parent = (*ptr);
       }//else is ballanced
        balance_tree( &((*ptr)->parent) );
    }/* End *ptr !NULL If */  
    else cout << "done";
}/* End balance_tree Func */

Is called by:

bool insertion(KEY key_val, TREE_NODE** ptr)
{
   TREE_NODE** temp = insert(key_val, ptr); //inserts as leaf and returns it
   if(!(*temp)) return false;
   else update_height(*temp);
	
   balance_tree(temp);

   return true;
}/* End Func */

Please enter your request (i=insert, d=delete, p=print, e=exit): i 1 i 2 i 3
(NULL,1,NULL)
(NULL,1,(NULL,2,NULL))

Breakpoint 1, rotate (grandparent=0x605010, left=0) at AVL_Tree.cpp:121
(gdb) n #skipping along to end of the function
145 return yparent;
(gdb) print yparent
$1 = (TREE_NODE *) 0x605040
(gdb) print *yparent
$2 = {contents = {keyval = 2, height = 2}, child = {0x605010, 0x605070}, parent = 0x0}
(gdb) n #returning to calling frame
balance_tree (ptr=0x605058) at AVL_Tree.cpp:242
242 balance_tree( &((*ptr)->parent) );
(gdb) print *ptr
$3 = (TREE_NODE *) 0x605040
(gdb) print **ptr
$4 = {contents = {keyval = 2, height = 2}, child = {0x605010, 0x605070}, parent = 0x605040}

When I comment out the line in balance_tree shown here as 10, and add an if(*ptr) before the recursive call then everything seems to be working out except that my pointer to the root still points at the now left child.

[wulfsdad]

I added a TREE_NODE* return value for balance_tree to be assigned to *ptr in insertion, and had it return a "next" variable which accepted the return value of rotate. Now the simple case works. Hopefully, the complex cases wont give me any problems, and then I can fold balance tree into 2 nested ifs. I wouldn't have found the solution If I hadn't made this post trying to explain the problem. So, thanks for being here.