algorithm - 您如何知道在 AVL 树中的何处执行旋转？

Question

所以我在自学 AVL 树，我理解它背后的基本思想，但我只是想确保我实际实现它的直觉是有效的:

我会用左旋转来检查它-

所以，下面的情况很简单:

      8
     / \
    7   10
   /
  6
 /
3

当我们添加 3 时，树将自身重新平衡为:

    8
   / \
  6   10
 / \
3   7

但是旋转是基于3的加法还是以7为根的子树的不平衡？它甚至是基于以 8 为根的树的不平衡吗？

在我看来，下面的例子有点棘手:

      9
     / \
    7   10
   / \
  6   8
 /
3

所以，在这种情况下，当添加 3 时，位于 7 的子树就可以了，因此该子树不需要旋转。然而，9 处的树由于添加了 3 而变得不平衡，因此我们将旋转基于 9。我们得到:

      7
     / \
    6   9
   /   / \
  3   8   10

因此，在编写我的代码时(我很快就会这样做)，下面的代码(从小的子树开始逐步扩展到更大的子树)是否可以达到目的？

伪代码:

function balanceTree(Node n){

  if (n is not null){

    balanceTree(n.rightchild);
    balanceTree(n.leftchild);
  }

  if (abs(balanceFactor(n))>1){

    rotateAsNeeded(n);// rotate based on balance factor

  }

}

提前致谢!

Answer 1

您发布的伪代码将正确平衡一棵树。也就是说，它的效率太低而不实用 - 请注意，您正在递归地探索整棵树以尝试进行重新平衡操作，这将使所有插入和删除都花费 O(n) 时间，从而消除了拥有一个的所有效率 yield 平衡树。

AVL 树背后的想法是全局重新平衡树可以通过迭代应用局部旋转来完成。换句话说，当您进行插入或删除并需要进行树旋转时，这些旋转不会出现在树中的随机位置。它们将始终出现在您插入或删除节点时采用的访问路径上。

例如，您对将值 3 插入这棵树感到好奇:

      9
     / \
    7   10
   / \
  6   8

让我们首先写出与每个节点相关的平衡因子的差异(AVL 树节点存储此信息至关重要，因为它可以有效地进行插入和删除):

           9(+1)
         /       \
       7 (0)    10 (0)
      / \
  6(0)   8(0)

现在让我们看看当我们插入 3 时会发生什么。这会将 3 放在这里:

           9(+1?)
          /       \
        7 (0?)    10 (0)
       /   \
   6(0?)   8(0)
   /
 3(0)

请注意，我已经用 ? 标记了访问路径上的所有节点，因为我们不再确定它们的平衡因子是多少。由于我们为 6 插入了一个新的 child ，这将 6 节点的平衡因子更改为 +1:

           9(+1?)
          /       \
        7 (0?)    10 (0)
       /   \
   6(+1)   8(0)
   /
 3(0)

同理，7的左子树的高度增长了，所以它的平衡因子应该增加:

           9(+1?)
          /       \
        7 (+1)    10 (0)
       /   \
   6(+1)   8(0)
   /
 3(0)

最后，9 的左子树增长了 1，这给出了:

           9(+2!)
          /       \
        7 (+1)    10 (0)
       /   \
   6(+1)   8(0)
   /
 3(0)

而这里我们发现9的平衡因子为+2，这意味着我们需要做一个旋转。咨询Wikipedia's great table of all AVL tree rotations ，我们可以看到我们处于平衡因子为 +2 的情况，其中左 child 的平衡因子为 +1。这意味着我们进行右旋并将 7 拉到 9 上方，如下所示:

        7(0)
       /   \
   6(+1)     9(0)
   /       /   \
 3(0)    8(0)   10 (0)

Et voilà!现在树已经平衡了。

请注意，当我们执行此修复过程时，我们不必查看整棵树。相反，我们需要做的就是沿着访问路径查看并检查那里的每个节点。通常，在实现 AVL 树时，您的插入过程将执行以下操作:

• 如果树为空:
  • 插入平衡因子为0的节点。
  • 返回树高增加了1。
• 否则:
  • 如果要插入的值与当前节点匹配，什么也不做。
  • 否则，递归地将节点插入到正确的子树中，并获取树高变化的量。
  • 根据子树高度的变化量更新该节点的平衡因子。
  • 如果这要求进行一系列轮换，请执行它们。
  • 返回这棵树的高度变化。

由于所有这些操作都是本地的，因此完成的总工作量完全基于访问路径的长度，在本例中为 O(log n)，因为 AVL 树始终是平衡的。

希望这对您有所帮助!

---

PS:你最初的例子是这棵树:

      8
     / \
    7   10
   /
  6
 /
3

请注意，这棵树实际上不是合法的 AVL 树，因为根节点的平衡因子是 +2。如果您始终使用 AVL 算法来保持树平衡，就永远不会遇到这种情况。