Блог

Вот уже много дней я не могу избавиться от этой проблемы. Я пытаюсь реализовать простое красно-черное дерево (в C) с дополнительной функцией, которая вычисляет время в часах в течение всего периода вставки и поиска в дереве.

Ниже приведен мой код:

 #include lt;stdio.hgt; #include lt;time.hgt; #include lt;stdlib.hgt; #include lt;limits.hgt;  #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-gt;key;  temp-gt;color = 'B';  temp-gt;leftChild = NULL;  temp-gt;rightChild = NULL;  temp-gt;parent = NULL;    return temp;  };  struct rbtNode* RootCreator(int key){  rbtNode *temp = (rbtNode*)malloc(sizeof(rbtNode));  temp-gt;key = key;  temp-gt;color = 'B';  temp-gt;leftChild = NULL;  temp-gt;rightChild = NULL;  temp-gt;parent = NULL;    return temp; };   //function for creating a new node struct rbtNode* newNodeRBT(int key){  rbtNode *temp =(rbtNode*)malloc(sizeof(rbtNode));  temp-gt;key = key;  temp-gt;color = 'R';  temp-gt;leftChild = NULL;  temp-gt;rightChild = NULL;  temp-gt;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-gt;rightChild; //y is initialize  x-gt;rightChild = y-gt;leftChild; //y's left subtree are turning into x's right subtree   if(y-gt;leftChild != t_nil){  y-gt;leftChild-gt;parent = x; //y's left subtree's parent is x  }   y-gt;parent = x-gt;parent; //y's parent is x's parent   if(x-gt;parent == t_nil){  root = y;  }else if (x-gt;parent != t_nil amp;amp; x == x-gt;parent-gt;leftChild){  x-gt;parent-gt;leftChild = y;  }else if(x-gt;parent != t_nil amp;amp; x == x-gt;parent-gt;rightChild){  x-gt;parent-gt;rightChild = y;  }  y-gt;leftChild = x; //x is turning into y's left subtree  x-gt;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-gt;leftChild; //x is initialize  y-gt;leftChild = x-gt;rightChild; //x's right subtree is turning into y's left subtree   if(x-gt;rightChild != t_nil){  x-gt;rightChild-gt;parent = y; //x's right subtree's parent is y  }   x-gt;parent = y-gt;parent; //x's parent is y's parent   if(y-gt;parent == t_nil){  root = x;  }else if (y-gt;parent != t_nil amp;amp; y == y-gt;parent-gt;rightChild){  y-gt;parent-gt;rightChild = x;  }else if(y-gt;parent != t_nil amp;amp; y == y-gt;parent-gt;leftChild){  y-gt;parent-gt;leftChild = x;  }  x-gt;rightChild = y; //y is turning into x's right subtree  y-gt;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-gt;parent-gt;parent-gt;rightChild; //y is initialize  if(y-gt;color == 'R'){  z-gt;parent-gt;color = 'B';  y-gt;color = 'B';  z-gt;parent-gt;parent-gt;color = 'R';  z = z-gt;parent-gt;parent;  }else{  if(z == z-gt;parent-gt;rightChild){  z = z-gt;parent;  TreeLeftRotate(root,z);  }  z-gt;parent-gt;color = 'B';  z-gt;parent-gt;parent-gt;color = 'R';  TreeRightRotate(root,z-gt;parent-gt;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-gt;parent-gt;parent-gt;leftChild; //y is initialize  if(y-gt;color == 'R'){  z-gt;parent-gt;color = 'B';  y-gt;color = 'B';  z-gt;parent-gt;parent-gt;color = 'R';  z = z-gt;parent-gt;parent;  }else{  if(z == z-gt;parent-gt;leftChild){  z = z-gt;parent;  TreeRightRotate(root,z);  }  z-gt;parent-gt;color = 'B';  z-gt;parent-gt;parent-gt;color = 'R';  TreeLeftRotate(root,z-gt;parent-gt;parent);  } }   //function for performing a fixup of the RBT (necessary for pergorming an insertion) void RBTreeInsertFixup(struct rbtNode* root, struct rbtNode* z){  while(z-gt;parent-gt;color == 'R'){  if(z-gt;parent == z-gt;parent-gt;parent-gt;leftChild){  RBTreeInsertFixUpLeft(root,z); //calling the function for the left side  }else{  RBTreeInsertFixUpRight(root,z); //calling the function for the right side  }    }   root-gt;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-gt;key lt; x-gt;key){  x = x-gt;leftChild ;  }else{  x = x-gt;rightChild;  }  }  z-gt;parent = y;  if(y == t_nil){  root = z;  }if(y != t_nil amp;amp; z-gt;key lt; y-gt;key){  y-gt;leftChild = z;  }if(y != t_nil amp;amp; z-gt;key gt;= y-gt;key){  y-gt;rightChild = z;  }   z-gt;leftChild = t_nil;  z-gt;rightChild = t_nil;  z-gt;color = 'R';  RBTreeInsertFixup(root,z); }   //experimenting with the insert function /*void insert(struct rbtNode* root, struct rbtNode* z) {  z-gt;leftChild = z-gt;rightChild = z-gt;parent = NULL;    //if root is null make z as root  if (root == NULL)  {  z-gt;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-gt;key lt; x-gt;key)  x = x-gt;leftChild;  else  x = x-gt;rightChild;  }  z-gt;parent = y;  if (z-gt;key gt; y-gt;key)  y-gt;rightChild = z;  else  y-gt;leftChild = z;  z-gt;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-gt;key == k){  return;  }  if(k lt;= root-gt;key){  RBTreeSearch(root-gt;leftChild,k);  RBTreeSearch(root-gt;rightChild,k);  } }  //Function for emptying a RBT void RBTreeDeallocate(struct rbtNode* root){  if(root == NULL){  return;  }  RBTreeDeallocate(root-gt;leftChild);  RBTreeDeallocate(root-gt;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; ilt;=max_instances;i  ){  clock_t start_t, end_t;   srand(0);  struct rbtNode* root = RootCreator(rand());   start_t = clock();  for(key = 1; key lt;= max_keys;key  ){  RBTreeInsert(root,newNodeRBT(rand())); //inserting the keys  }  for(search = 1; search lt;= 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(amp;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 lt;= 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: %fn",keys,timeRBT);   seed = seed   1;  } }  

Если, возможно, кто-нибудь из вас сумеет помочь мне и найти решение этого ужасного кошмара, я был бы чрезвычайно благодарен!

PS: Я использовал отладчик (gdb) и нада, не могу найти никакого решения