c++ - 2 つの異なる AVL ツリーのマージ

Question

2 つの AVL ツリーがあり、それぞれのサイズがわかっているとします。ただし、ノードが繰り返されているかどうか、またはその他の情報があるかどうかはわかりません。それらを新しい AVL ツリーにマージする最も効率的な方法は何ですか? 元の木は破壊することができます。

Answer 1

1. ツリーT1をT2ソート済みリストに変換しL1、L2
2. 並べ替えられたリストに統合しL1ますL2L
3. L再びツリーに変換しTます。

IIRC では、この操作はすべて O(N) であるため、完全なマージも O(N) になります。

AVL ツリーの表現がそれらを効率的に反復できる場合 (たとえば、バックポインター、継続、遅延評価などを使用) は、中間リストなしでも実行できるはずです。

更新: プログラミング言語が C/C++ のように見えるため、AVL ノードの estructure を一時的に悪用してリンク リスト内のノードにし、後でそれらを出力ツリーに再利用することができます。

更新 2 : @hwlau: これは O(N) です。avl.plから入手できる Prolog の独自の AVL 実装と、サイズ 1 の AVL ツリーをマージするときの操作数をチェックするこのテスト プログラムavl_test.plを使用してチェックしました。 2、4、8、16、...

これは出力です：

timing avl_merge, size: 128
% 1,790 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
timing avl_merge, size: 256
% 3,591 inferences, 0.010 CPU in 0.002 seconds (430% CPU, 359100 Lips)
timing avl_merge, size: 512
% 7,176 inferences, 0.030 CPU in 0.028 seconds (107% CPU, 239200 Lips)
...
timing avl_merge, size: 32000
% 451,839 inferences, 0.490 CPU in 0.499 seconds (98% CPU, 922120 Lips)
timing avl_merge, size: 64000
% 903,682 inferences, 0.900 CPU in 0.964 seconds (93% CPU, 1004091 Lips)
timing avl_merge, size: 128000
% 1,807,363 inferences, 2.420 CPU in 2.559 seconds (95% CPU, 746844 Lips)

推論/操作の数は、マージされたツリーのサイズに比例するため、アルゴリズム O(N) の複雑さは明らかです。

Answer 2

これは最も効率的ではありませんが、間違いなく実装が最も簡単です。2 番目のツリーから最初のツリーにすべてのノードを追加するだけです。2 番目のツリーからノードを削除する必要はありません。次に、2 番目のツリーを破棄するだけで、結果として最初のツリーが得られます。時間計算量はO(N*log(N))です。