如何合并两个二叉搜索树并保持 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}