你怎么知道在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)时间,从而消耗掉所有效率增益.平衡的树.

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的左子树增长了一个,这给出了:

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

在这里我们发现9的平衡因子为+2,这意味着我们需要进行轮换.咨询维基百科所有AVL树旋转的伟大表格,我们可以看到我们的平衡因子为+2,左边的孩子的平衡因子为+1.这意味着我们进行了正确的旋转并将7拉到了9之上,如下所示:

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

Etvoilà! 树现在平衡了.

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

• 如果树为空:
  • 插入余额为0的节点.
  • 返回树高增加1.
• 除此以外:
  • 如果要插入的值与当前节点匹配,则不执行任何操作.
  • 否则,递归地将节点插入到适当的子树中,并获得树高已经改变的量.
  • 根据子树高度更改的量更新此节点的平衡因子.
  • 如果要求进行一系列旋转,请执行它们.
  • 返回此树高度的结果更改.

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

希望这可以帮助!

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

      8
     / \
    7   10
   /
  6
 /
3

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