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