为了让AVL树恢复平衡，主要手段是将不平衡的子树进行旋转。通过一个例子来理解什么是旋转，下图是通过左旋让失衡的树恢复平衡，左边的树失去平衡，平衡因子为-2，为了恢复平衡，围绕节点A为根节点的子树做一次左旋。
本质上，左旋包括以下步骤：
（1）将右子节点（节点B）提升为子树的根节点；
（2）将旧根节点（节点A）作为新根节点（节点B）的左子节点；
（3）如果新根节点（节点B）已经有左子节点，就将此节点设置为A的右子节点(A的右子节点一定有空)。
左旋看起来很简单，但代码细节有些复杂，因为要将节点挪来挪去以保证二叉搜索树的性质。另外，还要保证正确地更新父指针。
再通过一颗复杂的树理解右旋过程：
下图是通过右旋让失衡的树恢复平衡，左边是一棵左倾的树，平衡因子为2。右旋步骤如下：
（1）将左子节点（节点C）提升为子树的根节点；
（2）将旧根节点（节点E）作为新根节点的右子节点；
（3）如果新根节点（节点C）已经有一个右子节点（节点D），将其作为新右子节点（节点E）的左子节点。
左旋：
defrotateLeft(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+l-min(newRoot.balanceFactor,0)newRoot.balanceFactor=newRoot.balanceFactor+1+max(rotRoot.balanceFactor,0)预览时标签不可点收录于话题#个上一篇下一篇