Segmentation fault - Red Black Trees

Question

It's been now many days that I cannot get out of this problem. I am trying to implement a simple red-black tree (in C) with an extra function that calculates the clock time throughout the period of inserting and searching in the tree.

Bellow is my code:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <limits.h>

#define RED 'R'
#define BLACK 'B'


typedef struct rbtNode{
    int key;
    char color; //this time i also added the color since its an rbt
    struct rbtNode *leftChild;
    struct rbtNode *rightChild;
    struct rbtNode *parent;
} rbtNode;

struct tree{
    int cardinality;
    struct rbtNode *root; 
};


struct rbtNode* TNIL(){
   rbtNode *temp = (rbtNode*)malloc(sizeof(rbtNode));
   temp->key;
   temp->color = 'B';
   temp->leftChild = NULL;
   temp->rightChild = NULL;
   temp->parent = NULL;
   
   return temp;

};

struct rbtNode* RootCreator(int key){
   rbtNode *temp = (rbtNode*)malloc(sizeof(rbtNode));
   temp->key = key;
   temp->color = 'B';
   temp->leftChild = NULL;
   temp->rightChild = NULL;
   temp->parent = NULL;
   
   return temp;
};


//function for creating a new node
struct rbtNode* newNodeRBT(int key){
    rbtNode *temp =(rbtNode*)malloc(sizeof(rbtNode));
    temp->key = key;
    temp->color = 'R';
    temp->leftChild = NULL;
    temp->rightChild = NULL;
    temp->parent = NULL;

    return temp;
}

//function for performing a left side rotation
void TreeLeftRotate(struct rbtNode* root, struct rbtNode* x){
    struct rbtNode* t_nil = TNIL();

    struct rbtNode* y = x->rightChild; //y is initialize
    x->rightChild = y->leftChild; //y's left subtree are turning into x's right subtree

    if(y->leftChild != t_nil){
        y->leftChild->parent = x; //y's left subtree's parent is x
    }

    y->parent = x->parent; //y's parent is x's parent

    if(x->parent == t_nil){
        root = y;
    }else if (x->parent != t_nil && x == x->parent->leftChild){
        x->parent->leftChild = y;
    }else if(x->parent != t_nil && x == x->parent->rightChild){
        x->parent->rightChild = y;
    }
    y->leftChild = x; //x is turning into y's left subtree
    x->parent = y; //x's parent is y
}

//function for performing a right side rotation
void TreeRightRotate(struct rbtNode* root, struct rbtNode* y){
    struct rbtNode* t_nil = TNIL();

    struct rbtNode* x = y->leftChild; //x is initialize
    y->leftChild = x->rightChild; //x's right subtree is turning into y's left subtree

    if(x->rightChild != t_nil){
        x->rightChild->parent = y; //x's right subtree's parent is y
    }

    x->parent = y->parent; //x's parent is y's parent

    if(y->parent == t_nil){
        root = x;
    }else if (y->parent != t_nil && y == y->parent->rightChild){
        y->parent->rightChild = x;
    }else if(y->parent != t_nil && y == y->parent->leftChild){
        y->parent->leftChild = x;
    }
    x->rightChild = y; //y is turning into x's right subtree
    y->parent = x; //y's parent is x
}

//function for implementing the fixup for the left side, this function is needed for performing the insert fixup
void RBTreeInsertFixUpLeft(struct rbtNode* root, struct rbtNode* z){
    struct rbtNode* y = z->parent->parent->rightChild; //y is initialize
    if(y->color == 'R'){
        z->parent->color = 'B';
        y->color = 'B';
        z->parent->parent->color = 'R';
        z = z->parent->parent;
    }else{
        if(z == z->parent->rightChild){
            z = z->parent;
            TreeLeftRotate(root,z);
        }
        z->parent->color = 'B';
        z->parent->parent->color = 'R';
        TreeRightRotate(root,z->parent->parent);
    }
}


//function for implementing the fixup for the right side, this function is needed for performing the insert fixup
void RBTreeInsertFixUpRight(struct rbtNode* root,struct rbtNode* z){
    struct rbtNode* y = z->parent->parent->leftChild; //y is initialize
    if(y->color == 'R'){
        z->parent->color = 'B';
        y->color = 'B';
        z->parent->parent->color = 'R';
        z = z->parent->parent;
    }else{
        if(z == z->parent->leftChild){
            z = z->parent;
            TreeRightRotate(root,z);
        }
        z->parent->color = 'B';
        z->parent->parent->color = 'R';
        TreeLeftRotate(root,z->parent->parent);
    }
}


//function for performing a fixup of the RBT (necessary for pergorming an insertion)
void RBTreeInsertFixup(struct rbtNode* root, struct rbtNode* z){
    while(z->parent->color == 'R'){
        if(z->parent == z->parent->parent->leftChild){
            RBTreeInsertFixUpLeft(root,z); //calling the function for the left side
        }else{
            RBTreeInsertFixUpRight(root,z); //calling the function for the right side
        }
        
    }        
    root->color = 'B';

}



