pointer to pointer problem

Question

I was studying trees and everything seem fine until i started a avl tree, which requires rotation. I built a rotation algorithm that works fine until the 2 or 3 rotation, the algorithm it's the following:

static void _nodeRotateRight(avl_tree* t, avl_tree_node** n) {
avl_tree_node* node = (*n)->left;

// refresh parents before rotate
if (node->right)
    node->right->parent = (*n);

if ((*n) == t->top) {
    t->top = node;
    node->parent = NULL;
}
else {
    (*n)->parent->right = node;
    node->parent = (*n)->parent;
}

(*n)->parent = (*n)->left;

// rotate nodes (pointers)
(*n)->left = node->right;
node->right = (*n);
(*n) = node;

// refresh heights
(*n)->right->height -= 2;

}

the error is on: (*n)->parent->right = node;

actually works, but on the 3º rotation has a strange behaviour, assigning a new value to "right" actually changes (_n) instead of right itself. Obviously that (_n)->parent->right points to (_n), but if i assign a new value to right, i can't change (_n) because they are different pointers with different addresses... Any solution to this problem ?

Answer 1

You should cache the value of of *n.

avl_tree_node *n1 = *n;

Now, regardless of how you change *n, n1 will continue pointing to the original node.