Red Black Tree insertion operation keeps on crashing

Question

I was trying to implement Red Black Tree but was unable to code it myself so I was searching for it's code written in C and found the below code on github I analyzed it and it was pretty straight forward and simple so I did a little modifications (just renamed a couple of variables and added a menu) and when I tried to run it I faced a problem when trying to rotate the tree. Insertion works fine until the tree get's unbalanced specially when the uncle becomes "Black" my program fails to rotate the tree and it just crashes. So Let me explain you the flow of the program: whenever we insert a new node a function named insert gets called, after a successful insertion it calls another function named insertfixup which checks whether any properties of the Red Black Tree have been violated and if so then it rotates the tree on the basis of whether the uncle of the problematic node is RED or BLACK if the uncle is Red then it works fine, but soon as the uncle becomes Black then it just crashes. Can someone please examine the code I have given below and point out what exactly is causing the problem, I doubt it has something to do with the pointers but can't figure out what is actually happening,

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef struct RB_Tree {
    struct RB_Tree *left, *right, *parent;
    int info;
    char color;
} node;
int count = 0;

void left_rotate(node **root, node *par) {  
    node *child = par->right;

    par->right = child->left;

    if (child->left!=NULL)
        child->left->parent = par;

    child->parent = par->parent;

    if (par->parent == NULL)
        (*root) = child;
    else
    if (par == par->parent->left)
        par->parent->left = child;
    else
        par->parent->right = child; 

    child->left = par;
    par->parent = child;
}

void right_rotate(node **root, node *par) {
    node *child = par->left;

    par->left = child->right;

    if (child->right!=NULL)
        child->right->parent = par;

    child->parent = par->parent;

    if (par->parent == NULL)
        (*root) = child;
    else
    if (par = par->parent->left)
        par->parent->left = child;
    else
        par->parent->right = child;

    child->right = par;

    par->parent = child;
}

void insertFixup(node **root, node *new) {
    while (new != *root && new->parent->color == 'R') {
        node *uncle;
        //Find uncle and store uncle in "uncle" variable!

        if (new->parent == new->parent->parent->left) {
            uncle = new->parent->parent->right;
        } else {
            uncle = new->parent->parent->left;
        }

        if (uncle == NULL || uncle->color == 'B') {

            if (new->parent == new->parent->parent->left && new == new->parent->left) {
                printf("Inside ll case before rot");
                char col = new->parent->color;
                new->parent->color = new->parent->parent->color;
                new->parent->parent->color = col;

                right_rotate(root, new->parent->parent);
            }

            if (new->parent == new->parent->parent->right && new == new->parent->right) {
                char col = new->parent->color;
                new->parent->color = new->parent->parent->color;
                new->parent->parent->color = col;
                left_rotate(root, new->parent->parent);
            }

            if (new->parent == new->parent->parent->left && new == new->parent->right) {
                char col = new->color;
                new->color = new->parent->parent->color;
                new->parent->parent->color = col;
                //printf("\nHere we are in the left right!");
                left_rotate(root, new->parent);

                right_rotate(root, new->parent->parent); 
            }

            if (new->parent == new->parent->parent->right && new == new->parent->left) {
                char col = new->color;
                new->color = new->parent->parent->color;
                new->parent->parent->color = col;
                right_rotate(root, new->parent);
                left_rotate(root, new->parent->parent);
            }
        }

        if (uncle) {
            if (uncle->color == 'R') {
                uncle->color = 'B';
                new->parent->color = 'B';
                new->parent->parent->color = 'R';
                new = new->parent->parent;
            }
        }
    }

    (*root)->color = 'B';
}

void insert(node **root, int data) {
    node *new = (node*)malloc(sizeof(node));
    new->info = data;
    new->parent = new->left = new->right = NULL;

    if (*root == NULL) {
        (*root) = new;
        new->color = 'B';
    } else {
        node *par;
        node *temp = (*root);

        while (temp) {
            par = temp;
            if(new->info > temp->info)
                temp = temp->right;
            else
                temp = temp->left;
        }

        new->parent = par;

        if (par->info > new->info)
            par->left = new;
        else
            par->right = new;

        new->color = 'R';

        insertFixup(root, new);
    }
}

