我遇到问题的问题如下 .
假设您有两个不同的二叉搜索树A和B，并且您以某种方式知道A中的最大元素小于B中的最小元素 . 假设高度（A）<height（B） . 提供一种破坏性地创建二进制搜索树的算法，该搜索树将包含A∪B中的所有元素并且在时间O（高度（A））中运行 .
因此，由于A中的最大元素小于B中的最小元素，这意味着A中的每个元素都小于B中的每个元素 . 在新树中，左侧应为树A，右侧应为树B.但是你如何在时间O（高度（A））中以编程方式进行合并？你也不需要循环通过B吗？ （这将使其成为O（高度（A）高度（B））
2 回答
那么根节点的元素是什么？
如果你是对的，那么你可以在O（1）中执行：
node(X, A, B)（用于创建具有元素X，左子树A和右子树B的节点的伪代码） .如果"loop through B"表示访问所有元素，则需要更长时间 . 在 balancer 搜索树中，
height(B)与log(size(B))成比例 .你可以做的是走在A的最右边的分支（这需要
O(height(A))步） . 找到结束后，在那里插入B（通过分配node.right，在O(1)中） .正如当前所述的问题，您可以将B树的根作为A树的最大元素（最右边的叶子）的右子项追加 .
复杂性将是O（高度（A）） - 找到叶子 .