Take the 2-minute tour ×

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;
        if (node = node.Parent.Left)
            node.Parent.Left = y;
            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;
            if (node == node.Parent.Left)
                node.Parent.Left = y;
                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 ?

share|improve this question
As Andras says, show us the code so far and we'll give it a shot. –  C. Ross Feb 12 '10 at 13:20
add comment

3 Answers

up vote 2 down vote accepted

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

share|improve this answer
Just tried it, and it finally works!! I can't believe it was that easy, and i didn't realize that!... Thanks a lot! –  gillyb Feb 12 '10 at 14:39
add comment

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.

share|improve this answer
Well, i was trying to use the ref keyword, and i thought that was the right way to do it... I'll try without using ref, and see how it goes, Thanks. –  gillyb Feb 12 '10 at 13:24
I just edited the question with the code i tried so far, maybe it will help you help me, since it doesn't fully work, I explained why in the edited question above. –  gillyb Feb 12 '10 at 14:27
Well - there you go - @AakashM sorted it for you! –  Andras Zoltan Feb 12 '10 at 14:41
add comment

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.
share|improve this answer
I need the parent pointers for something else that has to do with the structure. This will make it much faster to travel along the tree. –  gillyb Feb 12 '10 at 13:21
Even if you do need them, it might be easier to implement the algorithms without them first and add them in later. –  finnw Feb 12 '10 at 13:43
add comment

Your Answer


