0
我试图在C中实现红黑树。对于参考，我使用的是CLRS。C中的红黑树
但是，当我运行代码时，我得到“分段错误（核心转储）”错误消息。
我无法弄清楚我的代码有什么问题，所以有谁能告诉我我的代码有什么问题？
该问题似乎在功能rb_insert_fixup()，但我不知道它有什么问题。
#include <stdio.h>
#include <stdlib.h>
//constants
#define RED 0
#define BLACK 1
struct node
{
int key;
struct node *left;
struct node *right;
struct node *parent;
int color;
};
struct node *rb_insert(struct node *tree, struct node *z);
struct node *rb_insert_fixup(struct node *tree, struct node *z);
struct node *left_rotate(struct node *t, struct node *x);
struct node *right_rotate(struct node *t, struct node *x);
struct node *create_node(int key);
int main()
{
struct node *tree = NULL;
struct node *new;
new = create_node(5);
tree = rb_insert(tree, new);
new = create_node(15);
tree = rb_insert(tree, new);
new = create_node(4);
tree = rb_insert(tree, new);
new = create_node(14);
tree = rb_insert(tree, new);
printf("inserting 14\n");
printf("%d %d\n%d %d\n", (tree->left)->key, (tree->left)->color, ((tree->right)->left)->key, ((tree->right)->left)->color);
return 0;
}
struct node *rb_insert_fixup(struct node *tree, struct node *z)
{
struct node *y = NULL;
printf("fixup \n");
while (z->parent != NULL && (z->parent)->color == RED)
{
printf("while\n");
if ((z->parent)->parent != NULL && printf("if condition %d\n", (((z->parent)->parent)->left)->color) && z->parent == ((z->parent)->parent)->left)
{
printf("start if\n");
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;
tree = left_rotate(tree, z);
}
(z->parent)->color = BLACK;
((z->parent)->parent)->color = RED;
tree = right_rotate(tree, ((z->parent)->parent));
printf("End if\n");
}
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;
tree = right_rotate(tree, z);
}
(z->parent)->color = BLACK;
((z->parent)->parent)->color = RED;
tree = left_rotate(tree, ((z->parent)->parent));
printf("End else\n");
}
printf("End while\n");
}
tree->color = BLACK;
return tree;
}
struct node *rb_insert(struct node *tree, struct node *z)
{
struct node *y = NULL;
struct node *x = tree;
while (x != NULL)
{
y = x;
if (z->key < x->key)
{
x = x->left;
}
else
{
x = x->right;
}
}
z->parent = y;
if (y == NULL)
{
tree = z;
}
else if (z->key < y->key)
{
y->left = z;
}
else
{
y->right = z;
}
z->left = NULL;
z->right = NULL;
z->color = RED;
tree = rb_insert_fixup(tree, z);
//printf("bye insert\n");
return tree;
}
struct node *right_rotate(struct node *t, struct node *x)
{
struct node *y = x->left;
x->left = y->right;
if (y->right != NULL)
{
(y->right)->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL)
{
t = y;
}
else if (x == (x->parent)->left)
{
(x->parent)->left = y;
}
else
{
(x->parent)->right = y;
}
y->right = x;
x->parent = y;
return t;
}
struct node *left_rotate(struct node *t, struct node *x)
{
struct node *y = x->right;
x->right = y->left;
if (y->left != NULL)
{
(y->left)->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL)
{
t = y;
}
else if (x == (x->parent)->left)
{
(x->parent)->left = y;
}
else
{
(x->parent)->right = y;
}
y->left = x;
x->parent = y;
return t;
}
struct node *create_node(int key)
{
struct node *new = malloc(sizeof(struct node));
if (new == NULL)
{
fprintf(stderr, "Malloc failed to create a new node\n");
exit(EXIT_FAILURE);
}
else
{
new->key = key;
new->left = NULL;
new->right = NULL;
new->parent = NULL;
new->color = BLACK;
}
}
1）您还没有用'create_node'返回一个值。在函数结束时你需要'return new;'。 – BLUEPIXY
打开你的编译器警告并将它们视为错误。问题BLUEPIXY指出，例如，*“main.c：260：1：控制可能会到达非空函数的结尾”* – WhozCraig
2）在'rb_insert_fixup'：'if（（z-> parent） - > parent ！= NULL && ...）{...} else {y =（（z-> parent） - > parent） - > left;'：if-conditional-expression成为false因为（z-> parent） - >父''是'NULL'，当执行else-block时，'y =（（z->父） - >父） - >左;'可能'y = NULL-> left; NULL'解除引用。 – BLUEPIXY