Red-black tree in C

Question

I would like to verify that the code fulfills the specification of a red-black tree or receive suggestions for improvements.

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
static char BLACK = 'b';
static char RED = 'r';
struct node {
 int key;
 char color;
 struct node *left, *right, *parent;
};
void insert_repair_tree(struct node *n);
void delete_case1(struct node *n);
void delete_case2(struct node *n);
void delete_case3(struct node *n);
void delete_case4(struct node *n);
void delete_case5(struct node *n);
struct node *LEAF;
struct node *parent(struct node *n) {
 return n->parent; // NULL for root node
}
struct node *grandparent(struct node *n) {
 struct node *p = parent(n);
 if (p == NULL)
 return NULL; // No parent means no grandparent
 return parent(p); // NULL if parent is root
}
struct node *sibling(struct node *n) {
 struct node *p = parent(n);
 if (p == NULL)
 return NULL; // No parent means no sibling
 if (n == p->left)
 return p->right;
 else
 return p->left;
}
struct node *uncle(struct node *n) {
 struct node *p = parent(n);
 struct node *g = grandparent(n);
 if (g == NULL)
 return NULL; // No grandparent means no uncle
 return sibling(p);
}
void rotate_left(struct node *n) {
 struct node *nnew = n->right;
 struct node *p = parent(n);
 assert(nnew != NULL); // since the leaves of a red-black tree are empty, they cannot become internal nodes
 n->right = nnew->left;
 nnew->left = n;
 n->parent = nnew;
 // handle other child/parent pointers
 if (n->right != NULL)
 n->right->parent = n;
 if (p != NULL) // initially n could be the root
 {
 if (n == p->left)
 p->left = nnew;
 else if (n == p->right) // if (...) is excessive
 p->right = nnew;
 }
 nnew->parent = p;
}
void rotate_right(struct node *n) {
 struct node *nnew = n->left;
 struct node *p = parent(n);
 assert(nnew != NULL); // since the leaves of a red-black tree are empty, they cannot become internal nodes
 n->left = nnew->right;
 nnew->right = n;
 n->parent = nnew;
 // handle other child/parent pointers
 if (n->left != NULL)
 n->left->parent = n;
 if (p != NULL) // initially n could be the root
 {
 if (n == p->left)
 p->left = nnew;
 else if (n == p->right) // if (...) is excessive
 p->right = nnew;
 }
 nnew->parent = p;
}
void insert_recurse(struct node *root, struct node *n) {
 // recursively descend the tree until a leaf is found
 if (root != NULL && n->key < root->key) {
 if (root->left != LEAF) {
 insert_recurse(root->left, n);
 return;
 } else
 root->left = n;
 } else if (root != NULL) {
 if (root->right != LEAF) {
 insert_recurse(root->right, n);
 return;
 } else
 root->right = n;
 }
 // insert new node n
 n->parent = root;
 n->left = LEAF;
 n->right = LEAF;
 n->color = RED;
}
void insert_case1(struct node *n) {
 if (parent(n) == NULL)
 n->color = BLACK;
}
void insert_case2(struct node *n) {
 return; /* Do nothing since tree is still valid */
}
void insert_case3(struct node *n) {
 parent(n)->color = BLACK;
 uncle(n)->color = BLACK;
 grandparent(n)->color = RED;
 insert_repair_tree(grandparent(n));
}
void insert_case4step2(struct node *n) {
 struct node *p = parent(n);
 struct node *g = grandparent(n);
 if (n == p->left)
 rotate_right(g);
 else
 rotate_left(g);
 p->color = BLACK;
 g->color = RED;
}
void insert_case4(struct node *n) {
 struct node *p = parent(n);
 struct node *g = grandparent(n);
 if (n == g->left->right) {
 rotate_left(p);
 n = n->left;
 } else if (n == g->right->left) {
 rotate_right(p);
 n = n->right;
 }
 insert_case4step2(n);
}
void insert_repair_tree(struct node *n) {
 if (parent(n) == NULL) {
 insert_case1(n);
 } else if (parent(n)->color == BLACK) {
 insert_case2(n);
 } else if (uncle(n)->color == RED) {
 insert_case3(n);
 } else {
 insert_case4(n);
 }
}
struct node *insert(struct node *root, struct node *n) {
 // insert new node into the current tree
 insert_recurse(root, n);
 // repair the tree in case any of the red-black properties have been violated
 insert_repair_tree(n);
 // find the new root to return
 root = n;
 while (parent(root) != NULL)
 root = parent(root);
 return root;
}
void replace_node(struct node *n, struct node *child) {
 child->parent = n->parent;
 if (n == n->parent->left)
 n->parent->left = child;
 else
 n->parent->right = child;
}
int is_leaf(struct node *n) {
 if (n->right == NULL && n->left == NULL)
 return 1;
 else return 0;
}
void delete_one_child(struct node *n) {
 /*
 * Precondition: n has at most one non-leaf child.
 */
 struct node *child = is_leaf(n->right) ? n->left : n->right;
 replace_node(n, child);
 if (n->color == BLACK) {
 if (child->color == RED)
 child->color = BLACK;
 else
 delete_case1(child);
 }
 free(n);
}
void delete_case1(struct node *n) {
 if (n->parent != NULL)
 delete_case2(n);
}
void delete_case2(struct node *n) {
 struct node *s = sibling(n);
 if (s->color == RED) {
 n->parent->color = RED;
 s->color = BLACK;
 if (n == n->parent->left)
 rotate_left(n->parent);
 else
 rotate_right(n->parent);
 }
 delete_case3(n);
}
void delete_case3(struct node *n) {
 struct node *s = sibling(n);
 if ((n->parent->color == BLACK) &&
 (s->color == BLACK) &&
 (s->left->color == BLACK) &&
 (s->right->color == BLACK)) {
 s->color = RED;
 delete_case1(n->parent);
 } else
 delete_case4(n);
}
void delete_case4(struct node *n) {
 struct node *s = sibling(n);
 if ((n->parent->color == RED) &&
 (s->color == BLACK) &&
 (s->left->color == BLACK) &&
 (s->right->color == BLACK)) {
 s->color = RED;
 n->parent->color = BLACK;
 } else
 delete_case5(n);
}
void delete_case6(struct node *n) {
 struct node *s = sibling(n);
 s->color = n->parent->color;
 n->parent->color = BLACK;
 if (n == n->parent->left) {
 s->right->color = BLACK;
 rotate_left(n->parent);
 } else {
 s->left->color = BLACK;
 rotate_right(n->parent);
 }
}
void delete_case5(struct node *n) {
 struct node *s = sibling(n);
 if (s->color == BLACK) { /* this if statement is trivial,
due to case 2 (even though case 2 changed the sibling to a sibling's child,
the sibling's child can't be red, since no red parent can have a red child). */
/* the following statements just force the red to be on the left of the left of the parent,
 or right of the right, so case six will rotate correctly. */
 if ((n == n->parent->left) &&
 (s->right->color == BLACK) &&
 (s->left->color == RED)) { /* this last test is trivial too due to cases 2-4. */
 s->color = RED;
 s->left->color = BLACK;
 rotate_right(s);
 } else if ((n == n->parent->right) &&
 (s->left->color == BLACK) &&
 (s->right->color == RED)) {/* this last test is trivial too due to cases 2-4. */
 s->color = RED;
 s->right->color = BLACK;
 rotate_left(s);
 }
 }
 delete_case6(n);
}
struct node *search(struct node *temp, int val) {
 int diff;
 while (!is_leaf(temp)) {
 diff = val - temp->key;
 if (diff > 0) {
 temp = temp->right;
 } else if (diff < 0) {
 temp = temp->left;
 } else {
 printf("Search Element Found!!\n");
 return temp;
 }
 }
 printf("Given Data Not Found in the tree!!\n");
 return 0;
}
void inorderTree(struct node *root) {
 struct node *temp = root;
 if (temp != NULL) {
 inorderTree(temp->left);
 printf(" %d--%c ", temp->key, temp->color);
 inorderTree(temp->right);
 }
}
void postorderTree(struct node *root) {
 struct node *temp = root;
 if (temp != NULL) {
 postorderTree(temp->left);
 postorderTree(temp->right);
 printf(" %d--%c ", temp->key, temp->color);
 }
}
void traversal(struct node *root) {
 if (root != NULL) {
 printf("root is %d-- %c", root->key, root->color);
 printf("\nInorder tree traversal\n");
 inorderTree(root);
 printf("\npostorder tree traversal\n");
 postorderTree(root);
 }
}
int main() {
 int T = 1000000000; //test case 1000000000 nodes
 int r2;
 struct node *root = NULL;
 srand(time(NULL));
 struct node *z;
 LEAF = malloc(sizeof(struct node));
 LEAF->color = BLACK;
 LEAF->left = NULL;
 LEAF->right = NULL;
 LEAF->key = 0;
 //printf("starting loop!\n");
 while (T-- > 0) {
 r2 = (2 + T) * (rand() % 100); // data
 z = malloc(sizeof(struct node));
 //printf(" loop!\n");
 if (z != NULL) {
//printf(" test!\n");
 z->key = r2;
 z->left = NULL;
 z->right = NULL;
 z->parent = NULL;
 z->color = RED;
//printf(" test2!\n");
 root = insert(root, z);
//printf(" test3!\n");
 } else printf("malloc failed at node number %d", T);
 }
 root = NULL;
 return 0;
}
int test() {
 printf("Hello!\n");
 struct node *root = NULL;//malloc(sizeof(struct node));
 LEAF = malloc(sizeof(struct node));
 LEAF->color = BLACK;
 LEAF->left = NULL;
 LEAF->right = NULL;
 LEAF->key = 0;
 int choice, val, var, fl = 0;
 while (1) {
 setbuf(stdout, 0); // Bugfix for debugging mode on Windows
 printf("\nEnter your choice :1:Add 2:Delete 3:Find 4:Traverse 5: Test 6:Exit\n");
 scanf("%d", &choice);
 switch (choice) {
 case 1:
 setbuf(stdout, 0);
 printf("Enter the integer you want to add : ");
 scanf("%d", &val);
 struct node *z = malloc(sizeof(struct node));
 z->key = val;
 z->left = NULL;
 z->right = NULL;
 z->parent = NULL;
 z->color = RED;
 root = insert(root, z);
 printf("The root is now %d: ", root->key);
 break;
 case 2:
 printf("Enter the integer you want to delete : ");
 scanf("%d", &var);
 delete_one_child(search(root, var));
 break;
 case 3:
 printf("Enter search element \n");
 scanf("%d", &val);
 search(root, val);
 break;
 case 4:
 traversal(root);
 break;
 case 5: // TODO
 test();
 break;
 case 6:
 fl = 1;
 break;
 default:
 printf("\nInvalid Choice\n");
 }
 if (fl == 1) { break; }
 }
 return 0;
}

