0

ノードに2つの親ノードへの参照が含まれているツリーがあります。動作の仕方により、ある時点で同じノードを指すことがあります。

Example:

Parent1: Node234234 -> Node233645 -> Node2323429 -> Node2939230
Parent2: Node112938 -> Node2323429 -> Node2939230

各ノードを 1 回だけ解析しようとしているだけの場合、それが何回表示されても、どのように処理しますか?

List.Contains を使用して、それが true の場合は停止することを考えましたが、ややこしいようです。HashTable (ノードを追加するだけ) を使用することを考えましたが、大きなツリーでは非常に非効率的である可能性があると思います。効率的で迅速な解決策は何だと思いますか?

4

1 に答える 1

0

**編集:** あなたの質問をもう一度読んだ後、私はそれを誤解したと信じる十分な理由があります。あなたは実際にテキスト入力を解析し、そこからツリーを作成しているようです。その場合は、オプション番号を無視してください。2.


1.ブルーム フィルターを使用する。ツリーが大きい場合はスペースの点で間違いなく価値があり、ノードがあまり頻繁に繰り返されない場合、および一部のノードがまったく解析されないことを許容できる場合は、ニーズに合う可能性があります。一部のノードは解析されない場合があります。これは、この構造体が属している演算子に対して誤検知を返す可能性があるためです (その意味では、確率的データ構造です)。詳細については、ウィキペディアのページを確認してください。

2.現在のノード クラスをラップし、ノードにアクセスすると true に設定されるブール値を追加するクラスのツリーを作成します。次のようなもの： 

class NodeAndVisitationInfo {
    public bool Visited;
    public NodeType Node;

    public NodeAndVisitationInfo() {
        Visited = false;
    }
}

この 2 番目のソリューションは、この操作を複数回行う必要がある場合には理想的ではない可能性があります。その場合、訪問アルゴリズムを再度実行する前に、両方のツリーのすべてのノードに対してを設定Visitedする必要があるためです。また、このアルゴリズムは完全にスレッドセーフfalseではないことに注意してください。

何よりも、新しく解析されたノードごとに単純な呼び出しを行わないでくださいList.Contains。これは、最悪のシナリオでは O(n^2) になります。ノードを検索構造に格納する場合は、償却挿入と検索の複雑さの両方が優れている構造を優先してください。その点では、順序付きリストまたはハッシュセットの方が適している場合があります。

于 2013-01-07T03:16:03.603 に答える