最近几天在 AVL 树上工作。我找不到任何在 log(N) 时间内有效的伪代码。我想避免(如果可能的话)遍历树并将每个节点添加到其他节点的过程。
最佳答案
这不能在亚线性时间内完成。
证明:
假设您可以在 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
关于java - lg(N) 时间内的 AVL 树连接操作算法或伪代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32496296/