1

現在、C ++で二分探索木に取り組んでおり、削除/削除関数を作成する必要がある段階に達しました（再帰的アプローチを使用x = change(x)）。私には2つの選択肢があります：

  • 削除するノードのノードの親で停止します。


  • 削除するノードに到達してから、親を返す関数を呼び出します

アプローチ1：より安価で、より多くのコード

アプローチ2：コードが少なく、コストが高い

あなたによると、どちらのアプローチが優れていますか、そしてその理由は何ですか？

4

3 に答える 3

1

それらがあなたの唯一の2つの選択肢であることに同意しません.

より簡単な解決策は、各ノードに削除する必要があるかどうかを尋ねることだと思います。「はい」と判断した場合は削除され、それを置き換える新しいノードが返されます。いいえと判断した場合は、自分自身を返します。

// pseudo code.
deleteNode(Node* node, int value)
{
    if (node == NULL) return node;

    if (node->value == value)
    {
        // This is the node I want to delete.
        // So delete it and return the value of the node I want to replace it with.
        // Which may involve some shifting of things around.
        return doDelete(node);
    }
    else if (value < node->value)
    {
        // Not node. But try deleting the node on the left.
        // whatever happens a value will be returned that
        // is assigned to left and the tree will be correct.
        node->left = deleteNode(node->left, value);
    }
    else
    {
        // Not node. But try deleting the node on the right.
        // whatever happens a value will be returned that
        // is assigned to right and the tree will be correct.
        node->right = deleteNode(node->right, value);
    }
    // since this node is not being deleted return it.
    // so it can be assigned back into the correct place.
    return node;
}
于 2012-04-28T22:32:57.003 に答える
0

最善の方法は、削除するノードの親までトラバースしてから、その子ノードを削除することです。最終的にこのアプローチを使用すると、子ノードが削除したいノードであることを常に確認する必要があるため、常に子ノードにアクセスします。

于 2012-04-28T22:12:00.390 に答える
0

一般に、ツリー データ構造の関数を記述するための最も効率的な形式は、次の擬似コード形式であることがわかりました。

    function someActionOnTree() {
         return someActionOnTree(root)
    }

    function someActionOnTree (Node current) {
         if (current is null) {
              return null
         }
         if (current is not the node I seek) {
              //logic for picking the next node to move to
              next node = ...

              next node = someActionOnTree(next node)
         }
         else {
              // do whatever you need to do with current
              // i.e. give it a child, delete its memory, etc
              current = ...
         }
         return current;
    }

この再帰関数は、データ構造の頂点セットを再帰します。アルゴリズムの反復ごとに、関数を再帰するノードを探し、そのノードへのデータ構造の参照をそのノードでのアルゴリズムの反復の値で上書きします。それ以外の場合は、ノードの値を上書きします (そして、別のロジック セットを実行する可能性があります)。最後に、関数はパラメータ ノードへの参照を返します。これは、上書きステップに不可欠です。

これは、一般的に、C++ のツリー データ構造に対して私が見つけた最も効率的な形式のコードです。概念は他の構造にも適用されます。この形式の再帰を使用できます。戻り値は常に、データ構造の平面表現の固定点への参照です (基本的に、常に、その場所にあるはずのものを常に返します)。見ている）。

これは、このスタイルをバイナリ検索ツリーの削除関数に適用して、私の要点を装飾したものです。

function deleteNodeFromTreeWithValue( value ) {
     return deleteNodeFromTree(root, value)
}

function deleteNodeFromTree(Node current, value) {
     if (current is null) return null
     if (current does not represent value) {
          if (current is greater than my value) {
               leftNode = deleteNodeFromTree(leftNode, value)
          } else {
                rightNode = deleteNodeFromTree(rightNode, value)
          }
      }
      else {
           free current's memory
           current = null
      }
      return current
}

もちろん、このコードを記述する方法は他にもたくさんありますが、私の経験からすると、これが最も効果的な方法であることがわかりました。ハードウェアはすでにノードをキャッシュしているため、ポインターを上書きしてもパフォーマンスは実際には影響を受けないことに注意してください。検索ツリーのパフォーマンスを改善することを検討している場合は、自己均衡ツリー (AVL ツリー)、B ツリー、赤黒ツリーなどの特殊なツリーを調べることをお勧めします。

于 2012-04-28T22:31:30.643 に答える