2

ノードと葉Tを持つツリーが与えられます。nl

k (<=l)正確に葉を含むいくつかのサブツリーを選択する必要があります。ノードtの祖先のサブツリーを選択すると、tのサブツリーを選択できません。

例えば：

ここに画像の説明を入力

これは、T13 のノード (7 つの葉) を持つツリーです。

葉を選択したい場合k = 4は、ノード 4 と 6 (またはノード 2 と 5) を選択できます。これは、選択の最小数です。(ノード 6、7、8、9 のいずれかを選択できますが、これは最小値ではありません)。

葉を選択したい場合k = 5は、ノード 3 を選択できます。これが選択の最小数です。

最小数のサブツリーを選択したい。BFSと動的計画法を使用するアルゴリズムのみO(nk^2)を見つけることができます。O(nk)これを選択することで、より良い解決策はありますか？

ありがとう ：）

4

1 に答える 1

2

実際、各サブツリーの葉の数を知るには、各ノードを1 回通過するだけでよく、複雑さは各ノードの子の平均数である必要O(nm)があります。これを行うには、次のことを行う必要があります。mO(n)m

  • ツリーのどのノードが葉であるかを見つけます
  • ツリーを上に移動し、ノードごとにそのサブツリーの葉の数を保存します

これを行うには、葉から始めて、親をキューに入れます。キューからノードをポップするときはn_i、 の各子から始まる各サブツリーに含まれる葉の数を合計しますn_i。完了したら、訪問済みとしてマークn_iします (子ごとに 1 回追加できるため、複数回訪問しないようにします)。

これにより、次のような結果が得られます。

^
|               f (3)              This node last
|              / \
|            /     \
|          /         \
|        /             \
|       d (2)           e (1)      These nodes second
|      /  \            /
|     /    \          / 
|    a (1)  b (1)    c (1)         These nodes first

手順は次のとおりです。

Find leaves `a`, `b` and `c`.
For each leave, add parent to queue   # queue q = (d, d, e)

Pop d                                 # queue q = (d, e)
Count leaves in subtree: d.leaves = a.leaves + b.leaves
Mark d as visited
Add parent to queue                   # queue q = (d, e, f)

Pop d                                 # queue q = (e, f)
d is visited, do nothing

Pop e                                 # queue q = (f)
Count leaves in subtree: e.leaves = c.leaves
Mark d as visited
Add parent to tree                    # queue q = (f, f)

Pop f                                 # queue q = (f)
Count leaves in subtree: f.leaves = d.leaves + e.leaves
Mark d as visited
Add parent to tree (none)

Pop f                                 # queue q = ()
f is visited, do nothing

2 回追加されたノードを無視するスマート データ構造を使用することもできます。「上位」ノードの前に「下位」ノードを探索することが非常に重要であるため、順序付きセットを使用できないことに注意してください。

あなたの場合、キュー内のノードが葉よりも多い場合はそれらを削除し、k葉を持つことがわかった各ノードを返すことができますk。これにより、さらに高速なアルゴリズムが得られます。

于 2012-11-18T19:19:32.910 に答える