1

Thomas H Cormen の本「Introduction to Algorithms」などの赤と黒の木の疑似コードがあります。

挿入と挿入修正の疑似コードはここにあります

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 挿入アルゴリズムにバグがあると思います。親と叔父の両方の色が赤の場合、アルゴリズムは最初に親と叔父を黒に再描画し、コードのように上に移動しますn = n->parent->parent。しかし、それはそのケースの終わりではありません。代わりに、アルゴリズムは上に移動した後に再帰的にそれ自体を呼び出す必要があります。つまり、コードを例にとると、次のようなステートメントがあるはずです。

insert_fix(n);

後n = n->parent->parent.

間違っている場合は修正してください。ところで、この場合、ウィキペディアのエントリ「赤黒の木」が役立つ場合があります。

于 2013-03-08T05:29:30.323 に答える