如何合并两个BST的效率？ [英] How to merge two BST's efficiently?

问题描述

如何合并两个二叉搜索树保持BST？财产

如果我们决定把每个元素从一棵树，把它插入到另一个时，这种方法的复杂性将是 O（N1 *日志（N2）），其中， N1 是树的节点（比如 T1 ），这是我们分裂，而<$ C的数量$ C> N2 是其他树的节点的数量（比如 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 *日志（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）
  • Flattening a BST into a sorted list is O(N)
    • It's just "in-order" iteration on the whole tree.
    • Doing it for both is O(n1+n2)
    • 请指向两个列表的头
    • 选择较小的头部和推进其指针
    • 这是怎样的合并排序合并工作原理
    • 在中间的价值将是根，和递归。
    • 在我们的例子中排序列表的大小为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更好的（N *日志（N2））

    For n1 and n2 of the same order of magnitude, that's better than O(n1 * log(n2))

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