如何平衡大型 AVL 树？

Question

我正在尝试重新学习如何平衡 AVL 树。看了很多教程后，我以为我已经掌握了要点，但后来我遇到了一个特定的场景，现在我被难住了。

我正在使用数字

5, 2, 3, 9, 4, 1, 6, 8, 10, 7

构建一棵 AVL 树，并按该顺序插入。树一直平衡到 10 没有任何问题，但我的算法在添加 7 后无法平衡树。这是在添加 7 后平衡树之前的样子：

    3
  ┌─┴──┐
  2    8 <-- Unbalanced subtree
┌─┘  ┌─┴──┐
1    5    9
    ┌┴─┐  └─┐
    4  6   10
       └─┐
         7 <-- Node causing the tree to be unbalanced 

我从使用USFCA's AVL Tree Visualizer知道我的树在平衡后应该看起来像这样，但我不知道如何实现这个结果：

      5
   ┌──┴───┐
   3      8
  ┌┴─┐  ┌─┴──┐
  2  4  6    9
┌─┘     └─┐  └─┐
1         7   10

这个教程表明我应该对8进行左右旋转，这会导致与期望的结果不一致：

     8
   ┌─┴──┐
   3    9
  ┌┴─┐  └─┐
  2  4   10
┌─┘  └─┐
1      5
       └─┐
         6
         └─┐
           7

这是我用来确定给定节点使用哪些旋转的逻辑（让我知道是否应该包含我的旋转方法的代码 - 我不确定 MCVE 是否有必要）：

private void balance(Node node) {
    if (node == null)
        return;

    int balanceFactor = balanceFactor(node);
    if (balanceFactor > 1) {
        // Left subtree is heavier
        balanceFactor = balanceFactor(node.left);
        if (balanceFactor > 0) {
            rightRotate(node.left.left);
        } else {
            leftRotate(node.left.right);
            rightRotate(node.left);
        }
    } else if (balanceFactor < -1) {
        // Right subtree is heavier
        balanceFactor = balanceFactor(node.right);
        if (balanceFactor > 0) {
            leftRotate(node.right);
            rightRotate(node.right.left);
        } else {
            leftRotate(node.right);
        }
    }

    balance(node.parent);
}

在我看来，逻辑运行良好，直到根节点变得右重。

我需要采取哪些不同措施来平衡这棵树？

Answer 1

balanceFactor < -1

应在左/右和平衡因子比较方面镜像其他块的情况的代码块。目前情况并非如此。所以改成：

} else if (balanceFactor < -1) {
    // Right subtree is heavier
    balanceFactor = balanceFactor(node.right);
    if (balanceFactor <= 0) {
        leftRotate(node.right.right);
    } else {
        rightRotate(node.right.left);
        leftRotate(node.right);
    }
}

请注意，我使用了

<=

。这也可以在第一种情况下完成 (

>=

)，因为即使子项的平衡系数为零，旋转一次就足够了。

另请参阅有关重新平衡的维基百科。请注意，他们使用相反的符号来表示平衡因子。