既然我们已经证明了保持AVL树的平衡会大大提高性能，那我们就来看看如何在程序中向树中插入一个新的键值。因为所有新键都作为叶节点插入到树中，并且新叶的平衡因子为零，所以我们不对新插入的节点进行任何调整。但是一旦插入新叶子，我们必须更新其父节点的平衡因子。新叶子如何影响父节点的平衡因子取决于叶子节点是左孩子还是右孩子。如果新节点是右孩子，则父节点的平衡因子减1。如果新节点是左孩子，则父节点的平衡因子将增加1。这个关系可以递归地应用到新节点的前两个节点，并可能影响之前的每个节点，甚至是根节点。由于这是一个递归过程，让我们看一下更新平衡因子的两个基本条件：递归调用已经到达树的根部。父节点的平衡因子已调整为零。一旦子树的平衡因子为零，父节点的平衡因子就不会改变。我们将实现AVL树的子类BinarySearchTree。首先，我们将覆盖_put方法并编写一个新的辅助方法updateBalance。这些方法如清单1所示。除了第7行和第13行对updateBalance的调用外，您会注意到_put的定义与简单的二叉搜索树完全相同。清单1def_put(self,key,val,currentNode):ifkey1ornode.balanceFactor<-1:self.rebalance(node)returnifnode.parent!=None:ifnode.isLeftChild():node.parent.balanceFactor+=1elifnode.isRightChild():node.parent.balanceFactor-=1ifnode.parent.balanceFactor!=0:self.updateBalance(node.parent)updateBalance方法完成了大部分功能，实现了我们刚才提到的递归过程。rebalance方法首先检查当前节点是否不平衡以至于需要重新平衡（第16行）。如果当前节点需要重新平衡，那么只需要重新平衡当前节点，而不需要进一步更新父节点。如果当前节点不需要重新平衡，则需要调整父节点的平衡因子。如果父节点的平衡因子不为零，则算法通过递归调用父节点上的updateBalance方法递归到树的根。当需要重新平衡树时，我们该怎么做？高效的再平衡是让AVL树在不牺牲性能的情况下表现良好的关键。为了使AVL树恢复平衡，我们对树执行一次或多次“旋转”。要理解什么是旋转，让我们看一个非常简单的例子。考虑图3左侧的树。树是不平衡的，平衡因子为-2。为了平衡树，我们将根子树节点A向左旋转。图3：使用左旋转变换不平衡树要执行左旋转，我们需要执行以下操作：使右节点(B)成为子树的根。将旧根节点(A)移动到新根的左节点。如果新根（B）原来有左节点，则让原B的左节点成为新根左节点（A）的右节点。注意：由于新根（B）是A的右节点，此时移动A的右节点必须为空。我们可以不加思索地直接将正确的节点添加到移动的A中。虽然这个过程在概念上看起来很简单，但实现细节有点棘手，因为要保留二叉搜索树的所有属性，必须以绝对正确的顺序移动节点。此外，我们需要确保所有父节点都已更新。让我们看一个稍微复杂的树来说明右旋。图4的左侧显示了一个“左重”树，其根的平衡因子为2。要执行正确的右旋，我们需要执行以下操作：使左节点(C)成为子树的根.将旧根(E)移动到新根的右节点。如果新根（C）原来有一个右节点（D），则设D为新根右节点（E）的左节点。注意：由于新根（C）是E的左节点，所以移动后E的左节点必须为空。这时候就可以直接在移动后的E上增加一个左节点。图4：使用右旋转变换一棵不平衡树了解了旋转的过程，也明白了如何去做之后，让我们看一下代码。清单2显示了左右旋转的代码。在第2行，我们创建了一个临时变量来跟踪新子树的根。正如我们之前所说，新根是旧根的右节点。现在，正确的节点已经存储在这个临时变量中。我们用新根的左节点替换旧根的右节点。下一步是调整两个节点的父指针。如果newRoot最初有一个左节点，则左节点的新父节点成为旧根节点。新根的父级将成为旧根的父级。如果旧根是整棵树的根，那我们就得让整棵树的根指向这个新根。如果旧根是左节点，则将左节点的父节点更改为新根；否则，我们将右节点的父节点更改为新的根节点（第10-13行）。最后我们将旧根的父节点设置为新根。这里有很多复杂的中间过程，建议大家一边看函数代码一边看图3。rotateRight方法和rotateLeft是对称的，请自行研究rotateRight的代码。清单2defrotateLeft(self,rotRoot):newRoot=rotRoot.rightChildrotRoot.rightChild=newRoot.leftChildifnewRoot.leftChild!=None:newRoot.leftChild.parent=rotRootnewRoot.parent=rotRoot.parentifrotRoot.isRoot():self.root=newRootelse:ifrotRoot.isLeftChild():rotRoot.parent.leftChild=newRootelse:rotRoot.parent.rightChild=newRootnewRoot.leftChild=rotRootrotRoot.parent=newRootrotRoot.balanceFactor=rotRoot.balanceFactor+1-min(newRoot.balanceFactor,0)newRoot.balanceFactor=newRoot.balanceFactor+1+max(rotRoot.balanceFactor,0)最后，第16-17行需要一些解释。这两行我们更新旧根和新根的平衡因子。由于其他操作会移动整个子树，因此移动子树内节点的平衡因子不受旋转影响。但是我们如何在不重新计算新子树高度的情况下更新平衡因子呢？下面的推导会告诉你这段代码是正确的。图5：左旋转图5显示了左旋转。B、D是中心节点，A、C、E是它的子树。设hX表示以X为根的子树的高度。根据定义我们知道：newBal(B)=hA?hColdBal(B)=hA?hD但是我们知道D的高度也可以由1+max(hC,hE)给出，即D的高度为2将较大的子树的高度增加1。记住，hC和hE没有改变。因此，将上式代入第二个方程，可以得到：oldBal(B)=hA?(1+max(hC,hE))，然后对两个方程进行差分。下面是求差的步骤，newBal(B)用一些代数的方法来化简方程。beginssplitnewBal(B)?oldBal(B)=hA?hC?(hA?(1+max(hC,hE)))newBal(B)?oldBal(B)=hA?hC?hA+(1+max(hC,hE))newBal(B)?oldBal(B)=hA?hA+1+max(hC,hE)?hCnewBal(B)?oldBal(B)=1+max(hC,hE)?hC接下来我们移动oldBal(B)到等式的右侧并使用max(a,b)?c=max(a?c,b?c)。newBal(B)=oldBal(B)+1+max(hC?hC,hE?hC)但hE?hC等价于?oldBal(D)。所以我们说：max(?a,?b)=?min(a,b)，newBal(B)的推导可以通过以下步骤完成：newBal(B)=oldBal(B)+1+max(0,?oldBal(D))newBal(B)=oldBal(B)+1?min(0,oldBal(D))现在方程的所有项都是已知的。如果我们记得B是rotRoot，D是newRoot，我们可以看到这与第16行的语句完全匹配：rotRoot.balanceFactor=rotRoot.balanceFactor+1-min(0,newRoot.balanceFactor)更新节点D，并且右-rotated平衡因子的方程推导是类似的。到现在为止，您可能认为所有步骤都已完全理解。我们知道如何以及何时左右旋转，但请看图6。由于节点A的平衡因子为-2，因此我们应该进行左旋转。但是当我们向左旋转时会发生什么？图6：更难平衡的不平衡树图7：所示树在向左旋转后仍然不平衡。如果我们做一个正确的旋转来尝试重??新平衡，我们就会回到我们开始的地方。为了解决这个问题，我们必须使用以下规则：如果子树需要向左旋转使其平衡，首先检查右节点的平衡因子。如果右节点是左重的，则将右节点向右旋转，然后将原始节点向左旋转。如果子树需要向右旋转使其平衡，首先检查左节点的平衡因子。如果左节点为右重，则将左节点向左旋转，然后将原节点向右旋转。图8显示了这些规则如何解决我们在图6和图7中遇到的问题。首先，围绕C向右旋转，树变成更好的形状；然后，围绕A向左旋转，整个子树恢复平衡。图8：右旋转后左旋转实现这些规则的代码可以在我们的“重新平衡”方法中找到，如清单3所示。上面的第一条规则是从第二行if语句开始实现的。第二条规则由第8行的elif语句实现。清单3defrebalance(self,node):ifnode.balanceFactor<0:ifnode.rightChild.balanceFactor>0:self.rotateRight(node.rightChild)self.rotateLeft(node)else:self.rotateLeft(node)elifnode.balanceFactor>0:ifnode.leftChild.balanceFactor<0:self.rotateLeft(node.leftChild)self.rotateRight(node)else:self.rotateRight(node)通过保持树的平衡，我们可以保证get方法的运行时间复杂度为O(log2n)。但是问题是put方法的时间复杂度是多少呢？我们分解put操作。由于每个新节点都是作为叶节点插入的，因此每轮更新所有父节点的平衡因子最多需要log2n次操作，每层执行一次。如果子树不平衡，则最多需要两次旋转才能使子树恢复平衡。但是每次旋转操作的复杂度都是O(1)，所以即使我们进行put操作，最终的复杂度还是O(log2n)。
