我正在尝试在C中构建一个简单的红黑树。不幸的是,我遇到了无法确定如何修复的分段错误。我已在下面添加了代码,并标记为发生故障的行。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define RED 1
#define BLACK 0
typedef struct RBNode {
char key[50];
int color;
struct RBNode *left;
struct RBNode *right;
struct RBNode *parent;
} RBNode;
typedef struct RBTree {
struct RBNode *root;
struct RBNode *nil;
} RBTree;
void inorderPrint(RBTree*, RBNode*);
void insertRB(RBTree*, RBNode*);
void insertRBFixup(RBTree*, RBNode*);
void leftRotate(RBTree*, RBNode*);
void rightRotate(RBTree*, RBNode*);
int count;
int main (int argc, char* argv[]) {
RBTree *tree = malloc(sizeof(RBTree));
tree->nil = malloc(sizeof(RBNode));
tree->nil->color = BLACK;
tree->root = NULL;
tree->nil->left = tree->root;
tree->nil->right = tree->root;
RBNode *curr = NULL;
curr = malloc(sizeof(RBNode));
strcpy(curr->key, "CAT");
insertRB(tree, curr);
strcpy(curr->key, "HAT");
insertRB(tree, curr);
strcpy(curr->key, "BIT");
insertRB(tree, curr);
strcpy(curr->key, "CAR");
insertRB(tree, curr);
strcpy(curr->key, "MAP");
insertRB(tree, curr);
inorderPrint(tree, tree->root);
return 1;
}
void inorderPrint(RBTree* tree, RBNode *node) {
if ((node != NULL) && (node != tree->nil)) {
inorderPrint(tree, node->left);
printf("%s\n", node->key);
inorderPrint(tree, node->right);
}
}
void leftRotate(RBTree *tree, RBNode *x) {
struct RBNode *y = NULL;
y = x->right;
x->right = y->left;
if (y->left != tree->nil) {
y->left->parent = x; //Segmentation fault occurs here
}
y->parent = x->parent;
if (x->parent == tree->nil) {
tree->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void rightRotate(RBTree *tree, RBNode *x) {
RBNode *y = x->left;
x->left = y->right;
if (y->right != tree->nil) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == tree->nil) {
tree->root = y;
} else if (x == x->parent->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
void insertRB(RBTree *tree, RBNode *z) {
RBNode *y = tree->nil;
RBNode *x = tree->root;
while ((x != tree->nil) && (x != NULL)) {
y = x;
if (strcmp(z->key, x->key) < 0) {
x = x->left;
} else {
x = x->right;
}
}
z->parent = y;
if (y == tree->nil) {
tree->root = z;
} else if (strcmp(z->key, y->key) < 0) {
y->left = z;
} else {
y->right = z;
}
z->left = tree->nil;
z->right = tree->nil;
z->color = RED;
insertRBFixup(tree, z);
}
void insertRBFixup(RBTree *tree, RBNode *z) {
RBNode *y = NULL;
while (z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
y = z->parent->parent->right;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else if (z == z->parent->right) {
z = z->parent;
leftRotate(tree, z);
} else {
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(tree, z->parent->parent);
}
} else {
y = z->parent->parent->left;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else if (z == z->parent->left) {
z = z->parent;
rightRotate(tree, z);
} else {
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(tree, z->parent->parent);
}
}
}
tree->root->color = BLACK;
}
我认为这可能与我在main()中初始化红黑树的方式有关,但是我不确定,我尝试了许多其他方式对其进行初始化。
你们中有人知道我要去哪里吗?
最佳答案
在
if (y->left != tree->nil) {
y->left->parent = x; //Segmentation fault occurs here
}
y-> left可以为NULL。
leftRotate需要检查NULL指针
关于c - 简单的红黑树中的分割错误,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/32916423/