如何合并两个二叉搜索树并保持 BST 的属性？如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将为 O(n1 * log(...
如何合并两棵二叉搜索树并保持 BST 的属性？
如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将是 O(n1 * log(n2)) ， n1 其中 是已拆分的 T1 树（假设 ）的节点数 n2 是另一棵树（假设 ）的节点数 T2 。 经过此操作后，只有一个 BST 有 n1 + n2 节点。
我的问题是：我们能做得比 O(n1 * log(n2)) 更好吗？
Naaff 的回答更详细一些：
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}