c - 二分木検索からのノードの削除

Question

BST からノードを削除するコードに複数のエラーがあると思います。私は何を理解することはできません！これが私のコードです。前もって感謝します！

void del(int val){
    help = root;
    f = help;
    while (help){
        if(help->data==val) break;
        f  = help;
        if (val > help-> data) help = help->right;
        else help = help->left;
    } if(help->data != val) printf("\nElement not found!");
    else{
        printf("Element found!");
        target = help;
        if(val>f->data){
            if(target->right && !target->left) {f->right = target->right; f = target->right;}
            else {f->right = target->left; f = target->left;}
        } else{
            if(target->right && !target->left) {f->left = target->right; f = target->right;}
            else {f->left = target->left; f = target->left;}
        }
        while(help ->right) help = help->right;
        if(help->left) help = help->left;
        f->right = help;
        free(target);
    }
}

score 0 · Accepted Answer

typedef struct xxx {
        struct xxx *left;
        struct xxx *right;
        int data;
        } ;
#define NULL (void*)0
#define FREE(p) (void)(p)

void treeDeleteNode1 (struct xxx **tree, int data)
{
    struct xxx *del,*sub;

        /* Find the place where node should be */
    for (       ; del = *tree; tree = (data < del->data) ? &del->left : &del->right ) {
        if (del->data == data) break;
        }
        /* not found: nothing to do */
    if ( !*tree) return;

        /* When we get here, `*tree` points to the pointer that points to the node_to_be_deleted
        ** If any of its subtrees is NULL, the other will become the new root
        ** ,replacing the deleted node..
        */
    if ( !del->left) { *tree = del->right; FREE(del); return; }
    if ( !del->right) { *tree = del->left; FREE(del); return; }

        /* Both subtrees non-empty:
        ** Pick one (the left) subchain , save it, and set it to NULL */
    sub = del->left;
    del->left = NULL;

        /* Find leftmost subtree of right subtree of 'tree' */
    for (tree =  &del->right; *tree; tree =  &(*tree)->left) {;}
        /* and put the remainder there */
    *tree = sub;
    FREE(del);
}

次のように呼び出されます。

...
struct xxx *root;
...
treeDeleteNode1( &root, 42);
...

score 0 · Accepted Answer

私が見つけたエラーの 1 つは、ツリーの左側のノードを削除すると、対称ではないため、最後の数行が機能しない可能性があることです。たとえば、ツリーのルートが 6、左の子が 4、右の子が 8 であるとします。ここで、4 を削除します。したがって、最初の while 句でノードを見つけた後、次のようにヒットします。「if (val > f->data){」のelse節。この時点で、f は 6 を指し、target と help は 4 を指します。ここで、f の左を target の右に設定しているため、6 の左は NULL を指し、f 自体は NULL を指します。ここまでは順調ですね！ただし、while ループに入ると、help には適切なノードがないため、help は 6 を指し続けます。最後に、f の適切なノードを作成して (ところで、この時点で f は既に NULL です)、ヘルプとあなたは実際にクラッシュしてしまうでしょう！

while (help->right)
     help = help->right;

if (help->left)
      help = help->left;

f->right = help;

もう 1 つのエラーは、ルートノードを削除してしまう場合に備えて、ルートポインタを更新しないことです。

より簡単なアプローチの 1 つは、これを 3 つのケースに分割することです。3つのケースすべてにコードを提供しています。これら 3 つのケースのそれぞれにサンプルツリーを使用し、それをデバッグ/テストします。

まず、見つかったノード (ファイル while ループが実行しているノード) に子ノードがない場合は、それを削除し、その親を NULL に設定すると完了です。以下は、最初のケースの大まかなカットです。

    /* If the node has no children */
    if (!help->left && !help->right) {
        printf("Deleting a leaf node \n");
        f = help->parent;
        if (f) {
            if (value > f->value)
                f->right = NULL;
            else
                f->left = NULL;
        }
        /* If deleting the root itself */
        if (f->value == root) {
            root = NULL;
        }
        free(help);
        return 0;
    }

次に、見つかったノードに子 (左または右) しかない場合は、それをスプライスして、見つかったノードの子が親ノードの子になります。2 番目のケースは次のとおりです。

    /* If the node has only one child node */
    if ((help->left && !help->right)
        || (!help->left && help->right)) {
        printf("Deleting a node with only one child \n");
        f = help->parent;

        if (help->left)  {
            child_node = help->left;
        } else  {
            child_node = help->right;
        }

        if (f) {
            if (value > f->value) {
                f->right = child_node;
            } else  {
                f->left = child_node;
            }
        } else {
            /* This must be the root */
            root = child_node;
        }
        free(help);
        return 0;
    }

3 番目のケースは注意が必要です。ここでは、見つかったノードに 2 つの子ノードがあります。この場合、ノードの後続ノードを見つけて、見つかったノードの値を後続ノードに置き換えてから、後続ノードを削除する必要があります。これが 3 番目のケースです。

    /* If the node has both children */
    if (help->left && help->right) {
        successor_found = find_successor(help, help->data);
        printf("Deleting a node with both children \n");
        if (successor_found) {
            successor_value = successor_found->value;
            del(successor_found->value);
            help->value = successor_value;
        }
        return 0;
    }

そして、後継者を見つけるためのコードは次のとおりです。

binary_node_t *node find_successor(binary_node_t *node, int value) {

    binary_node_t *node_found;

    if (!node) {return NULL; }

    node_found = node;
    old_data = node->data;

    /* If the node has a right sub-tree, get the min from the right sub-tree */
    if (node->right != NULL) {
        node = node->right;
        while (node) {
            node_found = node;
            node = node->left;
        }
        return node_found;
    }

    /* If no right sub-tree, get the min from one of its ancestors */
    while (node && node->data <= old_data) {
        node = node->parent;
    }
    return (node);
}

c - 二分木検索からのノードの削除

2 に答える 2

Related

Reference