Красное Черное Дерево в С
Я пытаюсь реализовать красное черное дерево в 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;
}
}
1 ответ
Я написал код неправильно. После того, как мы снова написали его с нуля (с использованием CLRS) и включили дозорный узел, все в порядке. Функция rb_delete_fixup() работает следующим образом. Изменения во внутреннем if-else. Точно так же мы должны изменить внутренний if-else rb_insert_fixup. Было ошибкой не писать правильный код из псевдокода.
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;
}