c - C语言中的红黑树

Question

我正在尝试在 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;
    }
}

Answer 1

我把代码写错了。从头开始再次编写(使用 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;
}