c++ - 2 つの二分探索木のマージ

Question

重複の可能性:
2 つのバイナリ ツリーをマージする方法

私は木のコードに不慣れで、関数を書いて 2 つの二分探索木をマージするコードを書くように頼まれました。

void mergeBst (BST & othertree)

この関数は別の Bst を受け取り、そのツリーからすべての非冗長値を現在のツリーに挿入します。その方法を教えてください。

Answer 1

2 つのツリーを使用して 2 つのソート済みリストを作成します。これは O(m+n) になります。次に、2 つのソートされたリストを順序を維持してマージします。(O(m+n)) マージされたリストを使用して構成ツリーを作成します。(O(m+n))

または、単に入力ツリー内のすべてのノードについて、ノードをソース ツリーに挿入する位置を見つけます。それから挿入します。

2 つのバイナリ ツリーをマージする方法

2 つの BST を効率的にマージするには?

Answer 2

ツリー B をツリー A にマージするには ( A.mergeBst(B)):

B のルートを A のルートと比較します。B のルート
の方が大きい場合は、B.leftA にマージし、B の残りを にマージしA.rightます。
少ない場合はB.rightA にマージし、残りの B を にマージしA.leftます。
それらが等しい場合は、 、 にマージB.leftしA.left、B のルートを破棄しB.rightます。A.right

Answer 3

2 つの二分探索木を考える:

1. ソース- 反復する BST
2. ターゲット- ソースの値を追加する BST

かなり単純なアルゴリズムがあります。

ソース検索の各「値」について、それらがターゲットにある場合はそれらを破棄し、そうでない場合は挿入します。

編集：「反復」とは、私が意味した：http://en.wikipedia.org/wiki/Tree_traversal

予約注文の反復:

1. ルートにアクセスします。
2. 左のサブツリーをトラバースします。
3. 右のサブツリーをトラバースします。