C++ 如何有效地合并两个 BST？

How to merge two BST's efficiently?

提问by gowth08

How to merge two binary search trees maintaining the property of BST?

如何合并两个保持 BST 属性的二叉搜索树？

If we decide to take each element from a tree and insert it into the other, the complexity of this method would be O(n1 * log(n2)), where n1is the number of nodes of the tree (say T1), which we have splitted, and n2is the number of nodes of the other tree (say T2). After this operation only one BST has n1 + n2nodes.

如果我们决定从树上取每个元素，并将其插入到另一个中，这种方法的复杂性将是O(n1 * log(n2))，其中n1是树（说的节点数量T1），这是我们分裂，并且n2是节点的数量另一棵树（比如说T2）。此操作后，只有一个 BST 有n1 + n2节点。

My question is: can we do any better than O(n1 * log(n2))?

我的问题是：我们能做得比 O(n1 * log(n2)) 更好吗？

回答by yairchu

Naaff's answer with a little more details:

Naaff 的回答有更多细节：

• Flattening a BST into a sorted list is O(N)
  • It's just "in-order" iteration on the whole tree.
  • Doing it for both is O(n1+n2)
• Merging two sorted lists is into one sorted list is O(n1+n2).
  • Keep pointers to the heads of both lists
  • Pick the smaller head and advance its pointer
  • This is how the merge of merge-sort works
• Creating a perfectly balanced BST from a sorted list is O(N)
  • See code snippet below for algorithm[1]
  • In our case the sorted list is of size n1+n2. so O(n1+n2)
  • The resulting tree would be the conceptual BST of binary searching the list

• 将 BST 展平为排序列表是 O(N)
  • 这只是整棵树上的“有序”迭代。
  • 对两者都这样做是 O(n1+n2)
• 将两个排序列表合并为一个排序列表是 O(n1+n2)。
  • 保持指向两个列表头部的指针
  • 选择较小的头部并推进其指针
  • 这就是归并排序的合并方式
• 从排序列表创建一个完美平衡的 BST 是 O(N)
  • 请参阅下面的代码片段以了解算法[1]
  • 在我们的例子中，排序列表的大小为 n1+n2。所以 O(n1+n2)
  • 结果树将是二分搜索列表的概念 BST

Three steps of O(n1+n2) result in O(n1+n2)

O(n1+n2) 的三个步骤导致 O(n1+n2)

For n1 and n2 of the same order of magnitude, that's better than O(n1 * log(n2))

对于相同数量级的 n1 和 n2，这优于 O(n1 * log(n2))

[1] Algorithm for creating a balanced BST from a sorted list (in Python):

[1] 从排序列表创建平衡 BST 的算法（在 Python 中）：

def create_balanced_search_tree(iterator, n):
    if n == 0:
        return None
    n_left = n//2
    n_right = n - 1 - n_left
    left = create_balanced_search_tree(iterator, n_left)
    node = iterator.next()
    right = create_balanced_search_tree(iterator, n_right)
    return {'left': left, 'node': node, 'right': right}

回答by Stu

• Flatten trees into sorted lists.
• Merge sorted lists.
• Create tree out of merged list.

• 将树扁平化为排序列表。
• 合并排序列表。
• 从合并列表中创建树。

IIRC, that is O(n1+n2).

IIRC，即 O(n1+n2)。

回答by Naaff

What about flattening both trees into sorted lists, merging the lists and then creating a new tree?

将两棵树展平为排序列表，合并列表然后创建一棵新树怎么样？

回答by genthu

Jonathan,

乔纳森，

After sorting, we have a list of length n1+n2. Building a binary tree out of it will take log(n1+n2) time. This is same as merge sort, only that at each recursive step we wont have a O(n1+n2) term as we have in merge sort algorithm . So the time complexity is log(n1+n2).

排序后，我们得到一个长度为 n1+n2 的列表。用它构建一个二叉树需要 log(n1+n2) 时间。这与合并排序相同，只是在每个递归步骤中，我们不会像合并排序算法那样有 O(n1+n2) 项。所以时间复杂度是 log(n1+n2)。

Now the complexity of the whole problem is O(n1+n2).

现在整个问题的复杂度是 O(n1+n2)。

Also I would say this approach is good if two lists are comparable size. If the sizes are not comparable then it is best to insert every node of the small tree into a large tree. This would take O(n1*log(n2)) time. For example if we have two trees one of size 10 and another of size 1024. Here n1+n2 = 1034 where as n1log(n2) = 10*10 = 100. So approach has to depend upon the sizes of the two trees.

如果两个列表的大小相当，我也会说这种方法很好。如果大小不具有可比性，那么最好将小树的每个节点都插入到大树中。这将花费 O(n1*log(n2)) 时间。例如，如果我们有两棵树，一个大小为 10，另一个大小为 1024。这里 n1+n2 = 1034，其中 n1log(n2) = 10*10 = 100。所以方法必须取决于两棵树的大小。

回答by Manu

O(n1 * log(n2)) is the average case scenario even if we have 2 merge any unsorted list into a BST. We are not utilizing the fact that list is sorted list or a BST.

O(n1 * log(n2)) 是平均情况，即使我们有 2 个将任何未排序列表合并到 BST 中。我们没有利用列表是排序列表或 BST 的事实。

According to me Lets assume one BST has n1 elements and other has n2 elements. Now convert one BST into a Sorted Array List L1 in O(n1).

根据我的说法，让我们假设一个 BST 有 n1 个元素，另一个有 n2 个元素。现在将一个 BST 转换为 O(n1) 中的排序数组列表 L1。

Merged BST(BST, Array)

合并 BST(BST, Array)

if (Array.size == 0) return BST if(Array.size ==1) insert the element in the BST. return BST;

if (Array.size == 0) return BST if(Array.size ==1) 在 BST 中插入元素。返回 BST；

Find the index in the array whose left element < BST.rootnode and right element >=BST.rootnode say Index. if(BST.rootNode.leftNode ==null ) //i.e No left node { insert all the array from Index to 0 into left of BST and } else { Merged BST(BST.leftNode, Array{0 to Index}) }

在数组中找到左元素 < BST.rootnode 和右元素 >=BST.rootnode 表示索引的索引。if(BST.rootNode.leftNode ==null ) //即无左节点 { 将所有从 Index 到 0 的数组插入到 BST 的左边 } else { 合并 BST(BST.leftNode, Array{0 to Index}) }

if(BST.rootNode.rightNode ==null)//i.e No right node { insert all the array from Index to Array.size into right of BST } else { Merged BST(BST.rightNode, Array{Index to Array.size}) }

if(BST.rootNode.rightNode ==null)//ie 无右节点 { 将所有从 Index 到 Array.size 的数组插入到 BST 的右边 } else { 合并 BST(BST.rightNode, Array{Index to Array.size} ) }

return BST.

返回 BST。

This algorithm will take << time than O(n1 * log(n2)) as every time we are partitioning the array and BST to handle the subproblem.

每次我们对数组和 BST 进行分区以处理子问题时，该算法将花费 << 时间比 O(n1 * log(n2)) 多。

---

---

回答by Soumajyoti

The idea is to use iterative inorder traversal. We use two auxiliary stacks for two BSTs. Since we need to print the elements in sorted form, whenever we get a smaller element from any of the trees, we print it. If the element is greater, then we push it back to stack for the next iteration.

这个想法是使用迭代中序遍历。我们为两个 BST 使用两个辅助堆栈。因为我们需要以排序的形式打印元素，所以每当我们从任何树中得到一个较小的元素时，我们就打印它。如果元素更大，那么我们将它推回堆栈以进行下一次迭代。