1

赤黒の木のコードをオンラインで見つけたので、それを実装しようとしています。

assert元のコードがここに配置されている関数を使用したくない

n->color = child->color;削除修正の直前に回線でセグ フォールトが発生しています。デバッグ後、このケースでは子が存在しないことがわかりました。そのため、元のコードに assert ステートメントが含まれている理由がわかりました。子が処理される場所から下に向かってすべての if 句を追加して、適切だと思うものを追加することにしました。

ただし、子が存在しない場合はループに入らないため、プログラムは実際には削除しません。試行錯誤の末、assert ステートメントを適切に置き換えるために if 句を閉じる場所をまだ見つけることができません。

あなたのアイデアを教えてください！

これは、アサートなしの「翻訳された」コードで、代わりに if ステートメントを使用しています。

void delete_node(int key)
{
    node* child;
    node* n ;

   n = searchTree(key);

    if(n == NULL)return;

    if(n->left != NULL && n->right != NULL)
    {
        node* pred = n->left;
        while(pred->right != NULL)
            pred = pred->right;

        n->value = pred->value;
        n = pred;
    }
if(n->right != NULL || n->left != NULL){

    child = n->right == NULL ? n->left : n->right;
    if(n->color == 'b')
    {
        n->color = child->color;
        delete_fix1(n);
    }

    swap_nodes(n, child);
    if(n->parent == NULL && child != NULL)
        child->color = 'b';
    free(n);

}

}

テスト データ (削除しようとすると Seg Fault が発生する 4): i は挿入を表します (私が知る限り、挿入は問題なく行われます) d は削除を表します

i 7
i 8
i 1
d 8
i 4
i 10
d 4
i 11
4

1 に答える 1

1

これ：

assert(n->left == NULL || n->right == NULL)

これにはほど遠い：

if (n->right != NULL || n->left != NULL)

翻訳を再確認してください。アサートは、そのうちの 1 つが NULLでなければならないことを示しています。いずれかがNULLでない場合、if-expr は true になります。アサートが失敗する場合、両方が非 null の場合、if-expr はパスします。同様に、アサートはパスしますが、両方が NULL の場合、if-expr は失敗します。

このようなことをするときは近道をしないでください。初め。追加されたチェックに関係なく、アサートを保持します。次に、起動して機能するまで、救済条件の if (expr): または (!(expr)) に assert 句をそのままコピーします。

逐語的なチェック:

assert(n->left == NULL || n->right == NULL)
if (n->left == NULL || n->right == NULL)...

救済チェック:

assert(n->left == NULL || n->right == NULL)
if (!(n->left == NULL || n->right == NULL))
    bailout loud.

EDIT統合された if-expr を使用したリンクされたコードの翻訳

void rbtree_delete(rbtree t, void* key, compare_func compare)
{
    node child;
    node n = lookup_node(t, key, compare);
    if (n == NULL) return;  /* Key not found, do nothing */
    if (n->left != NULL && n->right != NULL) {
        /* Copy key/value from predecessor and then delete it instead */
        node pred = maximum_node(n->left);
        n->key   = pred->key;
        n->value = pred->value;
        n = pred;
    }

    assert(n->left == NULL || n->right == NULL);
    if (n->left == NULL || n->right == NULL) // << note: SAME as above
    {
        child = n->right == NULL ? n->left  : n->right;
        if (node_color(n) == BLACK) {
            n->color = node_color(child);
            delete_case1(t, n);
        }
        replace_node(t, n, child);
        if (n->parent == NULL && child != NULL)
            child->color = BLACK;
        free(n);
    }

    verify_properties(t);
}
于 2012-11-29T04:47:49.047 に答える