如何有效地合并两个BST？

Question

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

如果我们决定从树上取每个元素,并将其插入到另一个中,这种方法的复杂性将是O(n1 * log(n2))其中n1的(比如树的节点数量T1),这是我们分裂,并且n2是节点的数量另一棵树(比如说T2).在此操作之后,只有一个BST具有n1 + n2节点.

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

Answer 1

Naaff回答了一些细节:

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

Answer 2

• 将树拼成分类列表.
• 合并排序列表.
• 从合并列表中创建树.

IIRC,即O(n1 + n2).

Answer 3

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