算法 - 如何有效地连接两个二叉搜索树？

Question

我不是问如何合并两个二叉搜索树,因为这个问题如何有效地合并两个BST？

我真的在问如何连接两棵树.因此,如果树A的所有节点都小于树B的任何节点,我们可以连接两棵树.但我该如何有效地做到这一点？

我的想法是找到树B的最小值,然后让树A成为最小的左子(树B).

这很简单,时间也是O(height of B).

但我想这个解决方案有一些问题:

1. 它可能导致最终的大树不再平衡
2. 如果最坏的情况是运行时间O(h),h那么两棵树的最大高度在哪里呢？

实际上," 算法设计手册 "这本书有这个消费税.我的简单解决方案是否足以进行此练习？

连接操作需要两组S1和S2,其中S1中的每个键都小于S2中的任何键,并将它们合并在一起.给出一种算法将两个二叉搜索树连接成一个二叉搜索树.最坏情况下的运行时间应为O(h),其中h是两棵树的最大高度.

谢谢

Answer 1

设A是较小的集合.假设x = maximum_element(A)和y = minimum_element(B).

我们知道x <y.取一个键值等于的节点,z = (x+y)/2使A为左子树,B为右子树.z从此BST中删除添加的节点(带密钥).