二叉搜索树的反例总是可以在对数时间内连接

Question

基本上，问题是不能在对数时间内合并的两个平衡二叉搜索树的例子是什么？

动机：

假设我们有两个平衡二叉搜索树 T1 和 T2，分别有 n 和 m 节点。它们的深度是对数的（分别为O（log n）和O（log m））。假设 n <= m.

如果T1和T2的取值区间不重叠，即max T1 < min T2 (or max T2 < min T1), joining those trees can be really efficient (O(log m)) if we use, e.g., Splay trees or Treaps.

否则，我所知道的最好的算法是线性 O(n + m) 算法（按顺序遍历两棵树，然后合并值并创建新的平衡树）。

这比对数差很多，但是（四处乱涂）我找不到两棵大小为 n 的树（对于一些任意大的 n），在那里有必要使用这个算法。

Answer 1

制作一棵长度为

m

的平衡二叉树，其中偶数在

2..2m

范围内。使另一个平衡二叉树的长度为

m

范围内的奇数

1..2m-1

.

合并的二叉树需要以

O(m)

节点结束，这些节点的值来自第二棵树，而第二棵树的子节点来自第一棵树。因此，您不能在少于

O(m)

的时间内合并。