如何合并两个二叉搜索树并保持 BST 的属性?如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中,则此方法的复杂度将为 O(n1 * log(...
如何合并两棵二叉搜索树并保持 BST 的属性?
如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中,则此方法的复杂度将是 O(n1 * log(n2))
, n1
其中 是已拆分的 T1
树(假设 )的节点数 n2
是另一棵树(假设 )的节点数 T2
。 经过此操作后,只有一个 BST 有 n1 + n2
节点。
我的问题是:我们能做得比 O(n1 * log(n2)) 更好吗?