title: Red Black Tree Insertion And Fixing From Pseudocode Having Issues
body: <p>I have pseudo code from the book "Introduction to Algorithms" by Thomas H Cormen and other for red and black trees.</p>
  
  <p>The pseudo code for insertion and insert fix are located <a href="http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap14.htm" rel="nofollow">here</a></p>
  
  <p>I am getting a seg fault at this line: <code>while(n-&gt;parent-&gt;color == 'r')</code> within the insert fix function utilizing the below test data when trying to insert "8":</p>
  
  <p>Test Data:</p>
  
  <pre><code>i 5
  i 7
  i 1
  i 8
  i 3
  </code></pre>
  
  <p>I believe this is due to the fact the parent of n may not exist? But I am unsure how to change the code appropriately without screwing up the pseudo code completely.:</p>
  
  <p>Here is my insert:</p>
  
  <pre><code>void insert_fix(node * n)
  {
      node * y;
      if(n-&gt;parent)
      {
          while(n-&gt;parent-&gt;color == 'r')
          {
              if(n-&gt;parent == n-&gt;parent-&gt;parent-&gt;left)
              {
                  y = n-&gt;parent-&gt;parent-&gt;right;
                  if(y-&gt;color == 'r')
                  {
                      n-&gt;parent-&gt;color = 'b';
                      y-&gt;color = 'b';
                      n-&gt;parent-&gt;parent-&gt;color = 'r';
                      n = n-&gt;parent-&gt;parent;
                  }
                  else
                  {
                      if(n == n-&gt;parent-&gt;right)
                      {
                          n = n-&gt;parent;
                          rotate_left(n);
                      }
                      n-&gt;parent-&gt;color = 'b';
                      n-&gt;parent-&gt;parent-&gt;color = 'r';
                  }
              }
              else
              {
                  y = n-&gt;parent-&gt;parent-&gt;left;
                  if(y-&gt;color == 'r')
                  {
                      n-&gt;parent-&gt;color = 'b';
                      y-&gt;color = 'b';
                      n-&gt;parent-&gt;parent-&gt;color = 'r';
                      n = n-&gt;parent-&gt;parent;
                  }
                  else
                  {
                      if(n == n-&gt;parent-&gt;left)
                      {
                          n = n-&gt;parent;
                          rotate_right(n);
                      }
                      n-&gt;parent-&gt;color = 'b';
                      n-&gt;parent-&gt;parent-&gt;color = 'r';
                  }
              }
          }
      }
      root-&gt;color = 'b';
  }
  </code></pre>
  
  <p>Here is my insert fix:</p>
  
  <pre><code>void insert_fix(node * n)
  {
      node * y;
      if(n-&gt;parent)
      {
          while(n-&gt;parent-&gt;color == 'r')
          {
              if(n-&gt;parent == n-&gt;parent-&gt;parent-&gt;left)
              {
                  y = n-&gt;parent-&gt;parent-&gt;right;
                  if(y-&gt;color == 'r')
                  {
                      n-&gt;parent-&gt;color = 'b';
                      y-&gt;color = 'b';
                      n-&gt;parent-&gt;parent-&gt;color = 'r';
                      n = n-&gt;parent-&gt;parent;
                  }
                  else
                  {
                      if(n == n-&gt;parent-&gt;right)
                      {
                          n = n-&gt;parent;
                          rotate_left(n);
                      }
                      n-&gt;parent-&gt;color = 'b';
                      n-&gt;parent-&gt;parent-&gt;color = 'r';
                  }
              }
              else
              {
                  y = n-&gt;parent-&gt;parent-&gt;left;
                  if(y-&gt;color == 'r')
                  {
                      n-&gt;parent-&gt;color = 'b';
                      y-&gt;color = 'b';
                      n-&gt;parent-&gt;parent-&gt;color = 'r';
                      n = n-&gt;parent-&gt;parent;
                  }
                  else
                  {
                      if(n == n-&gt;parent-&gt;left)
                      {
                          n = n-&gt;parent;
                          rotate_right(n);
                      }
                      n-&gt;parent-&gt;color = 'b';
                      n-&gt;parent-&gt;parent-&gt;color = 'r';
                  }
              }
          }
      }
      root-&gt;color = 'b';
  }
  </code></pre>
  
  <p>*To be clear, I added the extra if statement around the above while loop so that nothing would happen if the node was the root, however it did not solve my problem as I had hoped.</p>
  
  <p>For good measure I wrote the rotate right and left functions somewhat differently based off of information I found on the internet and I think they're pretty well written:</p>
  
  <pre><code>void rotate_right(node *n)
  {
      node* left = n-&gt;left;
      swap_nodes(n, left);
      n-&gt;left = left-&gt;right;
      if(left-&gt;right != NULL)
          left-&gt;right-&gt;parent = n;
      left-&gt;right = n;
      n-&gt;parent = left;
  }
  
  void rotate_left(node *n)
  {
      node* right = n-&gt;right;
      swap_nodes(n, right);
      n-&gt;right = right-&gt;left;
      if(right-&gt;left != NULL)
          right-&gt;left-&gt;parent = n;
      right-&gt;left = n;
      n-&gt;parent = right;
  }
  
  void swap_nodes(node* oldNode, node* newNode)
  {
      if(oldNode-&gt;parent == NULL)
          root = newNode;
      else
      {
          if(oldNode == oldNode-&gt;parent-&gt;left)
              oldNode-&gt;parent-&gt;left = newNode;
          else
              oldNode-&gt;parent-&gt;right = newNode;
      }
  
      if(newNode != NULL)
          newNode-&gt;parent = oldNode-&gt;parent;
  }
  </code></pre>
  
  <p>Again, I feel my real code follows the pseudo code accurately but I cannot figure out the part I'm missing.</p>
  
  <p>Let me know! Thanks!</p>