如何有效地合并两个BST的？如何有效地合并两个BST的？(How to merge two BST&

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

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

我的问题是：我们可以做任何为O更好（N1 *日志（N2））？

Answer 1:

Naaff的答案多一点细节：

压扁成BST排序列表是O（N）
- 这只是“有序”对整个树迭代。
- 做两个是O（N1 + N2）
合并两个排序列表是为一个排序列表是O（N1 + N2）。
- 请指向两个列表的头
- 挑头较小，推进其指针
- 这是合并排序的作品如何合并
从排序列表创建一个完美的平衡BST是O（N）
- 请参见下面的代码段用于算法[1]
- 在我们的例子排序列表的大小为N1 + N2的。所以O（N1 + N2）
- 结果树是二进制的概念BST搜索列表

三步O（N1 + N2），结果在O（N1 + N2）

对于大小的顺序相同的N1和N2，这是为O更好（N1 *日志（N2））

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

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}

Answer 2:

拼合树木成排序的列表。
合并排序名单。
创建树了合并后的名单。

IIRC，这是O（N1 + N2）。

Answer 3:

什么树都压扁成排序的列表，合并列表，然后创建一个新的树？

Answer 4:

乔纳森，

排序后，我们有长度N1 + N2的列表。建立二叉树出它需要登录（N1 + N2）的时间。这是一样的归并排序，只是在每个递归步骤，我们不会有一个O（N1 + N2）项，因为我们有在归并排序算法。所以，时间复杂度是log（N1 + N2）。

现在整个问题的复杂度为O（N1 + N2）。

此外，我会说这做法是好的，如果两个列表是规模相当。如果大小是没有可比性的话，就最好到小树上的每一个节点插入到一棵大树。这将需要O（N1 *日志（N2））的时间。例如，如果我们有两棵树的大小10的一个又一个的尺寸1024，这里N1 + N2 = 1034，其中作为n1log（N2）= 10 * 10 = 100。因此，方法必须依赖于两棵树的大小。