時間の複雑さ - すべての最も深い葉の最低の共通の祖先を見つけるためのアルゴリズム

cs.stackexchange https://cs.stackexchange.com/questions/120186

質問

これは私が今日の遭遇した問題の声明です。

バイナリツリーを与えられた、最も深い葉すべての最も低い共通の祖先を見つけます。

私は正しいアルゴリズムを思い付きましたが、このアプローチの実行時間を確認したいです。

アルゴリズムは次のとおりです。

  1. ツリーを通過し、ツリーの最も深いレベルを見つけます。 dmax 。
  2. 木を横切って、すべての葉が深さ Dmax 。
  3. lca（a、b、c） = LCA（LCA（A、B）、C） < / Strong>、ステップ2で見つけたすべてのノードを通過し、LCAを計算します。

    4. LCA（A、B） のサブルーチンは簡単です。 a から始めて、ルートまでずっと訪問したノードをハッシュセットに保存します。次に、 B から始めて、HashSetに含まれるノードを見つけるまで上がります。

    私はアルゴリズムの最初の2つのステップが o（n）の両方であることを知っています。ここで、nはツリー内のノードの数に対応します。しかし、私は最後のステップについて不確実です。

    LCA（A、B） サブルーチンは線形の複雑さを有する。しかし、最悪のシナリオでは、ステップ2でいくつのノードが見つかりますか？

    直感的に、私はそれがN個のノードよりはるかに小さい必要があると主張します。

役に立ちましたか？

解決

@Rick Deckerが説明されているので、 $ n / 2 $ を1つのケースの最大深さに残すことができます。この場合、ステップ3は $ o（n \ log n）$ です。 この記事最悪の場合を表示します。ツリーを考える $ t $ は、残りの $ n / 2 $ ノードのチェーンで構成されています。 class="math-container"> $ n / 2 $ ノードは、チェーンの下部にあるバランスのとれたツリーとして接続されています。これにより、すべてのリーフ深度 $ n / 2 + \ log_2（n）=theta（n）$ が $ n / 4 $ 深度 $ \ theta（n）$ $ \ theta（n ^ 2）この場合、ステップ3の$ 実行時。 max depth $ n $ で $ n $ ノードを持つので、これは最悪の場合です。

これを行うためのより良い方法があります。関数を定義する $ f $

$ f（v）=begin {ケース} v＆\ text {\ quad \ texttttt {高さ}（v.left）=texttt {高さ}（v.Right）\\ F（v.left）＆\ text {height}（v.left）> \ texttt {高さ}（v.Right）\\ f（v.right）＆\ text {height}（v.left）<\ texttttttttttt {高さ}（V.Right） \ end {ケース} $

ノードの子の高さが同じ場合は $ v $ が同じで、明らかに $ v $ は、 $ v $ に根ざしたサブツリーの最も深いノードのLCAです。左のサブツリーが背が高い場合は、 $ v.left $ に根ざしたサブツリーの最深部ノードのLCAが、最も深いノードより深いので、 $ v.right $ に根ざしたサブツリー。 $ v.right $ の場合は同じ論理があります。

$ \ texttt {height} $ との値の値 $ t $ の後期トラバーサルで計算されます。

呼び出し $ f（root）$ は、ツリー内の最も深いノードのLCAを返します。

他のヒント

まあ、私はあなたが「はるかに少ない」で意図するものを知りませんが、 $ n / 2 $ の最大深さにあることが明らかです：たとえば最低レベルのフルで、完全な2進ツリーを取ります。

ツリーごとに、ツリーのすべての最も深いノードの最低の共通の祖先を計算する関数を書きます、とツリーの高さを計算します。これは非常に簡単です：

ルートRに左側または右のブランチがない場合、高さは1で、共通の祖先はRです。ルートRに左側または右のブランチがある場合は、そのブランチの高さと最も低い祖先を計算します。ルートRを持つ高さは1つですが、最も低い共通の祖先は同じです。

左と右の分岐がある場合は、両方のブランチの高さと最も低い祖先を計算します。高さが異なる場合は、（高さ+ 1）とそのブランチの最低の先祖を返します。高さが同じであれば、（身長+ 1）、rを最低の共通の祖先として返します。

ノード数がNである場合は小さな定数CでCNステップを取る必要があります。また、すべてのノードNを訪問しなければならない（少なくとも分岐がないことを確認する）、これを改善することはできません。

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top