如何合并两个二叉搜索树并保持 BST 的属性？如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将为 O(n1 * log(...
如何合并两棵二叉搜索树并保持 BST 的属性？
如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将是 O(n1 * log(n2)) ， n1 其中 是已拆分的 T1 树（假设 ）的节点数 n2 是另一棵树（假设 ）的节点数 T2 。 经过此操作后，只有一个 BST 有 n1 + n2 节点。
我的问题是：我们能做得比 O(n1 * log(n2)) 更好吗？
乔纳森，
排序后，我们得到一个长度为 n1+n2 的列表。用它构建二叉树需要 log(n1+n2) 时间。这与归并排序相同，只是在每个递归步骤中，我们不会像归并排序算法那样有 O(n1+n2) 项。因此时间复杂度为 log(n1+n2)。
现在整个问题的复杂度为O(n1+n2)。
另外，如果两个列表的大小相当，我会说这种方法很好。如果大小不具可比性，那么最好将小树的每个节点插入大树中。这将花费 O(n1*log(n2)) 时间。例如，如果我们有两棵树，一棵树的大小为 10，另一棵树的大小为 1024。这里 n1+n2 = 1034，而 n1log(n2) = 10*10 = 100。因此，方法必须取决于两棵树的大小。
