在O（logn）时间内将两个AVL树连接在一起的算法

Question

因此，我试图找出一种算法，以在O（logn）时间内将2个AVL树连接在一起，其中n是两棵树中整数的总数，并且也是奇数。在此问题中，树中的整数彼此不同。此外，树的每个节点都存储以其为根的子树的大小。我当时正在考虑将较小的树的元素添加到较大的树中，但是我不确定如何证明这将花费O（logn）时间。有人对我该如何处理有任何建议吗？

Answer 1

这是不可能的。

证明：假设您有一种算法可以在O(logn)中加入2个AVL搜索树，并将其设为A(T1,T2)

我们现在代表一种新的排序算法：Sort(A)

Sort(A):
  Let T_i be an AVL tree consisting only of A_i  // O(1) n times, total O(n).
  curr_size = 1
  while curr_size < size(A):
    Let T_i, T_j be two trees of size curr_size  // O(1)
    // Assume without loss of generality i < j.
    if there are such T_i,T_j:
      T_i = A(T_i,T_j)  // O(log(curr_size))
    else:
      curr_size = curr_size * 2  // O(1)
  return in_order(T_0)  // O(n) by in-order traversal.

算法复杂度是：

T(n) = n/2 * log(2) + n/4 * log(4) + n/8 * log(8) + ... + 2*log(n/2) + log(n)

说明

首先，我们需要将所有大小为1的树合并为大小为2的树。这需要进行n / 2个合并，每个合并都需要O（log（2））。接下来，将生成的n / 2棵树合并为大小为4的树。这完成了n / 4个，每个O（log4），...最后，我们有两棵树，我们将它们合并一次，并且取O（n）。

这给我们公式：

T(n) = sum (n/2^i * log(2^i)) for i=1,2,3,...,logn

我们可以做更多的代数运算，但是我采取了一条捷径并将其输入到Wolfram alpha，这给了我们：

T(n) = 2n -log(n) -2

由于上面是线性的，这意味着我们的通用排序算法Sort（A）是线性的。

但是排序是Omega(nlogn)。

这意味着有问题-因此，假设存在这样一种算法A(T1,T2)，且复杂度为O(logn)是错误的。

QED