30

所以我在自学 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

  }

}

提前致谢！

4

1 回答 1

33

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

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 插入了一个新子节点，因此这会将 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，而左孩子的平衡因子为 +1。这意味着我们向右旋转并将 7 拉到 9 上方，如下所示：

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

瞧！ 树现在是平衡的。

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

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

由于所有这些操作都是本地的，所以完成的总工作完全基于访问路径的长度，在这种情况下是 O(log n)，因为 AVL 树总是平衡的。

希望这可以帮助！

PS：您最初的示例是这棵树：

      8
     / \
    7   10
   /
  6
 /
3

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

于 2013-06-21T19:25:26.957 回答