//Function for inserting a new key in the RBT
void RBTreeInsert(struct rbtNode* root, struct rbtNode* z){
    struct rbtNode* t_nil = TNIL();
    struct rbtNode* y = t_nil;
    struct rbtNode* x = root;

    while(x != t_nil){
        y = x;
        if(z->key < x->key){
            x = x->leftChild ;
        }else{
            x = x->rightChild;
        }
    }
    z->parent = y;
    if(y == t_nil){
        root = z;
    }if(y != t_nil && z->key < y->key){
        y->leftChild = z;
    }if(y != t_nil && z->key >= y->key){
        y->rightChild = z;
    }

    z->leftChild = t_nil;
    z->rightChild = t_nil;
    z->color = 'R';
    RBTreeInsertFixup(root,z);
}


//experimenting with the insert function
/*void insert(struct rbtNode* root, struct rbtNode* z)
{
    z->leftChild = z->rightChild = z->parent = NULL;
 
     //if root is null make z as root
    if (root == NULL)
    {
        z->color = 'B';
        root = z;
    }
    else
    {
        struct rbtNode* y = NULL;
        struct rbtNode* x = root;
 
        // Follow standard BST insert steps to first insert the node
        while (x != NULL)
        {
            y = x;
            if (z->key < x->key)
                x = x->leftChild;
            else
                x = x->rightChild;
        }
        z->parent = y;
        if (z->key > y->key)
            y->rightChild = z;
        else
            y->leftChild = z;
        z->color = 'R';
 
        // call insertFixUp to fix reb-black tree's property if it
        // is voilated due to insertion.
        RBTreeInsertFixup(root,z);
    }
}*/


//Function for searching a key in the RBT
void RBTreeSearch(struct rbtNode* root, int k){
    struct rbtNode* t_nil = TNIL();

    if(root == t_nil || root->key == k){
        return;
    }
    if(k <= root->key){
        RBTreeSearch(root->leftChild,k);
        RBTreeSearch(root->rightChild,k);
    }
}\

//Function for emptying a RBT
void RBTreeDeallocate(struct rbtNode* root){
    if(root == NULL){
        return;
    }
    RBTreeDeallocate(root->leftChild);
    RBTreeDeallocate(root->rightChild);
    free(root);
}

//Function which executes the Single Experiment in regards to the RBT
double SingleExperimentRBT(int max_keys,double max_search,int max_instances){
    double t_tot = 0;
    int i;
    int key;
    double search;

    for(i = 1; i<=max_instances;i++){
        clock_t start_t, end_t;

        srand(0);
        struct rbtNode* root = RootCreator(rand());

        start_t = clock();
        for(key = 1; key <= max_keys;key++){
            RBTreeInsert(root,newNodeRBT(rand())); //inserting the keys
        }
        for(search = 1; search <= max_search; search++){
            RBTreeSearch(root,rand()); //searching the keys
        }
        end_t = clock();
        double t_elapsed = (double)(end_t - start_t); //calculating the time elapsed
        t_tot += t_elapsed;

        //RBTreeDeallocate(&root); //Emptying the RBT

    }
    return t_tot/max_keys;
}

int main(void){
    int min_keys = 100000;
    int max_keys = 1000000;
    int max_instances = 5;
    int percentage_search = 60;
    int keys;
    int seed = 0;
    //setting up the main parameters for the experiments

    for(keys = min_keys; keys <= max_keys; keys += 100000){
        srand(seed);
        double max_search = keys * percentage_search / 100;
        double max_delete = keys - max_search;

        double timeRBT = SingleExperimentRBT(keys,max_search,max_instances);
        printf("Number of keys: %d -- timeRBT: %f\n",keys,timeRBT);

        seed = seed + 1;
    }
}

If perhaps one of you can manage to help me out and find a solution to this horrible nightmare, I would be extremely grateful!

PS: I did use the debugger (gdb) and nada, can't find any solution

Answer 1

These functions here:

void RBTreeInsertFixUpLeft(struct rbtNode* root, struct rbtNode* z){
    struct rbtNode* y = z->parent->parent->rightChild; //y is initialize
    if(y->color == 'R'){

and

void RBTreeInsertFixUpRight(struct rbtNode* root,struct rbtNode* z){
    struct rbtNode* y = z->parent->parent->leftChild; //y is initialize
    if(y->color == 'R'){

should have lines

    if(y != NULL && y->color == 'R'){

because the "Uncle" node can be a empty. I see this problem time and again. Red nodes are always real nodes but the reality needs to be checked. Black nodes can be real or empty (NULL). So all non-real Nodes or empty nodes are always Black.

If you code up RBTreeDeleteFixup, you need to bear in mind that Sibling node's children may not be real (but they will be black).