title: Red-Black Tree Deleting Problem C#
body: <p>I am trying to implement a red-black tree in C#. I already created an object called sRbTreeNode which has a String key, Color, Left, Right and Parent properties.
  I successfully managed implementing the methods Insert, InsertFixUp, LeftRotate, RightRotate, Delete, and now im having trouble with the method DeleteFixUp.</p>
  
  <p>DeleteFixUp is responsible for balancing out the tree again (using rotations and by changing the nodes colors) after a delete.</p>
  
  <p>I tried implementing the method from the pseudo code i found in a book called "Introduction to Algorithms".</p>
  
  <p>Here is my code :</p>
  
  <pre><code>private static void DeleteFixup(ref sRbTreeNode root, sRbTreeNode x)
      {
          sRbTreeNode y;
  
          while (x != root &amp;&amp; x.Color == BLACK)
          {
              if (x == x.Parent.Left)         // determine sub tree from parent
              {
                  y = x.Parent.Right;         // y is x's sibling 
                  if (y.Color == RED)
                  {   // x is black, y is red - make both black and rotate
                      y.Color = BLACK;
                      x.Parent.Color = RED;
                      LeftRotate(ref root, x.Parent);
                      y = x.Parent.Right;
                  }
                  if (y.Left.Color == BLACK &amp;&amp;
                      y.Right.Color == BLACK)
                  {   // children are both black
                      y.Color = RED;      // change parent to red
                      x = x.Parent;                   // move up the tree
                  }
                  else
                  {
                      if (y.Right.Color == BLACK)
                      {
                          y.Left.Color = BLACK;
                          y.Color = RED;
                          RightRotate(ref root, y);
                          y = x.Parent.Right;
                      }
                      y.Color = x.Parent.Color;
                      x.Parent.Color = BLACK;
                      y.Right.Color = BLACK;
                      LeftRotate(ref root, x.Parent);
                      x = root;
                  }
              }
              else
              {   // right subtree - same as code above with right and left swapped
                  y = x.Parent.Left;
                  if (y.Color == RED)
                  {
                      y.Color = BLACK;
                      x.Parent.Color = RED;
                      RightRotate(ref root, x.Parent);
                      y = x.Parent.Left;
                  }
                  if (y.Right.Color == BLACK &amp;&amp;
                      y.Left.Color == BLACK)
                  {
                      y.Color = RED;
                      x = x.Parent;
                  }
                  else
                  {
                      if (y.Left.Color == BLACK)
                      {
                          y.Right.Color = BLACK;
                          y.Color = RED;
                          LeftRotate(ref root, y);
                          y = x.Parent.Left;
                      }
                      y.Color = x.Parent.Color;
                      x.Parent.Color = BLACK;
                      y.Left.Color = BLACK;
                      RightRotate(ref root, x.Parent);
                      x = root;
                  }
              }
          }
  
          x.Color = BLACK;
      }
  </code></pre>
  
  <p>I keep running into the error "Object reference not set to an instance of an object" each time in different places...</p>
  
  <p>I searched the internet for implementations of this, just found one article on CodeProject, which implemented it exactly like i did. I tried copying their code, hoping im missing something with my eye, but it didn't work neither...</p>
  
  <p>Can someone please help me, before i start tearing my hairs out!!... ??
  :)</p>