我是自学AVL树的，我理解它背后的基本思想，但我只是想确保我的直觉是有效的:
我将检查它的左旋转-
所以，下面的情况很简单:
8
/
7 10
/
6
/
3
当我们加上3时，树重新平衡为:
8
/
6 10
/
3 7
但是旋转是基于3的加法还是子树的不平衡根植于7?它甚至是基于根植于8的树的不平衡吗?
在我看来，下面的例子是事情变得有点棘手的地方:
9
/
7 10
/
6 8
/
3
所以，在这种情况下，7处的子树在加上3时很好，所以子树不需要旋转。然而，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
}
}
提前感谢!
您发布的伪代码将正确地平衡树。也就是说，它的效率太低，不实用——请注意，您正在递归地探索整个树，试图进行再平衡操作，这将使所有插入和删除花费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，这意味着我们需要做一个旋转。查阅维基百科关于所有AVL树旋转的表格，我们可以看到我们的平衡因子是+2而左子结点的平衡因子是+1。这意味着我们做一个右旋转，把7拉到9上面，如下所示:
7(0)
/
6(+1) 9(0)
/ /
3(0) 8(0) 10 (0)
等voilà !树现在是平衡的。
注意，当我们执行这个修复过程时，我们不必遍历整个树。相反，我们所需要做的就是沿着访问路径查看并检查那里的每个节点。通常，在实现AVL树时，插入过程将执行以下操作:
- 如果树为空:
- 插入平衡因子为0的节点
- 返回树的高度增加了1。
- 否则:
- 如果插入的值与当前节点匹配，则不做任何操作。
- 否则，递归地将节点插入到适当的子树中，并获得树高度变化的量。
- 根据子树高度的变化量更新该节点的平衡因子
- 如果这要求一系列的旋转，执行它们。
- 返回树的高度变化。
由于所有这些操作都是局部的，因此完成的总工作量完全基于访问路径的长度，在这种情况下是O(log n)，因为AVL树总是平衡的。
希望这对你有帮助!
PS:你最初的例子是这棵树:
8
/
7 10
/
6
/
3
注意，这个树实际上不是一个合法的AVL树，因为根节点的平衡因子是+2。如果您始终使用AVL算法维护树平衡，您将永远不会遇到这种情况。