# Slow insertion into a Red Black tree

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, parent;  // child is left, child 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
}


• 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". – Roland Illig Apr 20 '19 at 14:13

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.