如何在O(log(n))中平衡此AVL树

Question

假设有两个AVL树U和V以及一个元素x，使得U中的每个元素都<x，并且V中的每个元素都>x.如何合并U、V和x来创建AVL树？什么算法会产生O(log(n((时间复杂性？

所以我知道答案是，你只需创建一个BST，x为根，U为左子，V为右子，然后重新平衡。但是，我如何证明这具有O(log(n((复杂性？

Answer 1

如果两棵树的高度相同或最多相差一棵，则您的方法是正确的(不需要平衡(。然而，当他们之间的差异更大时，事实并非如此。

我们可以递归地解决这个问题：

def merge(U, x, V):
if h(V) > h(U) + 1:
V.left = merge(U, x, V.left)
# Note that h(V.left) can only increase, by at most 1,
# so one rotation can fix all issues.
if h(V.left) > h(V.right) + 1:
V = rotate-right(V)
return V
if h(U) > h(V) + 1:
U.right = merge(U.right, x, V)
if h(U.right) > h(U.left) + 1:
U = rotate-left(U)
return U
return new-node(x, U, V)

请注意，我们在每个调用中最多执行恒定数量的工作，外加一个可选的单个递归调用。因此复杂性为CCD_ 1。但也应该很容易看出，递归深度受到树的高度差U, V的限制。其中每一个的高度都是O(log n)，因此我们可以得出merge也是O(log n)。