0

Javaのn分木に複数ノードのLCAを実装しようとしています。私は文の解析ツリーを扱っているので、ノードの子の数 <= 6 と仮定するのは合理的です。ここでの複数のノードは、文内の 2 つのフレーズ (連続した単語シーケンス) です。関係するノードの数を k とします。

1 つの方法は、k/2 ペアの 2 つのノードの LCA を見つけることで、k/2 ノードが得られます。これらの k/2 ノードで再帰します。順序は O(nlog k) になります。ここで、O(n) は線形 LCA 発見アルゴリズムの複雑さです。もっと効率的にできますか？

4

1 に答える 1

1

フレーズのノードが連続している、つまり解析ツリーの葉ノードのリストに連続したインデックスがあるという事実を使用して問題を解決しました。

segment1からstart1までのインデックスがあるとしend1ます。についても同様ですsegment2 = (start2,end2)。

(start1, end1)およびの必須共通祖先は、インデックスおよび(start2, end2)を持つノードの共通祖先です。min(start1,start2)max(end1,end2)

于 2012-07-15T13:59:32.790 に答える