如何合并两个二叉搜索树并保持 BST 的属性？如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将为 O(n1 * log(...

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

如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将是 O(n1 * log(n2)) ， n1 其中 是已拆分的 T1 树（假设 ）的节点数 n2 是另一棵树（假设 ）的节点数 T2 。 经过此操作后，只有一个 BST 有 n1 + n2 节点。

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