如何有效地合并两个 BST?
如何合并两棵保持BST性质的二叉搜索树?
如果我们决定从树中取出每个元素并将其插入到另一个元素中，则该方法的复杂度将是 O(n1 * log(n2))，其中 n1 是我们分裂的树的节点数(比如 T1)，n2 是另一棵树的节点数(比如 T1>T2).此操作后，只有一个 BST 有 n1 + n2 个节点.
If we decide to take each element from a tree and insert it into the other, the complexity of this method would be O(n1 * log(n2)), where n1 is the number of nodes of the tree (say T1), which we have splitted, and n2 is the number of nodes of the other tree (say T2). After this operation only one BST has n1 + n2 nodes.
我的问题是:我们能做得比 O(n1 * log(n2)) 更好吗?
My question is: can we do any better than O(n1 * log(n2))?
推荐答案
Naaff 的回答有更多细节:
Naaff's answer with a little more details:
- 将 BST 展平为排序列表是 O(N)
- 这只是对整个树的有序"迭代.
- 同时做这件事是 O(n1+n2)
- 保持指向两个列表头部的指针
- 选择较小的头部并移动其指针
- 这就是归并排序的合并方式
- 请参阅下面的代码片段以了解算法[1]
- 在我们的例子中，排序列表的大小为 n1+n2.所以 O(n1+n2)
- 结果树将是二分搜索列表的概念 BST
三步 O(n1+n2) 结果为 O(n1+n2)
Three steps of O(n1+n2) result in O(n1+n2)
对于相同数量级的 n1 和 n2，这优于 O(n1 * log(n2))
For n1 and n2 of the same order of magnitude, that's better than O(n1 * log(n2))
[1] 从排序列表中创建平衡 BST 的算法(在 Python 中):
[1] Algorithm for creating a balanced BST from a sorted list (in 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}
相关文章