問題タブ [lowest-common-ancestor]

ノード w がツリー内のノード u とノード v の間のパス上にあるかどうかを判断する必要がある問題を解決しようとしています (必ずしもバイナリではありません)。

たとえば、次のツリーの場合:

ノード 2 は、ノード 4 から 7 へのパス上にあります。

明らかな解決策は、ツリーのオイラー ツアーを取得し、両方のノードの最初の発生の間にアクセスされたノードをトラバースすることです。ただし、n がツリー内のノード数である最悪の場合、これは O(n) ソリューションになります。これは LCA (Lowest Common Ancestor) を使用して実行できることをどこかで読みました。しかし、私はその方法を理解できないようです。誰かが私にアドバイスしてもらえますか？

DNA SNP の階層ツリー (DAG) をロードしました。最低共通祖先を特定したい。

このクエリは機能し、単一の正しいノードが生成されます。

ただし、これでは結果が得られません。

両方のyieldノードの祖先を求める2つのクエリは、その一部が共有されていますが:

と

問題は、R-Z11 が 2 番目のクエリのパスにあり、それ自体が祖先であることです。つまり、LCA が最短経路の終点にある場合があります。R-Z11 が最短経路にあるかどうかに関係なく結果として返されるように、これに対処する方法はありますか?

pとの2 つのノードが与えられqた場合、どのようにして最も低い共通の祖先を見つけますか? (両方とも非常に大きなツリーに属していると仮定します)

ツリーのルートへの参照がありません。

これを行う最も効率的な方法は何ですか? これまでのところ、私が持っている唯一のアイデアは

(1) ノード p を選択します (どちらでも構いません)

(2) p の左部分木を検索し、q がある場合は p を返す

(3) そうでなければ、p の右側の部分木を検索し、q がある場合は p を返す

(4) そうでない場合は、1 レベル親に移動し、p を含まないサブツリーを検索します。q が見つかった場合は、親を返します。

(5) そうでない場合は、もう一度 1 レベル上に移動し、(4) を繰り返します (この親を含まないサブツリーを検索します)

これは非常に非効率に思えます。より良いアルゴリズムはありますか？

ツリー構造のデータで機能するツールを書きたいと思います。(実際には、git リビジョン DAG のツリーのようなサブセットで動作しますが、それはこの質問では重要ではありません)。特に、特定の入力セットのすべての「結合ポイント」からなるツリーのサブセットを再構築するアルゴリズムが必要です。

具体的に私が欲しいと思うのは

• H「最小共通祖先」関数を持つ型がありlcaます。これによりH、ツリーのような構造が得られます。

• このアルゴリズムは、 のサブセットSをH入力として受け取ります。

• t出力は、 の値でラベル付けされたノードを持つ多元木になりますH。

• tプロパティを満たす必要があります

  • すべてsのSラベルの一部のノードt

  • の葉は、 のt要素によってのみラベルを付けることができますS

  • のノードが 1 つ以下hのラベルの任意の要素Ht

  • h1labelsn1とh2labelsの場合、との最小共通祖先にラベルをn2付けます。lca(h1, h2)n1n2t

私の質問は、「これは既知のアルゴリズムの既知の問題ですか?」です。そうだと思います。トポロジカルソートに非常に似ているようです。マージソートに基づくアルゴリズムのアイデアはありますが、既知のアルゴリズムが既に存在する場合、独自のアルゴリズムを思いつく理由はありません。