如何合并两个二叉搜索树并保持 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。因此,方法必须取决于两棵树的大小。