I am currently trying to implement a program that evaluates the computing time of my RBT(red black tree):
#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 rbtNode T_Nil_rbtNode; //defining the T_Nil node
rbtNode* t_nil = &T_Nil_rbtNode; //using it as the sentinel
//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* 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{
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* 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{
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* 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);
}
//Function for searching a key in the RBT
void RBTreeSearch(struct rbtNode* root, int k){
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 = newNodeRBT(rand()); //initialize the root
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 = (double)keys * (double)percentage_search / 100.0;
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;
}
}
For some reason, I do receive the segmentation fault message as soon as I launch it :( My hypothesis is that it happens whenever the program tries to enter in the function "SingleExperimentRBT".
Where and why does this happen?