I have also added test code which builds up a large tree, the test completes on Linux but on Windows 10 malloc starts returning NULL after approx. 55 million nodes.

 int test() {
 int T = 1000000000; //test case 1000000000 nodes
 int r2;
 struct node *root = NULL;
 srand(time(NULL));
 struct node *z;
 LEAF = malloc(sizeof(struct node));
 LEAF->color = BLACK;
 LEAF->left = NULL;
 LEAF->right = NULL;
 LEAF->key = 0;
 while (T-- > 0) {
 r2 = (2 + T) * (rand() % 100); // data
 z = malloc(sizeof(struct node));
 if (z != NULL) {
 z->key = r2;
 z->left = NULL;
 z->right = NULL;
 z->parent = NULL;
 z->color = RED;
 root = insert(root, z);
 } else printf("malloc failed at node number %d", T);
 }
 root = NULL;
 return 0;
 }

• user1118321: I get a crash running the test on the first few iterations through the loop. Always on line 181, though the exact number of iterations varies each time. This line: ` } else if (uncle(n)->color == RED) {`. Building on macOS with llvm 9 set to C11.
• Niklas Rosencrantz: @user1118321 It's because the LEAF was null, I just updated the code with proper test including declaration of LEAF.
• user1118321: It still crashes for me. Also, you forgot to #include <time.h>.
• Niklas Rosencrantz: @user1118321 Thanks for testing! It should work from here (including everything) github.com/montao/rbtree2/blob/master/rbtree.c
• Niklas Rosencrantz: @user1118321 I am adding tests with an integration server now (travis-ci) to see what comes out. Thanks a lot for testing and reporting back.

Answer 1

Some suggestions:

• Your code is non-reentrant; that is, it can't be called by more than one user at a time due to the global LEAF. Don't have that as a global. It should be passed into your functions, either as a member of a struct if appropriate, or a separate argument.
• Use typedef so that you don't have to write struct node 100 times.
• Use const where appropriate. If you're not modifying an argument, e.g. in functions like parent, make the arg const.
• if (p != NULL) can be written if (p). if (p == NULL) can be written if (!p).
• Resist the 1980s temptation to declare all of your variables at the top. Declare them where they're used, especially for cases like this -

Your loop

int T = 1000000000; 
....
while (T-- > 0) {

can be written as

for (int T = 1000000000; T > 0; T--)

• It's good to have tests. It's better to have automated tests. Think about replacing your "interactive" test function with a series of tests that try out various features in your code and apply asserts.

• Niklas Rosencrantz: Thanks! I'm making these changes now. The automated test appears: travis-ci.org/montao/rbtree2