Red-Black Tree Deleting Problem C#

Question

Hey,

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.

DeleteFixUp is responsible for balancing out the tree again (using rotations and by changing the nodes colors) after a delete.

I tried implementing the method from the pseudo code i found in a book called "Introduction to Algorithms".

Here is my code :

private static void DeleteFixup(ref sRbTreeNode root, sRbTreeNode x)
    {
        sRbTreeNode y;

        while (x != root && 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 &&
                    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 &&
                    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;
    }

I keep running into the error "Object reference not set to an instance of an object" each time in different places...

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...

Can someone please help me, before i start tearing my hairs out!!... ?? :)

Answer 1

There are null parameters slipping in somewhere.

If x == null, then we crash as soon as we test the if.

If any of x.Parent's children are null, we also crash.

You need to test for those null conditions and handle them appropriately.

Answer 2

Let's see...

   while (x != root && (x == null || x.Color == BLACK))
    {
        if (x == x.Parent.Left)         // determine sub tree from parent

So, if x is null at the start, you try to dereference x.Parent, which is going to throw the exception you're getting. I looked at two lines and already found one bug.

You need to check each reference for null at some point prior to dereferencing.

Answer 3

While perhaps not a direct answer to your question, you will learn an incredible amount by simply stepping through your code in the debugger. Plus you will probably resolve the issue yourself! If you need help setting a break point, inspecting variables or stepping please let me know. Visual Studio is so easy to use it's almost brain-dead.

Answer 4

After some research, I found out that the problem was in the way i was handling the Red-Black trees i built.

According to books on the subject (including the one i'm learning from!), you're supposed to have every node at the bottom of your tree lead to a "null node". A null node is a node that has no value and is black in color. I thought i wouldn't have to implement null nodes on my tree, and in every place where there was a check for a black node, i added " || node == null" because it might be checking for a null node. The problem was that sometimes you need to check the null node's parent, and if you don't actually implement the "null node" so you'll get an error when trying to reach it's Parent property.

I implemented a "null node" by just adding a node with empty values and Black coloring to every node without children. It required a little tweaking to most of the manipulation methods on the tree, but in the end it solved (almost) all of my problems.

Thanks everyone for trying to help me out!! :)