1
\$\begingroup\$

I am trying to implement a red black tree. The problem is that the code runs slowly and I wonder if I did something wrong or just did it too many times. I already checked and the problem is in the insertion part. Can you possibly review my code for performance and best coding practices?

Code

typedef struct RBNode* RBNodePtr;
typedef enum Color { RED, BLACK } Color;

typedef struct RBNode {
    RBNodePtr child[2], parent;  // child[0] is left, child[1] is right.
    int key, size;               // size is the subtree size.
    Color color;
} RBNode;

RBNode NIL_T_NODE;
RBNodePtr NIL_T = &NIL_T_NODE;

int flag = 0;
int first_flag = 1;

RBNodePtr Rotate(RBNodePtr* Root, RBNodePtr node, int side)
{
    // rotate RB tree to "side" direction -
    //  Just fixing all pointers and moving some nodes
    RBNodePtr y = node->child[!side];
    int temp = y->size;
    y->size = node->size;
    node->size = node->size - temp + y->child[side]->size;
    node->child[!side] = y->child[side];
    if (y->child[side] != NIL_T) y->child[side]->parent = node;
    y->parent = node->parent;
    if (node->parent == NIL_T)
        (*Root) = y;
    else if (node == node->parent->child[side])
        node->parent->child[side] = y;
    else
        node->parent->child[!side] = y;
    y->child[side] = node;
    node->parent = y;

    return *Root;
}

void RB_fixup(RBNodePtr* Root, RBNodePtr node) 
{
    // fix insert violation according to the algorithms
    RBNodePtr temp;
    while (node->parent->color == RED) {
        if (node->parent == node->parent->parent->child[LEFT]) {
            temp = node->parent->parent->child[RIGHT];
            if (temp->color == RED) {
                // case 1- side 1
                node->parent->color = BLACK;
                temp->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->child[RIGHT]) {
                    // case 2- side 1
                    node = node->parent;
                    *Root = Rotate(Root, node, LEFT);
                }
                node->parent->color = BLACK;  // case 3- side 1
                node->parent->parent->color = RED;
                *Root = Rotate(Root, node->parent->parent, RIGHT);
            }
        } else {
            // all cases again just flips sides- same thing
            temp = node->parent->parent->child[LEFT];
            if (temp->color == RED) {
                node->parent->color = BLACK;
                temp->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->child[LEFT]) {
                    node = node->parent;
                    *Root = Rotate(Root, node, RIGHT);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                *Root = Rotate(Root, node->parent->parent, LEFT);
            }
        }
    }
    (*Root)->color = BLACK;
}

RBNodePtr rb_insert(RBNodePtr tnode, int k)
{
    // insert a new node z
    RBNodePtr z = new_rb_node(k);
    RBNodePtr y = NIL_T;  // will be parent of z
    RBNodePtr x = tnode;
    RBNodePtr temp = rb_search(tnode, k);
    if (temp == NULL || temp == NIL_T) {
        // only insert if k isn't in tree
        while (x && x != NIL_T) {
            // go down the tree and look for a spot to insert
            y = x;
            x->size++;
            if (z->key < x->key)
                x = x->child[LEFT];
            else
                x = x->child[RIGHT];
        }
        z->parent = y;  // update all pointers after the insertion
        if (y == NIL_T)
            tnode = z;
        else if (z->key < y->key)
            y->child[LEFT] = z;
        else
            y->child[RIGHT] = z;

        RB_fixup(&tnode, z);  // fix violation
    }
    return tnode;
}

RBNodePtr new_rb_node(int k)
{
    if (first_flag) {
        // initialize NIL_T for the first and only time
        NIL_T->color = BLACK;
        NIL_T->child[LEFT] = NULL;
        NIL_T->child[RIGHT] = NULL;
        NIL_T->parent = NULL;
        NIL_T->key = 0;
        NIL_T->size = 0;

        first_flag = 0;
    }
    // allocate space for new node
    RBNodePtr temp = (RBNodePtr)malloc(sizeof(RBNode));
    if (!temp) {
        return NULL;
    }
    temp->size = 1;  // initialize new node
    temp->key = k;
    temp->color = RED;
    temp->child[LEFT] = NIL_T;
    temp->child[RIGHT] = NIL_T;
    temp->parent = NIL_T;

    return temp;
}

RBNodePtr rb_search(RBNodePtr tnode, int k)
{
    // search for node with key k
    while (tnode != NULL && tnode != NIL_T && tnode->key != k) {
        // if tree exist and didn't reach leaf or found the correct node
        if (tnode->key > k)  // go left or right in binary search tree
            tnode = tnode->child[LEFT];
        else
            tnode = tnode->child[RIGHT];
    }
    return tnode;
    // return the correct node/ NIL_T if couldn't found and NULL
    // if tree doesn't exist
}
\$\endgroup\$
  • \$\begingroup\$ There are several other people on this site who have implemented a red black tree in C. You could take their implementations and compare it with yours, to get some more ideas. Just search for "red black tree c". \$\endgroup\$ – Roland Illig Apr 20 at 14:13
1
\$\begingroup\$

Why does Rotate return the modified root node as both a pointer parameter, and return it by value? It should do one or the other. Everywhere you call that function you assign the returned node to Root, which is also passed in as the first parameter.

RB_fixup has a lot of duplicated code. You can eliminate that by setting a variable to specify if you're working with the LEFT or RIGHT branch.

rb_insert leaks memory if a value is already in the tree, since it would allocate a node, not store the pointer anywhere, and not free it up. It would be better to not allocate z until you know you're going to use it. You also call rb_search to see if the node exists, then essentially do the same thing again (while increasing the counts). These could be combined into only one walk down the tree, and another back up to increase the counts if the node is added.

There's also a little inconsistency there, as you use a less than comparison in rb_insert but a greater than comparison in rb_search. This can be a bit confusing.

I don't see why you're using NIL_T. Everywhere you're using it will work just as well using NULL. You compare node pointers to see if they're pointing to this special node, but you never dereference it.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the comments, I will try to change most of it. As for the NIL_T, it is defined to have color black(unlike null which isn't even a node) and the main algorithms check for colors and assume NIL_T has a black color. One more thing, do you happen to have an idea why my code is running slowly besides what you have written? Thank you \$\endgroup\$ – Roni Apr 21 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.