0

私は、(理論的には) 3 つのすべてのケースを処理する必要があるバイナリ ツリー内のノードを削除する関数を C で実装しようとしています。

  • ノードは葉です
  • ノードには子が 1 つあります
  • ノードには 2 つの子があります

ケースごとに個別にチェックせずに、削除機能全体を処理する方法はありますか? 以下のコメンターが指摘したように、私は多くのケースをチェックしており、1 つの基本的なケースをチェックすることで、問題全体を再帰的に解決できる可能性があります。

親を持つツリー内のノードを削除し、それ自体が 2 つの子ノードの親である場合に特に興味があります。

以下の両方の回答は役に立ちましたが、問題全体に対処しているとは思いません。

ここに私が持っているものがあります:

typedef struct Node
{
    int key;
    int data;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node;

/* functions that take care of inserting and finding a node and also traversing and freeing the tree */
...

void delete(Node *root, int key)
{
    Node *target = find(root, key); // find will return the node to be deleted

    Node *parent = target->parent; // parent of node to be deleted

    // no children
    if (target->left == NULL && target->right == NULL)
    {
        // is it a right child
        if (target->key > parent->key)
            parent->right = NULL;
        // must be a left child
        else
            parent->left = NULL;

        free(target);
    }

    // one child
    else if ((target->left == NULL && target->right != NULL) || (target->left != NULL && target->right == NULL))
    {
        // here we swap the target and the child of that target, then delete the target
        Node *child = (target->left == NULL) ? target->right : target->left;
        child->parent = parent;
        if (parent->left == target) parent->left = child;
        else if (parent->right == target) parent->right = child;
        free(target);
    }
    // two children
      else
    {

        // find the largest node in the left subtree, this will be the node
        // that will take the place of the node to be deleted
        Node *toBeRepl = max(target->left);

        // assign the data of the second largest node
        target->key   = toBeRepl->key;
        target->data  = toBeRepl->data;

        // if new node immediately to the left of target 
        if (toBeRepl == target->left)
        {   
            target->left  = toBeRepl->left;
            Node *newLeft = target->left;
            if (newLeft != NULL) newLeft->parent = target;
        }
        else
        {
            delete(target->left, toBeRepl->key);
            // Node *replParent = toBeRepl->parent;
            // replParent->right = NULL;
        }
}

フィードバックをいただければ幸いです。

編集:明確にするために、サブツリーに触れずに特定のノードを削除しようとしています(存在する場合)。それらはそのままにしておく必要があります（削除するノードの値と（場合によっては）そのサブツリーのノードの1つを交換することで処理しました）。

編集: 次のウィキペディアの記事を参考にしました : http://en.wikipedia.org/wiki/Binary_search_tree#Deletion
:

削除するノードを N と呼びます。N を削除しないでください。代わりに、順序どおりの後続ノードまたは順序どおりの先行ノード R を選択します。N の値を R の値に置き換えてから、R を削除します。

上記の場合、C++ には興味深いコードがいくつかありますが、スワップが正確にどのように発生するかはわかりません。

else    //2 children
{
        temp = ptr->RightChild;
        Node<T> *parent = nullptr;

        while(temp->LeftChild!=nullptr)
        {
                parent = temp;
                temp = temp->LeftChild;
        }
        ptr->data = temp->data;
        if (parent!=nullptr)
                Delete(temp,temp->data);
        else
                Delete(ptr->rightChild,ptr->RightChild->data);
}

誰かがそのセクションで何が起こっているのか説明してもらえますか? 再帰は、ここでのユーザーのコメントと同様のアプローチであると想定しています。

4

3 に答える 3

1

コードに「不法」は見られません。そのようなフォーマットやコメント付きのコードを入手するのは困難です。しかし、はい、delete関数のif-else構造を1つのケースに減らすことができます。削除が何をしているのかについての最も抽象的な考えを見ると、すべてのケースが基本的に最後のケース（2つの子を持つノードを削除する）に要約されていることに気付くでしょう。

数行追加するだけです。toBeRepl = max（left-sub-tree）の後のように、それがNULLであるかどうか、そしてそれがtoBeRepl = min（right-sub-tree）であるかどうかを確認します。

したがって、ケース1（子なし）max() ：メソッドが正しく実装されていると仮定すると、メソッドはNULL左側のサブツリーの右端の要素として返され、右側のサブツリーにも返されmin()ます。ターゲットをtoBeReplに置き換えると、ノードが削除されます。

ケース2（1人の子供）：戻った場合、max()戻ってこNULLないmin()、またはその逆。したがって、NULL以外の値になりますtoBeRepl。もう一度、ターゲットをこの新しいものtoBeReplに置き換えれば、完了です。

ケース3（2人の子供）：ケース2と同じですが、確実max()に戻ってこないのはあなただけですNULL。

したがって、関数全体delete()が最後のelseステートメントに要約されます（いくつかの変更があります）。次の行に何か：

Node *toBeRepl = max(target->left);
if toBeRepl is NULL
{
  toBeRepl = min(target->right);
}

if toBeRepl is not NULL
{
  target->key = tobeRepl->key;
  target->data = toBeRepl->data;

  deallocate(toBeRepl); // deallocate would be a free(ptr) followed by setting ptr to NULL
}
else
{
  deallocate(target);
}
于 2012-12-28T18:06:41.980 に答える
1

ツリーの最後にあると仮定して、再帰を使用してそれを行いnullます。null を見つけることは「戻る」または条件を返すことになります。

1 つの可能なアルゴリズムは次のようになります。

Node* delete(Node *aNode){
  if(aNode->right != NULL)
     delete(aNode->right);
  if(aNode->left != NULL)
     delete(aNode->left);
  //Here you're sure that the actual node is the last one
  //So free it! 
  free(aNode);
  //and, for the father to know that you're now empty, must return null
  return NULL;

}

確かにいくつかのバグがありますが、それが主なアイデアです。この実装はdfsに似ています。お役に立てれば。

[編集] ノード *aNode が修正されました。悪い、星を忘れた。

于 2012-12-28T17:12:39.043 に答える
0

I finished this a long time ago and I thought it would be good to add a sample answer for people coming here with the same problem (considering the 400+ views this question has accumulated):

/* two children */
else
{
    /* find the largest node in the left subtree (the source), this will be the node
     * that will take the place of the node to be deleted */
    Node* source = max(target->left);

    /* assign the data of that node to the one we originally intended to delete */
    target->key   = source->key;
    target->data  = source->data;

    /* delete the source */
    delete(target->left, source->key);
}

Wikipedia has an excellent article that inspired this code.

于 2013-06-24T13:55:08.013 に答える