5

私が立ち往生している宿題の質問を手伝ってくれませんか。

完全な二分木の極小値は、そのすべての隣接ノード（隣接ノード=親、左の子、右の子）よりも小さいノードとして定義されます。O（logn）複雑度時間で、ノードごとに異なる数を持つ、与えられた完全な二分木で極小値を見つける必要があります。

さて、要件はO（logn）なので、私は木を通り抜けて葉まで1つのパスだけを通過する方法を考えようとしました。または、再帰で毎回ツリーの半分しか見ることができず、この方法でログが記録されます。

だから私はこれをツリーに持っていると言います：

    70
   /  \
 77    60

3つのケースがあります：

1）ルートが左と右の両方の子よりも小さい//これで完了です

2）根は左よりも小さいだけです

3）根は右よりも小さい

上記のツリーはケース2です。77は親よりも大きいため、77を「ローカル最小値」にする方法がないため、左側のサブツリーを「捨ててしまおう」としましょう。したがって、右側のサブツリーが残ります。極小値が見つかるまで、以下同様です。

ここでの問題は、その左側のサブツリーをスローすると、下にある別のローカル最小値を見逃す可能性があることです。次に例を示します。

                70
              /    \
            77      60
          /   \    /   \
         1    8    9    14
        / \  / \  / \   / \
       3   4 5 6  2 7  15 13

したがって、この場合、ローカルの最小値は「1」のみですが、最初にルートの右側のサブツリーを検索することにしたため、これを見逃しました。

4

3 に答える 3

7

定義上、ローカル最小値は、それに結合されている他のノードの値よりも小さい値のノードです。したがって、あなたの例では、「1」、「5」、「6」、「2」、「7」、「13」はすべて極小値です。

それが明らかになれば、問題は単純です。

まず、ルートをチェックして、両方の子よりも小さいかどうかを確認します。はいの場合、完了です。そうでない場合は、小さい子をピックアップして、再帰的にチェックを適用します。

1）両方の子よりも小さいノードを見つけたか、2）最下位レベル（つまり葉）に到達したかのいずれかで終了します。

ケース1）の場合、停止するノードはローカル最小値です。これは、i）両方の子よりも小さく、ii）親よりも小さいためです。これは、このノードをチェックすることを決定するための前提条件です。

ケース2）の場合、2つの葉（兄弟）が残り、そのうちの少なくとも1つは親よりも小さくなります（そうでない場合は親が返されます）。次に、親よりも小さい限り、どちらか（または両方）がローカル最小値になります。

このアプローチに従うと、レベルごとに最大2つのノードが検査されるため、O（log n）チェックのみが必要になります。

これがお役に立てば幸いです。

于 2014-10-05T17:06:15.397 に答える
0

O（logn）内で子を検索する場合、子がない場合、「2」は極小値と見なされます。O（logn）内に「1」が見つかりません

于 2013-03-27T11:36:30.950 に答える
0

これはO（N）でできると思います。

ルートから開始します。それよりも小さい子がいるかどうかを確認します。もしそうなら、その子供に行きなさい。ない場合は完了です。

次に、現在のノードよりも小さい子を継続的に選択して、このプロセスを繰り返します。現地分か確認してください。そうでない場合は、繰り返します。

これにより、現在のノードの親が常にそれ自体よりも大きくなることが保証されます。アルゴリズムが停止した場合、次の2つのケースのみが発生する可能性があります。

  1. 現在のノードはリーフです。
  2. 現在のノードの2つの子は、どちらもそれよりも大きくなっています。

いずれの場合も、現在のノードはローカル最小値です。

編集：

「完全な」二分木がありません。log（n）である必要があります。

于 2019-01-11T21:25:27.643 に答える