void main() {
    int men, c, data;
    node *root = NULL;

    while (1) {
        system("cls");
        printf("1.) Insert\n");
        printf("2.) exit\n");
        printf("Enter your choice : ");
        scanf("%d", &men);
        switch (men) {
          case 1:
            printf("Enter data : ");
            scanf("%d", &data);
            insert(&root, data);
            printf("%d successfully added!", data);
            break;

          case 2:
            exit(0);

          default:
            printf("Invalid choice!");
            while ((c = fgetc(stdin)) != '\n') {}
            break;       
        }
        getch();
    }
}

Answer 1

Compile with warnings, on line 53:

else if(par = par->parent->left)
    par->parent->left = child;

you are assigning, you want to compare:

else if(par == par->parent->left)
    par->parent->left = child;

Answer 2

Main problems

As already said line 53

else if(par = par->parent->left)

must be

else if(par == par->parent->left)

The algorithm in insertFixup is not the right one, for instance to insert the data 3 then 2 then 1 produces a crash, I see an identical definition on internet, probably you got it but unfortunately your source is bugged. That definition works :

void insertFixup(node **root, node *new) {
  while (new != *root && new->parent->color == 'R') {
    if (new->parent == new->parent->parent->left) {
      if (new->parent->parent->right && new->parent->parent->right->color == 'R') {
        new->parent->color = 'B';
        new->parent->parent->right->color = 'B';
        new->parent->parent->color = 'R';
        new = new->parent->parent;
      }
      else {
        if (new == new->parent->right) {
          new = new->parent;
          left_rotate(root, new);
        }

        new->parent->color = 'B';
        new->parent->parent->color = 'R';
        right_rotate(root, new->parent->parent);
      }
    }
    else {
      if (new->parent->parent->left && new->parent->parent->left->color == 'R') {
        new->parent->color = 'B';
        new->parent->parent->left->color = 'B';
        new->parent->parent->color = 'R';
        new = new->parent->parent;
      }
      else {
        if (new == new->parent->left) {
          new = new->parent;
          right_rotate(root, new);
        }

        new->parent->color = 'B';
        new->parent->parent->color = 'R';
        left_rotate(root, new->parent->parent);
      }
    }
  }

  (*root)->color = 'B';
}

Additional problems

The signature of *main * is wrong, main returns an int

If the user does not input an int your scanf line 160 does not set men and you can test a never initialized value. Always check the return value of scanf, for instance to be compatible with the code after :

if (scanf("%d", &men) != 1)
  men = -1;

In

while ((c = fgetc(stdin)) != '\n') {}

c is set but never used, and worst if you reach EOF for instance because the input was redirected on a file you will loop without ending. For instance do

while ((c = fgetc(stdin)) != '\n')
  if (c == EOF)
    exit(0);

Line 10 :

int count = 0;

define a global variable never used, you can remove that line

---

To check my proposal I added that function to show the tree :

void display(node * x){
  if (x) {
    display(x->left);
    printf("%d ", x->info);
    display(x->right);
  }
}

and I modified your main to be able to show the tree :

int main()
{
  int men, c, data;
  node *root = NULL;

  while (1) {
    fputs("\n"
          "1.) Insert\n"
          "2.) exit\n"
          "3.) Display tree\n"
          "Enter your choice : ",
          stdout);
    if (scanf("%d", &men) != 1)
      men = -1;

    switch (men) {
    case 1:
      printf("Enter data : ");
      scanf("%d", &data);
      insert(&root, data);
      printf("%d successfully added!", data);
      break;

    case 2:
      exit(0);

    case 3:
      display(root);
      putchar('\n');
      break;

    default:
      puts("Invalid choice!");
      while ((c = fgetc(stdin)) != '\n')
        if (c == EOF)
          exit(0);
      break;       
    }
  }
}

Compilation and execution :

bruno@bruno-XPS-8300:/tmp/t$ gcc -Wall -Wextra t.c
bruno@bruno-XPS-8300:/tmp/t$ ./a.out

1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 3
3 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 2
2 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 1
1 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 3
1 2 3 

1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 5
5 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 4
4 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 3
1 2 3 4 5 

1.) Insert
2.) exit
3.) Display tree
Enter your choice : 2
bruno@bruno-XPS-8300:/tmp/t$