如何在 O(log(n)) 中平衡这个 AVL 树？
How to balance this AVL Tree in O(log(n))?
假设您有 2 棵 AVL 树 U 和 V 以及一个元素 x，使得 U 中的每个元素 < x 并且 V 中的每个元素 > x。您将如何合并 U、V 和 x 以创建 AVL 树？什么算法会产生 O(log(n)) 时间复杂度？
所以我知道答案是您只需创建一个以 x 为根、U 为左 child 和 V 为右 child 的 BST，然后重新平衡。但是我如何证明这具有 O(log(n)) 复杂性？
如果两棵树的高度相同或最多相差一棵，则您的方法是正确的（不需要平衡）。但是，当它们相差更多时，情况并非如此。
我们可以递归地解决这个问题：
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)
请注意，我们在每次调用中最多执行恒定量的工作，外加可选的单个递归调用。因此复杂度为O(recursion_depth)。但是也应该很容易看出，递归深度受限于树高的差异U, V。而且每个都有 O(log n) 的高度，因此我们可以得出结论 merge 也是 O(log n)。
假设您有 2 棵 AVL 树 U 和 V 以及一个元素 x，使得 U 中的每个元素 < x 并且 V 中的每个元素 > x。您将如何合并 U、V 和 x 以创建 AVL 树？什么算法会产生 O(log(n)) 时间复杂度？
所以我知道答案是您只需创建一个以 x 为根、U 为左 child 和 V 为右 child 的 BST，然后重新平衡。但是我如何证明这具有 O(log(n)) 复杂性？
如果两棵树的高度相同或最多相差一棵，则您的方法是正确的（不需要平衡）。但是，当它们相差更多时，情况并非如此。
我们可以递归地解决这个问题：
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)
请注意，我们在每次调用中最多执行恒定量的工作，外加可选的单个递归调用。因此复杂度为O(recursion_depth)。但是也应该很容易看出，递归深度受限于树高的差异U, V。而且每个都有 O(log n) 的高度，因此我们可以得出结论 merge 也是 O(log n)。