1

私はツリー データ構造を c# ベースで実装しています (主にDan Vanderboom の Generic implementationに基づいています)。私は現在、Dan が実装していない Count プロパティを処理する方法を検討しています。

明白で簡単な方法は、ツリーをトラバースしてノードを追加する再帰呼び出しを使用することです (または、必要に応じて、キューを使用してツリーを繰り返しトラバースし、ノードをカウントします)。ただ高価に思えます。(また、いくつかのノードを遅延ロードしたい場合もあります)。

ルート ノードでカウントを維持できました。すべての子は、ルートまでトラバースするか、ルートへの参照を保持し、変更時に内部的に設定可能な count プロパティを更新します。これにより、ブランチを分割したり、特定のノードの下にあるすべての子をクリアしたりするときに、反復の問題が発生します。一般的に安価であり、関数と呼ばれる頻度が低いと思われる重労働を行います。

少し力ずくのように思えますが、それは通常、私がまだ考えていない例外ケース、または必要に応じてバグを意味します。

その場でカウントするのではなく、アンバランスおよび/または非バイナリツリー構造のカウントを保持する実装の例はありますか? 遅延読み込みについて心配する必要はありません。特定のニーズに合わせて例を調整できると確信しています。

4

4 に答える 4

1

You could have a count property on the tree. In the method that adds nodes, increase the count and in the method that removes nodes, decrease the count.

Runtime = the time it takes to read a property.

于 2012-10-11T21:14:04.620 に答える
1

Node クラスは、ノードが追加または削除されるたびに更新される子の数を保持できます。次に、ルート ノード (または任意のノード) のカウントを取得するには、そのすべての子のカウントを合計します。

しかし、物事を単純にするために、D Stanley が提案するようにして、単に Count を再帰的に実装してみませんか?

于 2012-10-11T21:27:38.647 に答える
1

ノードのことばかり考えていて、ノードへのアクセスを制御する Tree クラスがあることを忘れているようです。Tree クラスは Count プロパティを持つことができます。Add と Remove は両方とも Tree クラスによって公開されているため (ノードによって公開されるべきではありません)、項目が変更されるたびに常に増減できます。

于 2012-10-11T21:15:02.667 に答える
0

コメントありがとうございます。私は実際には議論を招きたくなかったのですが、誰かがサンプルを持っているかどうかを知りたかったのですが、そうではないようです.

良いサンプルが入手できず、自分で作業する必要があるというのが答えだと思います。

皆さんが私の結論に貢献してくれたので、それぞれに +1 を付けました。

于 2012-10-12T15:07:27.643 に答える