最初の全体的なツリーなしで、2 人の共通祖先の最小値を計算するための優れたアルゴリズムを探しています。
子供がいる場合は、電話をかけて親を迎えに行くことができます。したがって、2 人の子供がいる場合、共通の祖先ができるまで、それぞれを呼び出す必要があります。この時点で、ツリーに構築できる 2 つのリストが必要です。
これにはどのようなアルゴリズムが適しているでしょうか?
1 に答える
0
特定のノードが「原則として」別の特定のノードの親になることができるかどうかを決定する基本的な情報がある場合、共通の祖先（存在する場合）を迅速/効率的に決定できます。それが「年齢」についての私の質問（コメントを参照）についてでした。年齢プロパティは明らかにあなたにそのタイプの情報を与えるでしょう。
あなたの答えから、そのような情報が利用できないと仮定すると、2つの明白なアプローチがあります：
A.両方のツリーを上向きにスキャンし（getParentなど）、最初の子ごとに祖先リストを作成し、その間、すべての新しい祖先で、それが他の子の祖先リストにあるかどうかを確認します。一般的に言えば、共通の祖先が2人の子から（「ほぼ」）等距離にあると仮定する理由はありません。したがって、それぞれの祖先リストを作成する順序は、共通の祖先を与えるのと同じようになります。可能な限り少ないステップ。
この方法の欠点は、新しい候補の出現のために相互リストを何度も検索しなければならないリスクを冒すことです。これは潜在的に遅いです。
B.別の方法は、使い果たされるまで2人の祖先のそれぞれを独立して構築することです。「他の」リストの内容をチェックする必要があるため、各ステップで中断されないため、これはおそらく比較的高速です。
次に、2つのリストを終了すると、上位のアイテムを相互に検証するだけで、共通の祖先があるかどうかがわかります。いいえの場合、完了です（結果はありません）。はいの場合は、リストを同期的にさかのぼって、リストがどこで分離されているかを確認します。これもリスト検索を避けます。
一般的な観点から、私は方法Bを好みます。場合によっては、方法Aの方がもちろん結果が速くなりますが、悪い場合には、方法Bでは起こらない退屈で遅くなる可能性があります。祖先リストを循環させることはできません。つまり、ノードをそれ自体の祖先にすることはできません。
最後の注意として：結局のところ、「年齢」の意味でノードを「順序付け」するプロパティがある場合は、現在のリストを常に処理するという意味で、2つのリストを同時に作成する必要があります。他のリストのトップノードの親になることはできないトップノード。これにより、現在のトップノードのみを相互にチェックできます（リストの他のメンバーはチェックできません）。
于 2012-10-01T18:52:18.223 に答える