1

RBT (Cormen に基づく) の削除機能を実装しました。動作しているように見えますが、事前注文で削除 + ツリーの印刷をテストすると、間違った答えが返されます。何が問題なのかを数時間調べましたが、何も見つかりませんでした...

予約注文でツリーを印刷する機能は次のとおりです。

void print_out(rbt_node *root, rbt_node *NIL)
{
    if(root != NIL)
    {
        printf("%d %s ", root->key, root->data.c_str());
        if(root->color == BLACK)
            printf("black ");
        else
            printf("red ");
        if(root->parent != NIL)
            printf("%d ",root->parent->key);
        else
            printf("- ");
        if(root->left != NIL)
            printf("%d ",root->left->key);
        else
            printf("- ");
        if(root->right != NIL)
            printf("%d ",root->right->key);
        else
            printf("- ");
        printf("\n");

        print_out(root->left, NIL);
        if(root->right != NIL)
        {
            print_out(root->right, NIL);
        }
    }
}

削除する重要な残りの部分は次のとおりです。

rbt_node *NIL = new rbt_node;
NIL->color = BLACK;
NIL->left = NIL->parent = NIL->right = NIL;

rbt_node *tree_minimum(rbt_node *node, rbt_node *NIL)
{
    while(node->left != NIL)
        node = node->left;

    return node;
}

rbt_node *tree_succesor(rbt_node *node, rbt_node *NIL)
{
    if(node->right != NIL)
        return tree_minimum(node->right, NIL);

    rbt_node *helper = node->parent;
    while(helper != NIL && node == helper->right)
    {
        node = helper;
        helper = helper->parent;
    }

    return helper;
}

void delete_fixup(rbt_node *&root, rbt_node *&target, rbt_node *NIL)
{
    rbt_node *helper = NIL;
    while(target != root && target->color == BLACK)
    {
        if(target == target->parent->left)
        {
            helper = target->parent->right;
            if(helper->color == RED)
            {
                helper->color = BLACK;
                target->parent->color = RED;
                left_rotate(root, target->parent, NIL);
                helper = target->parent->right;
            }
            if(helper->left->color == BLACK && helper->right->color == BLACK)
            {
                helper->color = RED;
                target = target->parent;
            }
            else if(helper->right->color== BLACK)
            {
                helper->left->color = BLACK;
                helper->color = RED;
                right_rotate(root, helper, NIL);
                helper = target->parent->right;
            }
            else
            {
                helper->color = target->parent->color;
                target->parent->color = BLACK;
                helper->right->color = BLACK;
                left_rotate(root, target->parent, NIL);
                target = root;
            }
        }
        else
        {
            helper = target->parent->left;
            if(helper->color == RED)
            {
                helper->color = BLACK;
                target->parent->color = RED;
                right_rotate(root, target->parent, NIL);
                helper = target->parent->left;
            }
            if(helper->right->color == BLACK && helper->left->color == BLACK)
            {
                helper->color = RED;
                target = target->parent;
            }
            else if(helper->left->color== BLACK)
            {
                helper->right->color = BLACK;
                helper->color = RED;
                left_rotate(root, helper, NIL);
                helper = target->parent->left;
            }
            else
            {
                helper->color = target->parent->color;
                target->parent->color = BLACK;
                helper->left->color = BLACK;
                right_rotate(root, target->parent, NIL);
                target = root;
            }
        }
    }

    target->color = BLACK;
}

void rbt_delete(rbt_node *&root, int key, rbt_node *NIL)
{
    rbt_node *victim = to_delete(root, key, NIL);
    if(victim != NIL)
    {
        rbt_node *help_one = NIL;
        rbt_node *help_two = NIL;
        if(victim->left == NIL || victim->right == NIL)
            help_one = victim;
        else
            help_one = tree_succesor(victim, NIL);

        if(help_one->left != NIL)
            help_two = help_one->left;
        else
            help_two = help_one->right;

        help_two->parent = help_one->parent;

        if(help_one->parent == NIL)
            root = help_two;
        else if(help_one == help_one->parent->left)
            help_one->parent->left = help_two;
        else
            help_two->parent->right = help_two;

        if(help_one != victim)
        {
            victim->key = help_one->key;
            victim->data = help_one->data;
        }

        if(help_one->color == BLACK)
            delete_fixup(root, help_two, NIL);
    }

    root->color = BLACK;
}
4

1 に答える 1

1

少なくとも IMO では、実際には正常にprint_out機能していません。特定の問題は、子ノードのデータを (直接) 印刷しようとしていることです。

二分木 (あらゆる種類 -- アンバランス、AVL、RB など) を扱っている場合、トラバーサルは通常、おおよそ次のようになります。

void print_out(node *current_node) { 
    if current_node != NIL {
        show_data(current_node);

        print_out(current_node->left);
        print_out(current_node->right);
   }
}

そのまま、それは予約注文です。post-order または inorder はprint_data、 の再帰呼び出しと比較して再配置するだけの問題ですprint_out(post-order の場合はそれらの後にあり、inorder の場合はそれらの間です)。

ただし、特に print_out は、再帰呼び出しでパラメーターとして渡す以外に、左または右のサブツリーとは関係があってはなりません。また、通常はそれらが NIL/NULL かどうかもチェックしないでください。再帰呼び出しを行い、再帰呼び出しのif (current_node != NIL)ハンドルでリーフ ノードにヒットした可能性を処理する必要があります。

私を怠け者と呼んでください。しかし、それは、私が探している問題の種類について少なくとも何らかのガイダンスがなくても、また少なくともそれが適切な場所であるという合理的な保証なしに、私が喜んで調査するのと同じくらいです。たとえば、いくつかのノードを挿入し、期待される構造を取得して、ノードを削除したときに何が問題になるかを示すことができれば、役に立ちます。ノードはまだありますか？他のノードが失われていますか? すべてのノードは正しいですが、バランスが間違っていますか? もしそうなら、バランスに何が問題になっていますか？

于 2011-05-11T16:30:36.200 に答える