1

私の問題は、txt ファイルのリストから作成される一般的なツリーの LCA を見つけることです。最も効率的な実装を探しています。データの形式は次のとおりです: Id、info、ParentId

データはいかなる方法でもソートされません。ツリーを作ろうと思ったのですが、最低でもO(nlogn)かかります。対数ベースは2ではありませんが、私が推測する子供の平均数に依存します。

代わりに、ノードをハッシュテーブルに格納すると、LCA を見つける方が O (nlogn) よりも優れています。右？宛先ノードの各親について、ソース ノードがアクセスしたかどうかを確認する必要があります (ソース ノードからルートまでを開始し、途中のすべての親をアクセス済みとしてマークすると仮定します)。 （ログイン）。親をチェックするだけなので、O(nlogn) よりも優れています。

もっと良いアイデアはありますか？

4

1 に答える 1

0

ツリーが何らかの形でバランスが取れているとします。つまり、O(logn) の高さであり、ハッシュテーブル データ構造は O(n) アルゴリズムを提供する必要があります。

最初に、ソースと宛先の両方からルートまでトレースします。長さ O(logn) の 2 つのパスがあります。たとえば、SXYZR と DWYZR。S と D はソースと宛先です。R はルートです。これには O(logn) 時間がかかります。

次に、YZR である最長の接尾辞を見つけることができます。Y は LCA になります。これには O(logn) 時間がかかります。

入力を読み取ってハッシュテーブルを作成するには、O(n) 時間かかることに注意してください。

于 2014-12-02T15:31:30.550 に答える