小编典典

如何有效地合并两个BST?

c++

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

如果我们决定从一棵树中取出每个元素并将其插入到另一个元素中,则此方法的复杂度将为O(n1 * log(n2)),其中n1T1我们已拆分的树的节点数(例如),n2是的结点数。另一棵树(例如T2)。此操作后,只有一个BST具有n1 + n2节点。

我的问题是:我们能做得比O(n1 * log(n2))好吗?


阅读 147

收藏
2020-08-02

共1个答案

小编典典

纳夫的答案还有更多细节:

  • 将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}

2020-08-02