c++ - 空のツリーを使用した AVL ツリーのマージ (C++ テンプレート)

Question

私が取り組んでいる AVL テンプレート (C++ テンプレート) の一部として、n1+n2 が両方のツリーの合計要素である場合、O(n1+n2) の複雑さで 2 つの AVL ツリーをマージしようとしていました。

次のアルゴリズムを考えました。

1. 1 番目のツリーを順番にトラバーサルし、配列/リストを作成する - O(n1)
2. 2 番目のツリーでの順序走査と配列/リストの構築 - O(n2)
3. これら 2 つの配列の並べ替えをマージし、n1+n2 - O(n1+n2) のサイズで最終的に並べ替えられた配列/リストを作成します。
4. n1+n2 頂点 - O(n1+n2) を持つ空のほぼ完全な二分木を構築します。
5. マージされた配列/リスト内の要素で頂点を更新しながら、ほぼ完全な二分木を順番にトラバーサルします。

私の質問は、n1 + n2頂点を持つ空のほぼ完全なバイナリツリーを実際に構築するにはどうすればよいですか?

Answer 1

マージソートで発行したノードをベクトルに格納しておけば、比較的簡単に行うことができます。ノードはすでにソートされているため、次の方法でノードを「挿入」できます。

1. 配列の 1/2 にある要素からルート ノードを構築します。
2. 配列の 1/4 と 3/4 の要素を使用してルートの子ノードを構築します。
3. 2 を再帰的に繰り返します。

これは、たまたまソートされた配列として表されているバイナリ ツリーの順序どおりのトラバーサルのように感じるはずです。

これが機能するには、バランスを「オフ」にしてツリーを構築する必要があることに注意してください。これはおそらく、これをクラスのプライベート メソッド、おそらく特別なコンストラクターにする必要があります。