如何有效地合并两个BST？
如果我们决定从一棵树中取出每个元素并将其插入到另一个元素中，则此方法的复杂度将为O(n1 * log(n2))，其中n1是T1我们已拆分的树的节点数（例如），n2是的结点数。另一棵树（例如T2）。此操作后，只有一个BST具有n1 + n2节点。
我的问题是：我们能做得比O（n1 * log（n2））好吗？
回答：
纳夫的答案还有更多细节：
- 将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 * 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}
以上是 如何有效地合并两个BST？ 的全部内容， 来源链接： utcz.com/qa/423712.html
