java - lg(N) 时间内的 AVL 树连接操作算法或伪代码

Question

最近几天在 AVL 树上工作。我找不到任何在 log(N) 时间内有效的伪代码。我想避免(如果可能的话)遍历树并将每个节点添加到其他节点的过程。

Answer 1

这不能在亚线性时间内完成。

证明:

假设您可以在 f(n) 中合并两棵 avl 树时间是次线性的，我们提出以下合并排序变体，以从未排序的元素列表中创建排序的 AVL 树:

mergeSort(arr,l,r):
    if (r-l < 2):
          return new AVLTree(arr[l])
    mid = l + (r-l)/2
    T1 = mergeSort(arr,l,mid)
    T2 = mergeSort(arr,mid+1,r)
    return merge(T1,T2)

这基本上是归并排序的一种变体，正确性证明是归纳式的，类似于归并排序。

复杂度:

T(n) = 2T(n/2) + f(n)

使用 master theorem case 1与 a=b=2 , 和一些 c<1 (因为 f(n) 是次线性的):

案例条件适用，因为 c < 1 = log_2(2) = log_b(a) , 所以我们可以找到一些 c这样 f(n)在O(n^c) , 对于一些 c<1 .

然后，定理告诉我们T(n)在Theta(n^(log_b(a)) = Theta(n) .

但这意味着我们已经创建了一个线性时间排序算法，并且由于这样的算法不存在，因为排序是 Omega(nlogn) ，我们不能在亚线性时间内运行合并。

QED