我在构建红黑树时遇到了问题。 insertFixUp等过程中出现分段错误。我不知道该怎么办。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct tree_node {
int key;
int color;
struct tree_node *parent;
struct tree_node *left_child;
struct tree_node *right_child;
};
struct tree {
int cardinality;
struct tree_node *root;
struct tree_node *Nil;
};
struct tree_node *getNewNode (int keys){
struct tree_node* newNode = (struct tree_node*) malloc(sizeof(struct tree_node));
newNode-> key = keys;
newNode-> color = 0;
newNode-> parent = NULL;
newNode-> right_child = NULL;
newNode-> left_child = NULL;
return newNode;
}
void TreeLeftRotate(struct tree *T, struct tree_node *x) {
struct tree_node *y = x->right_child;
x->right_child = y->left_child;
if (y->left_child != T->Nil) {
y->left_child->parent = x;
}
if (x->parent == T->Nil) {
T->root = y;
}
else if (x == x->parent->left_child) {
x->parent->left_child = y;
}
else {
x->parent->right_child = y;
}
y->left_child = x;
x->parent = y;
}
struct tree_node* BSTTreeMinimum(struct tree_node *x){
if(x->left_child== NULL){
return x;}
else{
return BSTTreeMinimum(x->left_child);}
};
struct tree_node *BSTTreeSearch(struct tree_node *x, int k){
if ((x==NULL)||(x->key=k)){
return x;
}
if(k<=x->key){
return BSTTreeSearch(x->left_child, k);
}
else {
return BSTTreeSearch(x->right_child, k);
}
}
void BSTTreeInsert(struct tree *T, struct tree_node *z) {
struct tree_node *x = NULL;
struct tree_node *y = NULL;
x = T->root;
while (x!=NULL){
y=x;
if(z->key <= x->key){
x=x->left_child;
}
else {
x=x->right_child;
}
}
z->parent =y;
if(y==NULL){
T->root = z;
}
if((y!=NULL)&&(z->key <= y->key)) {
y->left_child = z;
}
if((y!=NULL)&&(z->key > y->key)) {
y->right_child = z;
}
}
void BSTTreeTransplant(struct tree *T, struct tree_node *u, struct tree_node *v){
if (u->parent==NULL){
T->root = v;
}
if((u->parent != NULL)&&(u=u->parent->left_child)){
T->root = v;
}
if((u->parent!=NULL)&&(u=u->parent->right_child)){
u->parent->right_child=v;
}
if(v!=NULL){
v->parent = u->parent;
}
}
void BSTTreeDelete(struct tree *T, struct tree_node *z){
struct tree_node *y = NULL;
if (z->left_child == NULL){
BSTTreeTransplant(T,z,z->right_child);
}
if((z->left_child != NULL) && (z->right_child == NULL)){
BSTTreeTransplant(T,z,z->left_child);
}
if((z->left_child != NULL)&&(z->right_child != NULL)){
y=BSTTreeMinimum(z->right_child);
if (y->parent != z){
BSTTreeTransplant(T,y,y->right_child);
y->right_child = z->right_child;
y->right_child->parent =y;
}
BSTTreeTransplant(T,z,y);
y->left_child = z->left_child;
y->left_child->parent = y;
}
}
void TreeRightRotate(struct tree *T, struct tree_node *x) {
struct tree_node *y = x->left_child;
x->left_child = y->right_child;
if (y->right_child != T->Nil) {
y->right_child->parent = x;
}
if (x->parent == T->Nil) {
T->root = y;
}
else if (x == x->parent->right_child) {
x->parent->right_child = y;
}
else {
x->parent->left_child = y;
}
y->right_child = x;
x->parent = y;
}
void RBTreeInsertFixUpLeft(struct tree*T, struct tree_node *z){
struct tree_node *y = z->parent->parent->right_child;
if (y->color == 1) {
z->parent->color = 0;
y->color = 0;
z->parent->parent->color=1;
z=z->parent->parent;
}
else{
if (z==(z->parent->right_child)){
z=z->parent;
TreeLeftRotate(T,z);
}
z->parent->color = 0;
z->parent->parent->color=1;
TreeRightRotate(T,z->parent->parent);
};
};
void RBTreeInsertFixUpRight(struct tree*T, struct tree_node *z){
struct tree_node *y = z->parent->parent->left_child;
if (y->color == 1) {
z->parent->color = 0;
y->color = 0;
z->parent->parent->color=1;
z=z->parent->parent;
}
else{
if (z==z->parent->left_child){
z=z->parent;
TreeRightRotate(T,z);
}
z->parent->color = 0;
z->parent->parent->color=1;
TreeLeftRotate(T,z->parent->parent);
};
};
void RBTreeInsertFixup(struct tree *T, struct tree_node *z){
while (z->parent->color = 1){ //segmentation fault
if(z->parent == z->parent->parent->left_child){
RBTreeInsertFixUpLeft(T,z);
}
else {
RBTreeInsertFixUpRight(T,z);
}
}
T->root->color=0;
};
void RBTreeInsert(struct tree *T, struct tree_node *z) {
struct tree_node *y = T->Nil;
struct tree_node *x = T->root;
while (x!=T->Nil){
y=x;
if (z->key < x->key) {
x=x->left_child;
}
else {
x=x->right_child;
}
}
z->parent = malloc(sizeof(struct tree_node));
z->parent = y;
if (y==T->Nil){
T->root = z;
}
if((y!=T->Nil)&&(z->key < y->key)){
y->left_child=z;
}
if ((y!=T->Nil)&&(z->key >= y->key)){
y->right_child = z;
}
z->left_child = T->Nil;
z->right_child = T->Nil;
z->color = 1;
RBTreeInsertFixup(T,z);
};
void RBTransplant(struct tree *T, struct tree_node *u, struct tree_node *v){
if (u->parent == T->Nil) {
T->root = v;
}
else if (u==u->parent->left_child){
u->parent->left_child = v;
}
else {
u->parent->right_child=v;
}
v->parent = u->parent;
};
void RBDeleteFixup(struct tree *T, struct tree_node *x){
if (x == x->parent->left_child){
struct tree_node *w = x->parent->right_child;
if (w->color == 1) {
w->color = 0;
x->parent->color = 1;
TreeLeftRotate(T,x->parent);
w=x->parent->right_child;
}
if (w->left_child->color == 0 && w->right_child->color == 0){
w->color = 1;
x = x->parent;
}
else if (w->right_child->color == 0){
w->left_child->color = 0;
w->color = 1;
TreeRightRotate(T,w);
w = x->parent->right_child;
}
w->color = x->parent->color;
x->parent->color = 0;
w->right_child->color = 0;
TreeLeftRotate(T,x->parent);
x=T->root;
}
else {
struct tree_node *w = x->parent->left_child;
if (w->color == 1) {
w->color = 0;
x->parent->color = 1;
TreeRightRotate(T,x->parent);
w=x->parent->left_child;
}
if (w->right_child->color == 0 && w->left_child->color == 0){
w->color = 1;
x = x->parent;
}
else if (w->left_child->color == 0){
w->right_child->color = 0;
w->color = 1;
TreeLeftRotate(T,w);
w = x->parent->left_child;
}
w->color = x->parent->color;
x->parent->color = 0;
w->left_child->color = 0;
TreeRightRotate(T,x->parent);
x=T->root;
}
}
void RBDelete(struct tree *T, struct tree_node *z) {
struct tree_node *x = NULL;
struct tree_node *y = z;
int y_original_color = y->color;
if (z->left_child == T->Nil){
x = z->right_child;
RBTransplant(T,z,z->right_child);
}
else if(z->right_child == T->Nil){
x = z->left_child;
RBTransplant(T,z,z->left_child);
}
else {
y=BSTTreeMinimum(z->right_child);
y_original_color = y->color;
x = y->right_child;
if (y->parent == z){
x->parent = y;
}
else {
RBTransplant(T,y,y->right_child);
y->right_child = z->right_child;
y->right_child->parent = y;
}
RBTransplant(T,z,y);
y->left_child = z->left_child;
y->left_child->parent = y;
y->color = z->color;
}
if (y_original_color == 0) {
RBDeleteFixup(T, x);
}
}
double SingleExperimentBST (int max_keys, int max_search, int max_delete, int max_instances) {
int t_tot = 0;
int t_elapsed = 0;
clock_t t_start = 0, t_final = 0 ;
int A[max_keys];
int B[max_search];
int C[max_delete];
struct tree_node *z =NULL;
z = malloc(sizeof(struct tree_node));
struct nodo *x =NULL;
x = malloc(sizeof(struct tree_node));
for (int instance= 1; instance <= max_instances; instance++){
for (int j= 0; j < max_keys; j++){
A[j] = 1 + rand() % 100; }
struct tree *T= NULL;
T=malloc(sizeof(struct tree));
t_start = clock();
for (int key =1; key<= max_keys; key++){
struct tree_node* z = getNewNode(A[key]);
z->parent = malloc(sizeof(struct tree_node));
z->parent = getNewNode(A[key]);
BSTTreeInsert(T, z);
}
for (int key = 1; key<= max_search; key++){
B[key] = 1 + rand() % 100;
int k= B[key];
struct tree_node *x = T->root;
BSTTreeSearch(x, k) ;
}
for (int key = 1; key<= max_delete; key++){
C[key] = 1 + rand() % 100;
struct tree_node* z1 = getNewNode(C[key]);
BSTTreeDelete(T, z1) ;
}
t_final = clock();
t_elapsed = t_final - t_start;
t_tot = t_tot + t_elapsed;
T->root =NULL;
}
t_final= t_tot / max_keys;
return t_final;
}
double SingleExperimentRBT (int max_keys, int max_search, int max_delete, int max_instances){
int t_tot = 0;
int t_elapsed =0;
clock_t t_start = 0, t_end = 0 ;
int A[max_keys];
int B[max_search];
int C[max_delete];
struct tree_node *z =NULL;
z = malloc(sizeof(struct tree_node));
struct tree_node *x =NULL;
x = malloc(sizeof(struct tree_node));
for (int instance = 1; instance <=max_instances; instance++){
struct tree *T= NULL;
T=malloc(sizeof(struct tree));
for (int j= 0; j < max_keys; j++){
A[j] = 1 + rand() % 100;
}
t_start = clock();
for (int key=1; key<=max_keys; key++) {
struct tree_node *z = getNewNode(A[key]);
RBTreeInsert(T, z);
}
for (int key = 1; key<= max_search; key++){
B[key] = 1 + rand() % 100;
int k= B[key];
struct tree_node *x = T->root;
BSTTreeSearch(x, k) ;
}
for (int key = 1; key<= max_delete; key++){
C[key] = 1 + rand() % 100;
struct tree_node* z1 = getNewNode(C[key]);
RBDelete(T, z1) ;
}
t_end = clock();
t_elapsed = t_end + t_elapsed;
t_tot = t_tot + t_elapsed;
T->root = NULL;
}
return t_tot/max_keys;
}
void Experiment(int min_keys, int max_keys){
time_t t;
int step = 10;
int max_instances = 5;
int percentage_search = 60;
for (int keys = min_keys; keys<=max_keys; keys+step){
srand((unsigned) time(&t));
double max_search = keys*percentage_search/100;
double max_delete = keys - max_search;
double timeBST =SingleExperimentBST(keys, max_search, max_delete, max_instances);
srand((unsigned) time(&t));
double timeRBT = SingleExperimentRBT(keys, max_search, max_delete, max_instances);
printf("%f\t\t\t%f\n", timeBST, timeRBT);
t = t + 1;
}
}
int main() {
int min_key = 10;
int max_key = 150;
Experiment(min_key, max_key);
return 0;
}
此代码应该计算 RB Tree 上的插入、删除、研究操作的时间，但它不打印任何内容。代码相当复杂，如果还有其他错误，请告诉我。编译期间它不显示任何内容。调试时出现分段错误。
while (z->parent->color = 1){ //segmentation fault
这是作业
===此代码有错误
void RBTreeInsertFixUpLeft(struct tree*T, struct tree_node *z){
struct tree_node *y = z->parent->parent->right_child;
if (y->color == 1) {
有可能刚插入一个节点时，父节点存在，但叔节点可能不存在。它可能为 NULL。所以 y 可能为 NULL 但是如果为 NULL，则节点的“颜色”为黑色，如果为非 NULL，则节点->颜色 您应该编写一个返回节点颜色的内联函数 bool IsBlack(const tree_node *curr) { return (curr == NULL || curr->color == 0); } 并使用它。
请注意，删除修正也会发生相同的情况。 如果删除一个叶子黑色节点并且它有父节点，那么兄弟节点存在并且必须是黑色的，它是一个真正的节点。但兄弟姐妹的孩子可能不存在，但他们应该被视为黑人。您的删除代码必须考虑到这一点。