C# reference trouble...

Question

Hi, I'm taking an algorithm course at the university, and for one of my projects I want to implement a red-black tree in C# (the implementation itself isn't the project, yet just something i decided to choose to help me out).

My red-black tree should hold string keys, and the object i created for each node looks like this :

class sRbTreeNode
{
    public sRbTreeNode Parent = null;
    public sRbTreeNode Right = null;
    public sRbTreeNode Left = null;
    public String Color;
    public String Key;

    public sRbTreeNode()
    {
    }

    public sRbTreeNode(String key)
    {
        Key = key;
    }
}

I already added some basic methods for printing the tree, finding the root, min/max key (by alphabet), etc...

I'm having trouble inserting nodes (hence, building the tree). Whoever's familiar with red-black trees knows that when adding a node to one side, you could have changed the balance of the tree. To fix this, you need to "rotate" around nodes on the tree in order to balance the tree out.

I wrote a RightRotate and LeftRotate method in pseudo-code, and then when i tried to implement it in C#, i ran into a bunch of reference problems with the sRbTreeNode object i created.

This is the pseudo-code I wrote for the LeftRotate method :

LeftRotate(root, node)
    y <- node.Right;
    node.Right <- y.Left;
    if (y.Left != null)
        y.Left.Parent <- node;
    y.Parent <- node.Parent;
    if (node.Parent = null)
        root <- y;
    else
        if (node = node.Parent.Left)
            node.Parent.Left = y;
        else
            node.Parent.Right = y;
    y.Left <- node;
    node.Parent <- y

I received a suggestion to implement it straight forward, but without using the 'ref' keyword, which i tried at first. This is how i did it :

public static void LeftRotate(sRbTreeNode root, sRbTreeNode node)
    {
        sRbTreeNode y = node.Right;
        node.Right = y.Left;
        if (y.Left != null)
            y.Left.Parent = node;
        y.Parent = node.Parent;
        if (node.Parent == null)
            root = y;
        else
            if (node == node.Parent.Left)
                node.Parent.Left = y;
            else
                node.Parent.Right = y;
        y.Left = node;
        node.Parent = y;
    }

Now, when i debug, i see that it works fine, but the objects i pass to this method are only rotated within the scope of the method. When it leaves this method, it seems like there was no change to the actual nodes. That is why i thought of using the 'ref' keywords in the first place.

What am i doing wrong ?

Answer 1

I don't see why you should have had any issues with references - the Left/Right/Parent nodes can be copied just as in this pseudo-code.

You should be able to expand it to C# without too much fuss - unless you're using the 'ref' keyword, in which case you could very well get unpredictable results.

Perhaps if you could show the code you've actually written thus far, and we can help debug that.

Answer 2

My recommendations:

• Do not include parent pointers. They are not essential for the insertion or deletion algorithms and will make your code more complex. For example LeftRotate can be written with just one parameter and will be about half as long if you do not use parent pointers.
• Use an enum for the Color property rather than a string, and initialise it in the constructor.
• Read this article if you haven't already.

Answer 3

Because in the body of your method you do this:

root = y;

you need to pass root in with a ref modifier. node doesn't need one, becausenode itself is never updated to point at a different ndoe. .