2017-12-18 18 views
1

をマージします。 リストからすべての値を挿入intro target trie:n * O(m)、mはキーの長さです 最悪の場合、キーのサイズはnであり、マージの複雑さではありませんO(n^2 )?は、私は2つのトライ構造をマージしたいが、私は考えることができる最善の複雑さが</p> <p>ある他のトライから値の一覧を取得する2つのバイナリトライ

これを実行する方法はありますか?

+0

(推奨編集)ツリーのサブセットであるtrie(https://en.wikipedia.org/wiki/Trie)をマージする手順があれば、私は実際に興味がありますが、より具体的にしようとしました。 – Davar

+2

はい、良い方法があります。トライが木であるという事実を利用する。すなわち、ルートと木でもあるいくつかの枝を持つ。どのようにこれらのものをマージしますか? –

+0

@ n.m。たぶん私は両方の木を同時にトラバースすることができ、値が存在するかどうかを確認するだけです。 – Davar

答えて

1

複雑さはO(N + M)になります。 2つのイテレーター(ツリーノードポインター)が、それぞれのツリーのルートノードで開始する必要があります。

子供がイテレータの1つにしか存在しない場合、子供を見ると、その子を結果にコピーするだけです(子を直接動かす(ポインタを割り当てることができれば))。子が両方の側に存在する場合、それぞれの子に対して再帰的に関数を呼び出します。

このようにして、あいまいなノードをマージするだけで、1つのサブツリー全体をコピー/移動することができます。

元のアイデアを実行すると、複雑さはO(N * M)になります。ここでNはエントリの数であり、mはエントリの平均長です。すべてのノードが単一のエントリ(最悪の場合)のためのものであれば、そのエントリを一度だけコピーする必要があるため、O(N^2)を取得しません。

関連する問題