合并二叉搜索树

Question

我正在寻找一种合并两个BST的有效方法，因为我知道第一棵树中的元素都比第二棵树中的元素低。我看到了一些合并方法，但没有该功能，我认为这应该简化算法。

知道吗？

Answer 1

如果树不平衡，或者结果不应该平衡，这很容易：

without loss of generality - let the first BST be smaller (in size) than the second.
1. Find the highest element in the first BST - this is done by following the right son while it is still available. Let the value be x, and the node be v
2. Remove this item (v) from the first tree
3. Create a new Root with value x, let this new root be r
4. set r.left = tree1.root, r.right = tree2.root

（*） 如果第一个 BST 的大小大于第二个 BST，只需重复该过程以查找v作为第二个树中的最小节点。

（*）复杂性O(min{|T1|,|T2|})最坏情况（如果树非常不平衡，则找到最高的元素），O(log(min{|T1|,|T2|}))平均情况 - 如果树相对平衡。