title: Is this implementation of a Red Black Tree C# correct?
body: <p>Please critique my code. I noticed my last assert fails with value 277. I expected the value to 255 (1/2 500+10). Is this a valid test or have I done something wrong? </p>
  
  <pre><code>using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  using Microsoft.VisualStudio.TestTools.UnitTesting;
  
  namespace RedBlackTree
  {
      public enum NodeColor
      { 
          Red,
          Black
      }
  
      public enum NodeSide
      { 
          Left,
          Right,
          None
      }
  
  
      public class RedBlackTreeNode&lt;T&gt;
          where T : IComparable&lt;T&gt;
      {
          public RedBlackTreeNode&lt;T&gt; Left { get; set; }
          public RedBlackTreeNode&lt;T&gt; Right { get; set; }
          public RedBlackTreeNode&lt;T&gt; Parent { get; set; }
          public T Data {get; set;}
          public NodeColor Color { get; set; }
          public RedBlackTreeNode&lt;T&gt; Uncle
          {
              get
              {
                  if (WhichSideAmIOn() == NodeSide.Left)
                  {
                      return this.Parent.Right;
                  }
                  else
                      return this.Parent.Left;
              }
          }
  
          public string ToString()
          {
              return String.Format("Me: {0} Left: {1} Right: {2}", Data, Left != null ? Left.Data.ToString() : "null", Right != null ? Right.Data.ToString() : "null");
          }
          public NodeSide WhichSideAmIOn()
          {
              if (this.Parent == null) return NodeSide.None;
              if (this.Parent.Left == this)
                  return NodeSide.Left;
              if (this.Parent.Right == this)
                  return NodeSide.Right;
  
              throw new Exception("Impossible - there can be only two sides. You must not be a child of your parent.");
          }
  
      }
  
      public class RedBlackTree&lt;T&gt;
          where T : IComparable&lt;T&gt;
      {
          private RedBlackTreeNode&lt;T&gt; Root { get; set; }
  
          public void InsertNode(T data)
          { 
              //make a node to hold the data - always red
              RedBlackTreeNode&lt;T&gt; newNode = new RedBlackTreeNode&lt;T&gt;();
              newNode.Data = data;
              newNode.Color = NodeColor.Red;
  
              //rule 1 - if the root is null, then hte new node is the root and roots can't be red.
              if (Root == null)
              {
                  Root = newNode;
                  Root.Color = NodeColor.Black;
                  return;
              }
  
              //otherwise if we're not the first node, insert by walking.
              RedBlackTreeNode&lt;T&gt; walker = Root;
              while (walker != null)
              {
                  if (newNode.Data.CompareTo(walker.Data)&lt; 0) 
                  { 
                      //walk left
                      if (walker.Left == null) 
                      {
                          walker.Left = newNode;
                          newNode.Parent = walker;
                          break;                     
                      }
                      else
                      {
                          walker = walker.Left;     
                      }
                  }
                  else if (newNode.Data.CompareTo(walker.Data) &gt; 0)
                  {
                      //walk right
                      if (walker.Right == null) 
                      {
                          walker.Right = newNode;
                          newNode.Parent = walker;
                          break;                     
                      }
                      else
                      {
                          walker = walker.Right;
                      }
                  }
                  else //todo: remove me
                  { 
                      //we're equal, ignore this node in general
                      return;
                  }
              }
  
              //rebalance - 
              //at this point we have the parent , we have the newnode and we need to implement some rules.
              Rebalance();
  
  
          }
  
          private void Rebalance()
          {
              RedBlackTreeNode&lt;T&gt; node = Root;
              Stack&lt;RedBlackTreeNode&lt;T&gt;&gt; stack = new Stack&lt;RedBlackTreeNode&lt;T&gt;&gt;();
              while (stack.Count !=0 || node !=null )
              {
                  if (node != null)
                  {
                      stack.Push(node);
                      node = node.Left;
                  }
                  else
                  {
                      node = stack.Pop();
                      Rebalance(node);
                      node = node.Right;
                  }
  
  
              }
  
          }
  
          private void Rebalance(RedBlackTreeNode&lt;T&gt; node)
          {
              if (node.Parent == null) return;
  
              if (node.Parent.Color == NodeColor.Red) //rule 2 or 3
              {
                  if (node.Uncle != null) //the rule 2 - change him to black as well
                  {
                      Rule2(node);
                  }
                  else //if my uncle doesn't exist, it's could be rule 3 or 4, which requires rotation
                  {
                      //if my parent and I are on the same side, 
                      if (node.WhichSideAmIOn() == node.Parent.WhichSideAmIOn())
                      {
                          Rule3(node);
                      }
                      else
                      {
                          Rule4(node);
                      }
                  }
              }
  
  
  
          }
  
          private void Rule2(RedBlackTreeNode&lt;T&gt; node)
          {
              //my parent + uncle needs to be black
              if (node.Parent == null) throw new Exception("um how?");
              node.Parent.Color = NodeColor.Black;
              node.Uncle.Color = NodeColor.Black;
          }
  
          //The rule of two red nodes to the same side
          //if the nodes of the tree are stacked in one direction and the two stacked nodes are red
          //the middle node comes up to the parent and the top node becomes the left or right hand child.
          private void Rule3(RedBlackTreeNode&lt;T&gt; node)
          { 
              //make my grand parent, my parents left|right
              //where am i?
              NodeSide ns = node.WhichSideAmIOn();
  
              if (node.Parent == null) throw new Exception("um how?");
  
              RedBlackTreeNode&lt;T&gt; parent = node.Parent;
              RedBlackTreeNode&lt;T&gt; grandParent = parent.Parent;
              RedBlackTreeNode&lt;T&gt; greatGrandParent = grandParent.Parent;
  
              //set my great, grand parent, to point at my parent
              NodeSide gpSide = grandParent.WhichSideAmIOn();
              if (gpSide == NodeSide.Left)
              {
                  if (greatGrandParent !=null)
                      greatGrandParent.Left = parent;
              }
              else
              {
                  if (greatGrandParent != null)
                      greatGrandParent.Right = parent;
              }
  
              //swap my grandparent into my parent's other child
              if (ns == NodeSide.Left)
              {
                  //set my parents right to my grandParent
                  parent.Right = grandParent;
                  grandParent.Left = null;                             
              }
              else if (ns == NodeSide.Right)
              {
                  //set my parents right to my grandParent
                  parent.Left = grandParent;
                  grandParent.Right = null;
  
              }
  
              //reset the parent, update the root
              parent.Parent = greatGrandParent;
              if (greatGrandParent == null)
              {
                  Root = parent;
              }
  
  
  
              grandParent.Parent = parent;
  
              //swap colors
              parent.Color = NodeColor.Black;
  
              grandParent.Color = NodeColor.Red;
  
  
          }
  
          //The rule of two red nodes on different sides
          //if the nodes of a tree are both red and one goes to the left, but the other goes to the right
          //then the middle node becomes the parent and the top node becomes the left or right child
          private void Rule4(RedBlackTreeNode&lt;T&gt; node)
          {
  
              if (node.Parent == null) throw new Exception("um how?");
  
              RedBlackTreeNode&lt;T&gt; parent = node.Parent;
              RedBlackTreeNode&lt;T&gt; grandParent = parent.Parent;
              RedBlackTreeNode&lt;T&gt; greatGrandParent = grandParent.Parent;            
  
              //fix the reference that will be above me
              NodeSide ns;
              if (grandParent!= null)
              {
                  ns = grandParent.WhichSideAmIOn();
  
                  //replace the reference to my grand parent with me
                  if (ns == NodeSide.Left)
                  {
                      greatGrandParent.Left = node;
                  }
                  else if (ns == NodeSide.Right)
                  {
                      greatGrandParent.Right = node;
                  }                
              }
  
  
              //put my parent and my grand parent on the
              //correct side of me.
              ns = node.WhichSideAmIOn();
              NodeSide parentSide = parent.WhichSideAmIOn();
              if (ns == NodeSide.Left)
              {
                  node.Left = grandParent;
                  node.Right = parent;
  
                  //I was the child of parent, wipe this refernce
                  parent.Left = null;                                
              }
              else
              {
                  node.Left = parent;
                  node.Right = grandParent;
  
                  //i was the child of parent, wipe this reference
                  parent.Right = null;                
              }
  
              parent.Parent = node;
              grandParent.Parent = node;
  
              //parent was the child of grandparent, wipe this reference
              if (parentSide == NodeSide.Left) { grandParent.Left = null; }
              if (parentSide == NodeSide.Right) { grandParent.Right = null; }
  
  
              //reset my parent and root
              node.Parent = greatGrandParent;
              if (greatGrandParent == null)
              {
                  Root = node;
              }
  
              //swap colors
              node.Color = NodeColor.Black;
              grandParent.Color = NodeColor.Red;
          }
  
          public void Print()
          {
              Stack&lt;RedBlackTreeNode&lt;T&gt;&gt; stack = new Stack&lt;RedBlackTreeNode&lt;T&gt;&gt;();
              RedBlackTreeNode&lt;T&gt; temp = Root;
  
              while (stack.Count != 0 || temp != null)
              {
                  if (temp != null)
                  {
                      stack.Push(temp);                    
                      temp = temp.Left;
                  }
                  else
                  {                    
                      temp = stack.Pop();
                      Console.WriteLine(temp.Data.ToString());                    
                      temp = temp.Right;
                  }
  
              }
          }
  
          public double Height 
          { 
              get
              {
                  Stack&lt;RedBlackTreeNode&lt;T&gt;&gt; stack = new Stack&lt;RedBlackTreeNode&lt;T&gt;&gt;();
                  RedBlackTreeNode&lt;T&gt; temp = Root;
  
                  double currentHeight =0;
                  while (stack.Count != 0 || temp != null)
                  {
                      if (temp != null)
                      {
                          stack.Push(temp);
                          if (temp.Left != null || temp.Right != null)
                          {
                              currentHeight++;
                          }
  
                          temp = temp.Left;
                      }
                      else
                      {
                          temp = stack.Pop();
                          temp = temp.Right;
                      }
  
                  }
                  return currentHeight;
              }
          }
  
      }
  
      class Program
      {
          static void Main(string[] args)
          {
              RedBlackTree&lt;int&gt; rbt = new RedBlackTree&lt;int&gt;();
              rbt.InsertNode(1);
              rbt.InsertNode(2);
              rbt.InsertNode(3);
              rbt.InsertNode(4);
              rbt.InsertNode(5);
              rbt.InsertNode(6);
              rbt.InsertNode(7);
              rbt.InsertNode(8);
              rbt.InsertNode(9);
              rbt.InsertNode(10);
              rbt.Print();
              Assert.AreEqual(5, rbt.Height); //make sure sorted vals don't snake off to the left or right
  
              //inert 500 more random numbers, height should remain balanced
              Random random = new Random();
  
              for (int i = 0; i &lt; 500; i++)
              { 
                  rbt.InsertNode(random.Next(0, 10000)); 
              }
  
              Assert.AreEqual(255, rbt.Height);
  
          }
      }
  }
  </code></pre>