問題タブ [least-common-ancestor]

ここでの二分木は、必ずしも二分探索木である必要はありません。
構造は次のように取ることができます -

私が友人と一緒に解決できる最大の解決策は、このようなものでした -この二分木
を考えてみましょう:

順序通りのトラバーサルの結果 - 8、4、9、2、5、1、6、3、7

そして、ポストオーダー トラバーサルは、8、9、4、5、2、6、7、3、1 を生成します。

したがって、たとえば、ノード 8 と 5 の共通の祖先を見つけたい場合は、順序付けされたツリー トラバーサルで 8 と 5 の間にあるすべてのノードのリストを作成します。この場合、たまたま [4, 9 、2]。次に、このリストのどのノードがポストオーダー トラバーサルで最後に表示されるかを確認します。これは 2 です。したがって、8 と 5 の共通の祖先は 2 です。

このアルゴリズムの複雑さは、O(n) (順序/事後トラバーサルの場合は O(n)、配列内の単純な反復にすぎないため、残りのステップは O(n) であると私は信じています)。しかし、これが間違っている可能性が非常に高いです。:-)

しかし、これは非常に大雑把なアプローチであり、場合によってはうまくいかないかどうかはわかりません。この問題に対する他の (おそらくより最適な) 解決策はありますか?

私はこの質問を見て、次にTarjan の最小共通祖先アルゴリズムについて読んでいました。これまで、LCA アルゴリズムのアプリケーションに出くわしたことはありません。

そのような LCA アルゴリズムはどこで一般的に使用されていますか?

以前にも同様の質問があったことは知っていますが、私の解決策ははるかに簡単だと思います。特にウィキペディアと比較すると。

私が間違っていることを証明してください！

指定されたデータ構造を持つノードを持つツリーがある場合:

次のような関数を書くことができます:

このコードは非常に簡単で、最悪の場合は O(n)、平均的な場合はおそらく O(logn) です。特にツリーのバランスがとれている場合 (n はツリー内のノードの数)。

時々私はこのようなインタビューの質問に出くわします：「ツリー内の任意の2つのノードの共通の親を見つけてください」。グーグルやアマゾンなどでもLCAの質問をしていることに気づきました。

ウィキペディアが言うように、LCAは、与えられたノードからルートへのパスの交差によって見つけることができ、O（H）を取ります。ここで、Hは木の高さです。さらに、O（N）でツリーを処理し、O（1）でLCAクエリに応答するより高度なアルゴリズムがあります。

このLCAの質問をする候補者について、インタビュアーが正確に何を知りたいのだろうか。パス交差の最初のアルゴリズムは些細なようです。彼らは候補者が前処理アルゴリズムを覚えていることを期待していますか？彼らは候補者がこれらのアルゴリズムとデータ構造をその場で発明することを期待していますか？

以下は、最初の共通の祖先を見つけるための私のアルゴリズムです。しかし、時間の複雑さを計算する方法がわかりません。誰か助けてもらえますか?

目標:

グラフ内のノードが 0、1、または 2 つの親を持つことができるグラフの最適な共通祖先を見つけるアルゴリズムを探しています。「最良の共通祖先」の用語がよくわかりません。より適切な用語は、「最小の共通の祖先」または「最近の共通の祖先」などです。より適切な用語がある場合は、そのような用語を説明する URL を提供してください。

このアルゴリズムは、完全なグラフ データ構造にアクセスできます。

特定のノードがゼロ、1 つ、または 2 つの親を持つことができます。私が Web で見たアルゴリズムは、特定のノードに 0 または 1 つの親があり、2 つの親はないと想定しているため、これが重要です (以下の参考文献を参照)。たとえば、下の図の m1 ノードはルートであるため、親がありません (グラフの複数のルートが存在する可能性があります)。d3 には 2 つの親があり、1 つは d2 で、もう 1 つは b2 です。

ノードには、存在する場合は両方の親への参照があり、存在する場合はすべての子への参照があるため、ツリーを上下にトラバーサルするのは公正なゲームです。ノードは 0 個以上の子を持つことができます。データ構造を変更することはオプションではありません。

2 つの入力ノードに近いノードは、遠いノード (つまり、グラフのルートに近いノード) よりも優先されます。

例として、考えられるグラフの 1 つを以下の図に示します。このシナリオでは、アルゴリズムへの入力はノード b5 と d4 になります。ノード b5 と d4 の最良の共通祖先は b2 です。b3 は b5 につながる血統にあるため、c2 はありません。

アルゴリズムの可能な答えは最大で 1 つのノードであり、空のセットは 2 つの入力ノードの共通の祖先がない場合の有効な答えです。

参考資料

Tarjan のオフラインの最小共通祖先アルゴリズムは、0 または 1 つの親を暗示しているように見えるため、それが解決策である場合、そのアルゴリズムで 2 つの親がどのように考慮されるかについての説明を回答に含める必要があります。最低共通祖先のウィキペディアのページも、ノードが 2 つではなく、0 または 1 つの親を持つデータ構造のみを説明しているようです。

各ノードがその親を指すツリー データ構造では、...

図：

そのため、私は最も低い共通祖先アルゴリズムの実装を検討してきました。私は多くの異なるアルゴリズム（主にTrajanのソリューションのバリエーションまたはRMQのバリエーション）を調べました。

非二分木を使用しています。私のツリーはクエリ間で頻繁に変更されるため、前処理は必ずしも価値がありません。ツリーには、50〜75を超えるノードを含めることはできません。私が疑問に思っているのは、彼らのアルゴリズムをわざわざ使用するべきか、それとも自分のアルゴリズムに固執するべきかということです。

私のアルゴリズム

有向非巡回グラフで複数のノードの最も一般的でない祖先を見つけるにはどうすればよいですか?

このトピックに関するかなりの数の論文を見つけましたが、それらはすべて、2 つのノードの DAG で LCA を見つけたようです。

複数のノードに適したアルゴリズムはありますか?

この質問は多くの人から聞かれたかもしれませんが、それはちょっと違います。二分木があります。そして、2つのノードpとqが与えられます。最も一般的でない親を見つける必要があります。しかし、ルートを指すルートノードポインタはありません。次の2つの組み込み関数が提供されます。

1）BOOL same(node *p, node *q);->ノードが同じである場合はtrueを返し、そうでない場合はfalseを返します。

2）node* parentNode(node *c);->現在のノードの親であるノードを返します。

ノードcが実際にルートである場合、parentNode関数はNULL値を返します。関数を使用して、ツリーの最も一般的でない親を見つける必要があります。

組織階層の推移閉包を表すテーブルがあります（つまり、単一のルートを持つツリー）。

各ユーザーがアクセスを許可されている組織を含む別のテーブルがあります。

システムは、ユーザーがアクセスできる各組織に関連付けられた支出のロールアップをユーザーに表示します。私はいつでも、ユーザーに会社のビュー（つまり、ルート）を表示して、ユーザーに直接の子組織のリストと、彼の組織が合計にどれだけ貢献しているかを表示することから始めることができます。ほとんどの場合、子は1人であり、ユーザーは複数の子を表示する前に複数のレベルをドリルダウンする必要があります。私は、複数の子供を示す最初の組織（つまり、LCA）からプレゼンテーションを開始したいと思います。

特定のユーザーの場合、ルートへのパスのセットを簡単に見つけることができますが、最も一般的でない祖先を見つけるのに問題があります。私はpostgresql9.1を使用していますが、データベースに依存しないソリューションを好みます。最悪の場合、ルートへのパスをアプリケーションのコードに戻し、そこでLCAを計算できます。