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 at 14:13