Is this implementation of a Red Black Tree C# correct?

Question

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?

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<T>
        where T : IComparable<T>
    {
        public RedBlackTreeNode<T> Left { get; set; }
        public RedBlackTreeNode<T> Right { get; set; }
        public RedBlackTreeNode<T> Parent { get; set; }
        public T Data {get; set;}
        public NodeColor Color { get; set; }
        public RedBlackTreeNode<T> 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<T>
        where T : IComparable<T>
    {
        private RedBlackTreeNode<T> Root { get; set; }

        public void InsertNode(T data)
        { 
            //make a node to hold the data - always red
            RedBlackTreeNode<T> newNode = new RedBlackTreeNode<T>();
            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<T> walker = Root;
            while (walker != null)
            {
                if (newNode.Data.CompareTo(walker.Data)< 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) > 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<T> node = Root;
            Stack<RedBlackTreeNode<T>> stack = new Stack<RedBlackTreeNode<T>>();
            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<T> 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<T> 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<T> 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<T> parent = node.Parent;
            RedBlackTreeNode<T> grandParent = parent.Parent;
            RedBlackTreeNode<T> 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<T> node)
        {

            if (node.Parent == null) throw new Exception("um how?");

            RedBlackTreeNode<T> parent = node.Parent;
            RedBlackTreeNode<T> grandParent = parent.Parent;
            RedBlackTreeNode<T> 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<RedBlackTreeNode<T>> stack = new Stack<RedBlackTreeNode<T>>();
            RedBlackTreeNode<T> 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<RedBlackTreeNode<T>> stack = new Stack<RedBlackTreeNode<T>>();
                RedBlackTreeNode<T> 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<int> rbt = new RedBlackTree<int>();
            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 < 500; i++)
            { 
                rbt.InsertNode(random.Next(0, 10000)); 
            }

            Assert.AreEqual(255, rbt.Height);

        }
    }
}

Answer 1

I think your test is incorrect, although I think your code has other problems that the test isn't catching.

First of all, the Height property does not actually return the height, but the number of nodes with at least one child. If you want the height of the deepest node then you should do something like currentHeight = Math.Max(currentHeight, stack.Count) on each iteration instead. You may also want it to return an int rather than a double.

The number of nodes without children should be approximately half of them like you want, but red-black trees are not perfectly balanced. You can have a valid tree with one third of the nodes having one child, one third having two, and one third having none: start with a perfectly balanced tree with all black nodes at the last level and add a red child to each one. This maintains the red-black tree invariants, but as many as two-thirds of the nodes will have children.

Similarly, if you were to test depth it would be between log(N) and 2 log(N).

You may want to write tests that verify the invariants of the tree directly. Visit every node in the tree, and verify that every red node has a black parent and that every path to a leaf contains the same number of black nodes. If you run those tests after every insert in your test suite, you can be sure that the tree is always balanced.

As for the code itself, your Rebalance method crawls the entire tree on every insert. This means insert will require O(N) time and will negate the benefits of using a self-balancing tree. Retrieval will still be O(log N), but you could get the same result by keeping a sorted list and inserting elements into the appropriate place. You should only have to rebalance the tree along the path being inserted, which will only be O(log N) nodes.

I think some of your transformations are wrong. You don't check the color of the current node before calling Rule2, and that rule appears to change nodes to black without ensuring that other paths in the tree have the same number of black nodes. (I may be misreading it; red-black trees are too complicated to do entirely in my head.)

If you're looking for a reference implementation, the Wikipedia page on Red-black trees has an implementation in C that could easily be translated to C#, and SortedSet<T> is implemented using a red-black tree that you can view with Reflector.