I am trying to implement red black tree in C. For reference I am using CLRS.
But when I run the code I am getting "Segmentation fault (core dumped)" error message.
I can't figure out what's wrong in my code so, could anyone tell me what's wrong in my code?
The problem seems to be in the function rb_insert_fixup(), but I don't know what's wrong in it.
Code
#include <stdio.h>
#include <stdlib.h>
//constants
#define RED 0
#define BLACK 1
struct node
{
int key;
struct node *left;
struct node *right;
struct node *parent;
int color;
};
struct node *rb_insert(struct node *tree, struct node *z);
struct node *rb_insert_fixup(struct node *tree, struct node *z);
struct node *left_rotate(struct node *t, struct node *x);
struct node *right_rotate(struct node *t, struct node *x);
struct node *create_node(int key);
int main()
{
struct node *tree = NULL;
struct node *new;
new = create_node(5);
tree = rb_insert(tree, new);
new = create_node(15);
tree = rb_insert(tree, new);
new = create_node(4);
tree = rb_insert(tree, new);
new = create_node(14);
tree = rb_insert(tree, new);
printf("inserting 14\n");
printf("%d %d\n%d %d\n", (tree->left)->key, (tree->left)->color, ((tree->right)->left)->key, ((tree->right)->left)->color);
return 0;
}
struct node *rb_insert_fixup(struct node *tree, struct node *z)
{
struct node *y = NULL;
printf("fixup \n");
while ( z->parent != NULL && (z->parent)->color == RED )
{
printf("while\n");
if ( (z->parent)->parent != NULL && printf("if condition %d\n", (((z->parent)->parent)->left)->color) && z->parent == ((z->parent)->parent)->left )
{
printf("start if\n");
y = ((z->parent)->parent)->right;
if ( y->color == RED )
{
(z->parent)->color = BLACK;
y->color = BLACK;
((z->parent)->parent)->color = RED;
z = (z->parent)->parent;
}
else if ( z == (z->parent)->right )
{
z = z->parent;
tree = left_rotate(tree, z);
}
(z->parent)->color = BLACK;
((z->parent)->parent)->color = RED;
tree = right_rotate(tree, ((z->parent)->parent));
printf("End if\n");
}
else
{
y = ((z->parent)->parent)->left;
if ( y->color == RED )
{
(z->parent)->color = BLACK;
y->color = BLACK;
((z->parent)->parent)->color = RED;
z = (z->parent)->parent;
}
else if ( z == (z->parent)->left )
{
z = z->parent;
tree = right_rotate(tree, z);
}
(z->parent)->color = BLACK;
((z->parent)->parent)->color = RED;
tree = left_rotate(tree, ((z->parent)->parent));
printf("End else\n");
}
printf("End while\n");
}
tree->color = BLACK;
return tree;
}
struct node *rb_insert(struct node *tree, struct node *z)
{
struct node *y = NULL;
struct node *x = tree;
while (x != NULL)
{
y = x;
if (z->key < x->key)
{
x = x->left;
}
else
{
x = x->right;
}
}
z->parent = y;
if (y == NULL)
{
tree = z;
}
else if (z->key < y->key)
{
y->left = z;
}
else
{
y->right = z;
}
z->left = NULL;
z->right = NULL;
z->color = RED;
tree = rb_insert_fixup(tree, z);
//printf("bye insert\n");
return tree;
}
struct node *right_rotate(struct node *t, struct node *x)
{
struct node *y = x->left;
x->left = y->right;
if (y->right != NULL)
{
(y->right)->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL)
{
t = y;
}
else if (x == (x->parent)->left)
{
(x->parent)->left = y;
}
else
{
(x->parent)->right = y;
}
y->right = x;
x->parent = y;
return t;
}
struct node *left_rotate(struct node *t, struct node *x)
{
struct node *y = x->right;
x->right = y->left;
if (y->left != NULL)
{
(y->left)->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL)
{
t = y;
}
else if (x == (x->parent)->left)
{
(x->parent)->left = y;
}
else
{
(x->parent)->right = y;
}
y->left = x;
x->parent = y;
return t;
}
struct node *create_node(int key)
{
struct node *new = malloc(sizeof(struct node));
if (new == NULL)
{
fprintf(stderr, "Malloc failed to create a new node\n");
exit(EXIT_FAILURE);
}
else
{
new->key = key;
new->left = NULL;
new->right = NULL;
new->parent = NULL;
new->color = BLACK;
}
}
I have written the code wrong. After writing it again from scratch (using CLRS) and including sentinal node this time, everything is fine. The rb_delete_fixup() function is as follows. The changes are in inner if-else. Similarly we have to change the inner if-else of rb_insert_fixup. It was a blunder to not write the correct code from the pseudocode.