27

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

如果我们决定从一棵树中取出每个元素并将其插入另一个元素，则此方法的复杂O(n1 * log(n2))性为另一棵树（比如）。在这个操作之后，只有一个 BST 有节点。n1T1n2T2n1 + n2

我的问题是：我们能比 O(n1 * log(n2)) 做得更好吗？

4

6 回答 6

28

纳夫的回答有更多细节：

  • 将 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}
于 2009-06-18T00:14:33.117 回答
21
  • Flatten trees into sorted lists.
  • Merge sorted lists.
  • Create tree out of merged list.

IIRC, that is O(n1+n2).

于 2009-06-17T17:43:17.473 回答
9

将两棵树展平为排序列表，合并列表然后创建一个新树怎么样？

于 2009-06-17T17:43:11.153 回答
1

乔纳森，

排序后，我们有一个长度为 n1+n2 的列表。用它构建二叉树需要 log(n1+n2) 时间。这与归并排序相同，只是在每个递归步骤中，我们不会像归并排序算法那样拥有 O(n1+n2) 项。所以时间复杂度是log(n1+n2)。

现在整个问题的复杂度是O(n1+n2)。

如果两个列表的大小相当，我也会说这种方法很好。如果大小无法比较，那么最好将小树的每个节点都插入到大树中。这将花费 O(n1*log(n2)) 时间。例如，如果我们有两棵树，一棵大小为 10，另一棵大小为 1024。这里 n1+n2 = 1034，其中 n1log(n2) = 10*10 = 100。所以方法必须取决于两棵树的大小。

于 2010-07-27T21:08:19.630 回答
0

O(n1 * log(n2)) 是平均情况，即使我们有 2 将任何未排序的列表合并到 BST 中。我们没有利用列表是排序列表或 BST 的事实。

根据我的说法，假设一个 BST 有 n1 个元素，另一个有 n2 个元素。现在将一个 BST 转换为 O(n1) 中的排序数组列表 L1。

合并 BST(BST, Array)

if (Array.size == 0) return BST if(Array.size ==1) 在 BST 中插入元素。返回 BST；

在数组中找到左元素< BST.rootnode 和右元素>=BST.rootnode 的索引，即Index。if(BST.rootNode.leftNode ==null ) //ie No left node { 将 Index 到 0 的所有数组插入到 BST 的左边 } else { Merged BST(BST.leftNode, Array{0 to Index}) }

if(BST.rootNode.rightNode ==null)//ie No right node { 将Index到Array.size的数组全部插入BST的右边} else { Merged BST(BST.rightNode, Array{Index to Array.size} ) }

返回 BST。

每次我们对数组和 BST 进行分区以处理子问题时，该算法将花费 << 时间而不是 O(n1 * log(n2))。

于 2010-08-30T10:12:43.920 回答
-1

这个想法是使用迭代中序遍历。我们为两个 BST 使用两个辅助堆栈。由于我们需要以排序形式打印元素，所以每当我们从任何树中获得较小的元素时，我们都会打印它。如果元素更大，则我们将其推回堆栈以进行下一次迭代。

于 2013-01-08T06:04:48.700 回答