c - 红黑树插入节点报错

Question

我正在尝试在红黑树中插入节点。函数 rotate_left、rotate_right、insertion 是正确的，但 rb_fixup 似乎是错误的。红色显示为 1，黑色显示为 0。我已经从 CLRS 实现了算法。当插入第三个元素时，它会出现段错误。 rb_fixup 的代码是:

struct node
{
    int data;

    int color;
    struct node *left;
    struct node *right;
    struct node *parent;
}*root;


rb_fixup(struct node *z)
{

    struct node *y;
    y=(struct node *)malloc(sizeof(struct node));
    while(z->parent->color==1)
    {
        if(z->parent==z->parent->parent->left)
        {
            y=z->parent->parent->right;
            if(y->color==1)
            {
                z->parent->color=0;
                y->color=0;
                z->parent->parent->color=1;
                z=z->parent->parent;
            }
            else if(z==z->parent->right)
            {
                z=z->parent;
                rotate_left(z);
            }
            z->parent->color=0;
            z->parent->parent->color=1;
            rotate_right(z->parent->parent);

        }
        else if(z->parent==z->parent->parent->right)
        {
            y=z->parent->parent->left;
            if(y->color==1)
            {
                z->parent->color=0;
                y->color=0;
                z->parent->parent->color=1;
                z=z->parent->parent;
            }
            else if(z->parent->left==z)
            {
                z=z->parent;
                rotate_right(z);
            }
            z->parent->color=0;
            z->parent->parent->color=1;
            rotate_left(z->parent->parent);
        }
    }
    root->color=0;
}

Answer 1

我解决了上面的问题。上面代码的错误在于，如果叔叔是红色的，它会将叔叔和 parent 涂成黑色，将祖 parent 涂成红色，但它会继续执行在每个条件的 else if 之后编写的操作许多条件没有正确完成。最终代码如下所示:-

rb_fixup(struct node *z)
{

    struct node *y;
    y=(struct node *)malloc(sizeof(struct node));
    while(z->parent->color==1 && z->parent!=NULL)
    {
        if(z->parent==z->parent->parent->left)
        {
            if(z->parent->parent->right!=NULL)
            y=z->parent->parent->right;
            if(y->color==1)
            {
                z->parent->color=0;
                y->color=0;
                z->parent->parent->color=1;
                z=z->parent->parent;
            }
            else if(z==z->parent->right)
            {
                z=z->parent;
                rotate_left(z,z->right);
                z->parent->color=0;
                z->parent->parent->color=1;
                rotate_right(z->parent->parent,z->parent);
            }
            else
            {
                z->parent->color=0;
                z->parent->parent->color=1;
                rotate_right(z->parent->parent,z->parent);
            }
        }
        else 
        {
            if(z->parent->parent->left!=NULL)
            {
                y=z->parent->parent->left;
            }           
            if(y->color==1)
            {
                z->parent->color=0;
                y->color=0;
                z->parent->parent->color=1;
                z=z->parent->parent;                
            }
            else if(z==z->parent->left)
            {
                z=z->parent;
                rotate_right(z,z->left);
                z->parent->color=0;
                z->parent->parent->color=1;
                rotate_left(z->parent->parent,z->parent);
            }
            else
            {
                z->parent->color=0;
                z->parent->parent->color=1;
                rotate_left(z->parent->parent,z->parent);
            }
        }
    }
    root->color=0;
}