如何有效地合并两个 BST？

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

如果我们决定从树中取出每个元素并将其插入到另一个元素中，则此方法的复杂度将为O(n1 * log(n2)), where n1是树的节点数（比如T1），我们已经拆分了，并且n2是另一棵树的节点数（比如T2）。执行此操作后，只有一个 BSTn1 + n2 nodes.

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

Naaff 的回答有更多细节：

• Flattening a BST into a sorted list is O(N)
  • 这只是整个树上的“按顺序”迭代。
  • 两者都做是 O(n1+n2)
• Merging two sorted lists is into one sorted list is O(n1+n2).
  • 保留指向两个列表头部的指针
  • 选择较小的头部并将其指针向前推进
  • 这就是归并排序的合并工作原理
• Creating a perfectly balanced BST from a sorted list is O(N)
  • 请参阅下面的代码片段了解算法[1]
  • 在我们的例子中，排序列表的大小为 n1+n2。所以 O(n1+n2)
  • 生成的树将是二分搜索列表的概念 BST

O(n1+n2) 的三步结果为 O(n1+n2)

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

[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}