c-分割错误-红黑树

Question

我已经很多天无法摆脱这个问题了。我试图用一个额外的函数来实现一个简单的红黑树(在C中(，该函数计算在树中插入和搜索的整个时间段内的时钟时间。

Bellow是我的代码：

#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: %fn",keys,timeRBT);
seed = seed + 1;
}
}

如果你们中的一个人能帮助我，找到解决这场可怕噩梦的办法，我将不胜感激！

PS：我确实使用了调试器(gdb(和nada，找不到任何解决方案

Answer 1

此处的这些函数：

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

和

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

应该有线路

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

因为"；叔叔"节点可以为空。我一次又一次地看到这个问题。红色节点总是真实的节点，但需要检查真实性。黑色节点可以是实节点，也可以是空节点(NULL(。所以所有非实节点或空节点都是黑色的。

如果您对RBTreeDelteFixup进行编码，您需要记住，Sibling节点的子节点可能不是真实的(但它们将是黑色的(。