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

Question

我不是问如何合并两个二叉搜索树，就像这个问题一样How to merge two BST's efficiently?

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

我的想法是找到树B的最小值，然后让树A成为最小值(树B)的左 child 。

这很简单，时间是O(height of B)。

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

1. 可能会导致最终的大树不再平衡
2. 如果最坏情况下的运行时间是 O(h)，其中 h 是两棵树的最大高度怎么办？

实际上，“Algorithm Design Manual”这本书有这个消费税。我的简单解决方案是否足以完成此练习？

A concatenate operation takes two sets S1 and S2, where every key in S1 is smaller than any key in S2, and merges them together. Give an algorithm to concatenate two binary search trees into one binary search tree. The worst-case running time should be O(h), where h is the maximal height of the two trees.

谢谢

Answer 1

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

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