如何有效地合并两个 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}
  

  这篇关于如何有效地合并两个 BST?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！