1

我有来自 Thomas H Cormen 和其他红树和黑树的“算法简介”一书中的伪代码。

插入和插入修复的伪代码位于此处

我在这一行遇到了一个段错误：while(n->parent->color == 'r')在尝试插入“8”时使用以下测试数据的插入修复函数中：

测试数据：

i 5
i 7
i 1
i 8
i 3

我相信这是因为 n 的父级可能不存在？但我不确定如何在不完全搞砸伪代码的情况下适当地更改代码。：

这是我的插入：

void insert_fix(node * n)
{
    node * y;
    if(n->parent)
    {
        while(n->parent->color == 'r')
        {
            if(n->parent == n->parent->parent->left)
            {
                y = n->parent->parent->right;
                if(y->color == 'r')
                {
                    n->parent->color = 'b';
                    y->color = 'b';
                    n->parent->parent->color = 'r';
                    n = n->parent->parent;
                }
                else
                {
                    if(n == n->parent->right)
                    {
                        n = n->parent;
                        rotate_left(n);
                    }
                    n->parent->color = 'b';
                    n->parent->parent->color = 'r';
                }
            }
            else
            {
                y = n->parent->parent->left;
                if(y->color == 'r')
                {
                    n->parent->color = 'b';
                    y->color = 'b';
                    n->parent->parent->color = 'r';
                    n = n->parent->parent;
                }
                else
                {
                    if(n == n->parent->left)
                    {
                        n = n->parent;
                        rotate_right(n);
                    }
                    n->parent->color = 'b';
                    n->parent->parent->color = 'r';
                }
            }
        }
    }
    root->color = 'b';
}

这是我的插入修复：

void insert_fix(node * n)
{
    node * y;
    if(n->parent)
    {
        while(n->parent->color == 'r')
        {
            if(n->parent == n->parent->parent->left)
            {
                y = n->parent->parent->right;
                if(y->color == 'r')
                {
                    n->parent->color = 'b';
                    y->color = 'b';
                    n->parent->parent->color = 'r';
                    n = n->parent->parent;
                }
                else
                {
                    if(n == n->parent->right)
                    {
                        n = n->parent;
                        rotate_left(n);
                    }
                    n->parent->color = 'b';
                    n->parent->parent->color = 'r';
                }
            }
            else
            {
                y = n->parent->parent->left;
                if(y->color == 'r')
                {
                    n->parent->color = 'b';
                    y->color = 'b';
                    n->parent->parent->color = 'r';
                    n = n->parent->parent;
                }
                else
                {
                    if(n == n->parent->left)
                    {
                        n = n->parent;
                        rotate_right(n);
                    }
                    n->parent->color = 'b';
                    n->parent->parent->color = 'r';
                }
            }
        }
    }
    root->color = 'b';
}

*为了清楚起见，我在上面的 while 循环周围添加了额外的 if 语句，这样如果节点是根节点就不会发生任何事情，但是它并没有像我希望的那样解决我的问题。

为了更好地衡量，我根据我在互联网上找到的信息编写了左右旋转功能略有不同，我认为它们写得很好：

void rotate_right(node *n)
{
    node* left = n->left;
    swap_nodes(n, left);
    n->left = left->right;
    if(left->right != NULL)
        left->right->parent = n;
    left->right = n;
    n->parent = left;
}

void rotate_left(node *n)
{
    node* right = n->right;
    swap_nodes(n, right);
    n->right = right->left;
    if(right->left != NULL)
        right->left->parent = n;
    right->left = n;
    n->parent = right;
}

void swap_nodes(node* oldNode, node* newNode)
{
    if(oldNode->parent == NULL)
        root = newNode;
    else
    {
        if(oldNode == oldNode->parent->left)
            oldNode->parent->left = newNode;
        else
            oldNode->parent->right = newNode;
    }

    if(newNode != NULL)
        newNode->parent = oldNode->parent;
}

同样，我觉得我的真实代码准确地遵循了伪代码，但我无法弄清楚我缺少的部分。

让我知道！谢谢！

4

1 回答 1

0

我认为 CLRS 中的 RBT 插入算法存在错误。当 parent 和 uncle 的颜色都是红色时，算法首先将 parent 和 uncle 重新绘制为黑色，然后向上移动，如您的代码中所示n = n->parent->parent。然而，这并不是案件的结束。相反，算法应该在向上移动后递归调用自身。即，以您的代码为例，应该有这样的语句：

insert_fix(n);

后n = n->parent->parent.

如果我错了，请纠正我。顺便说一句，维基百科条目“红黑树”在这种情况下可能会有所帮助。

于 2013-03-08T05:29:30.323 回答