我正在尝试在C中实现红黑树。作为参考,我正在使用CLRS。
但是,当我运行代码时,我收到“分段错误(核心已转储)”错误消息。
我无法弄清楚代码中有什么问题,有人可以告诉我代码中有什么问题吗?
问题似乎出在函数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;
}
}
最佳答案
我写错了代码。再次从头开始编写(使用CLRS)并且这次包括哨点节点之后,一切都很好。
rb_delete_fixup()函数如下。更改位于内部if-else中。同样,我们必须更改rb_insert_fixup的内部if-else。不能从伪代码中编写正确的代码是一种错误。
Node *rb_delete_fixup(Node *tree, Node *tree_nil, Node *x)
{
Node *w;
while ( x != tree && x->color == BLACK )
{
if ( x == x->parent->left )
{
w = x->parent->right;
if ( w->color == RED )
{
w->color = BLACK;
x->parent->color = RED;
tree = left_rotate(tree, tree_nil, x->parent);
w = x->parent->right;
}
if ( w->left->color == BLACK && w->right->color == BLACK )
{
w->color = RED;
x = x->parent;
}
else
{
if ( w->right->color == BLACK )
{
w->left->color = BLACK;
w->color = RED;
tree = right_rotate(tree, tree_nil, w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
tree = left_rotate(tree, tree_nil, x->parent);
x = tree;
}
}
else
{
w = x->parent->left;
if ( w->color == RED )
{
w->color = BLACK;
x->parent->color = RED;
tree = right_rotate(tree, tree_nil, x->parent);
w = x->parent->left;
}
if ( w->left->color == BLACK && w->right->color == BLACK )
{
w->color = RED;
x = x->parent;
}
else
{
if ( w->left->color == BLACK )
{
w->right->color = BLACK;
w->color = RED;
tree = left_rotate(tree, tree_nil, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
tree = right_rotate(tree, tree_nil, x->parent);
x = tree;
}
}
}
x->color = BLACK;
}
关于c - C红黑树,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/46029740/