title: C pointer refuses to reassign
body: <p>I am writing an AVL tree in C, with each node keeping record of both its height and balance factor. I’ve encountered on odd bug when performing rotations. My rebalance function climbs the tree until it finds the root node or an unbalanced node, then checks the balance factors to figure out which rotations it needs to perform. The rotation functions take in double pointers and reassign the dereferenced node they were given. However, that didn’t seem to work, so for good measure I also made the functions return the node that took the original node’s place. This doesn’t seem to work either, which I don’t understand. On lines 164 and 171, I’m explicitly assigning the node’s child to the rotation function’s return value (which is what its new node will be.)</p>
  
  <p>My rotation functions:</p>
  
  <pre><code>Node *rotateRight(Node **root) {
      Node *node = *root;
      Node *pivot = node-&gt;left; //pivot will become the new root
      if(node-&gt;parent) {
          Node *g = node-&gt;parent;
          pivot-&gt;parent = node-&gt;parent;
          if(pivot-&gt;datum &lt; g-&gt;datum) g-&gt;left = pivot;
          else g-&gt;right = pivot;
      } else
          pivot-&gt;parent = NULL;
      node-&gt;parent = node-&gt;left;
      node-&gt;left = pivot-&gt;right? pivot-&gt;right : NULL;
      pivot-&gt;right = node;
      *root = node-&gt;parent;
      return pivot;
  }
  
  Node *rotateLeft(Node **root) {
      Node *node = *root;
      Node *pivot = node-&gt;right;
      if(node-&gt;parent) {
          Node *g = node-&gt;parent;
          pivot-&gt;parent = node-&gt;parent;
          if(pivot-&gt;datum &lt; g-&gt;datum) g-&gt;left = pivot;
          else g-&gt;right = pivot;
      } else
          pivot-&gt;parent = NULL;
      node-&gt;parent = pivot;
      node-&gt;right = pivot-&gt;left? pivot-&gt;left : NULL;
      pivot-&gt;left = node;
      *root = node-&gt;parent;
      return pivot;
  }
  </code></pre>
  
  <p>My rebalance function (retrace just finds the root of the tree):</p>
  
  <pre><code>Node *rebalance(Node **node) {
      if(-1 &lt;= (*node)-&gt;bal &amp;&amp; (*node)-&gt;bal &lt;= 1) { //current node is balanced, we can ascend and check the next node
          if((*node)-&gt;parent) rebalance(&amp;((*node)-&gt;parent));
          return retrace(*node);
      }
      if((*node)-&gt;bal == 2) {
          if((*node)-&gt;left-&gt;bal == 1) { //left left
              puts("ll");
              rotateRight(node);
              return retrace(*node);
          } else { //left right
              puts("lr");
              (*node)-&gt;left = rotateLeft(&amp;((*node)-&gt;left));
              rotateRight(node);
              return retrace(*node);
          }
      } else {
          if((*node)-&gt;right-&gt;bal == 1) { //right left
              puts("rl");
              (*node)-&gt;right = rotateRight(&amp;((*node)-&gt;right));
              rotateLeft(node);
              return retrace(*node);
          } else { //right right
              puts("rr");
              rotateLeft(node);
          }
      }
  }
  </code></pre>