c - 伪代码中的红黑树插入和修复有问题

Question

我有 Thomas H Cormen 和其他人写的“算法导论”一书中的伪代码，用于红树和黑树。

插入和插入修复的伪代码位于here

我在这一行遇到段错误: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 语句，这样如果节点是根节点就不会发生任何事情，但是它并没有像我希望的那样解决我的问题。

根据我在 Internet 上找到的信息，我编写的向右旋转和向左旋转功能有些不同，我认为它们写得很好:

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;
}

同样，我觉得我的真实代码准确地遵循了伪代码，但我无法找出我遗漏的部分。

告诉我!谢谢!

Answer 1

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

insert_fix(n);

在 n = n->parent->parent. 之后

如有错误请指正。顺便说一句，the wikipedia entry "red-black tree"在这种情况下可能会有所帮助。