平衡二叉搜索树
在 6.7 节中，我们了解了二叉搜索树的构建过程。我们已经知道，当二叉搜索树不平衡时，get 和 put 等操作的性能可能降到 \$O(n)\$。本节将介绍一种特殊的二叉搜索树，它能自动维持平衡。这种树叫作 AVL 树，以其发明者 G.M.Adelson-Velskii 和 E.M.Landis 的姓氏命名。
AVL 树实现映射抽象数据类型的方式与普通的二叉搜索树一样，唯一的差别就是性能。实现 AVL 树时，要记录每个节点的平衡因子。我们通过查看每个节点左右子树的高度来实现这一点。更正式地说，我们将平衡因子定义为左右子树的高度之差。
balance Factor=height (left SubTree)-height(right SubTree)
根据上述定义，如果平衡因子大于零，我们称之为左倾；如果平衡因子小于零，就是右倾；如果平衡因子等于零，那么树就是完全平衡的。为了实现AVL树并利用平衡树的优势，我们将平衡因子为 -1、0 和 1 的树都定义为平衡树。一旦某个节点的平衡因子超出这个范围，我们就需要通过一个过程让树恢复平衡。图6-26 展示了一棵右倾树及其中每个节点的平衡因子。
AVL树的性能
我们先看看限定平衡因子带来的结果。我们认为，保证树的平衡因子为 -1、0 或 1，可以使关键操作获得更好的大 O 性能。首先考虑平衡因子如何改善最坏情况。有左倾与右倾这两种可能性。如果考虑高度为 0、1、2 和 3 的树，图6-27 展示了应用新规则后最不平衡的左倾树。
查看树中的节点数之后可知，高度为 0 时有 1 个节点，高度为 1 时有 2 个节点（1 + 1= 2），高度为 2 时有 4 个节点（1 + 1 + 2 = 4），高度为 3 时有 7 个节点（1 + 2 + 4 = 7）。也就是说，当高度为 h 时，节点数 Nh 是：
你或许觉得这个公式很眼熟，因为它与斐波那契数列很相似。可以根据它推导出由AVL 树的节点数计算高度的公式。在斐波那契数列中，第 i 个数是：
\$F_1 = 1\$
\$F_i = F_(i-1) + F_(i-2) , i >= 2\$
一个重要的事实是，随着斐波那契数列的增长，Fi/Fi-1 逐渐逼近黄金分割比例 \$Φ,Φ=(1+sqrt(5))/2\$。如果你好奇这个等式的推导过程，可以找一本数学书看看。我们在此直接使用这个等式，将 Fi 近似为 \$Φ^i/sqrt(5)\$。由此，可以将 Nh 的等式重写为：
\$N_h=F_(h+2)-1，h>=1\$
用黄金分割近似替换，得到：
移项，两边以 2 为底取对数，求 h，得到：
在任何时间，AVL 树的高度都等于节点数取对数再乘以一个常数（1.44）。对于搜索 AVL 树来说，这是一件好事，因为时间复杂度被限制为 \$O(log N)\$。
AVL树的实现
我们已经证明，保持 AVL 树的平衡会带来很大的性能优势，现在看看如何往树中插入一个键。所有新键都是以叶子节点插入的，因为新叶子节点的平衡因子是零，所以新插节点没有什么限制条件。但插入新节点后，必须更新父节点的平衡因子。新的叶子节点对其父节点平衡因子的影响取决于它是左子节点还是右子节点。如果是右子节点，父节点的平衡因子减一。如果是左子节点，则父节点的平衡因子加一。这个关系可以递归地应用到每个祖先，直到根节点。既然更新平衡因子是递归过程，就来检查以下两种基本情况：
-
递归调用抵达根节点；
-
父节点的平衡因子调整为零；可以确信，如果子树的平衡因子为零，那么祖先节点的平衡因子将不会有变化。
我们将 AVL 树实现为 BinarySearchTree 的子类。首先重载 _put 方法，然后新写 updateBalance 辅助方法，如代码清单6-37 所示。可以看到，除了在第 8 行和第 15 行调用 updateBalance 以外，_put 方法的定义和代码清单6-25 中的几乎一模一样。
def _put(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,parent=currentNode)
self.updateBalance(currentNode.leftChild)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,parent=currentNode)
self.updateBalance(currentNode.rightChild)
def updateBalance(self,node):
if node.balanceFactor > 1 or node.balanceFactor < -1:
self.rebalance(node)
return
if node.parent != None:
if node.isLeftChild():
node.parent.balanceFactor += 1
elif node.isRightChild():
node.parent.balanceFactor -= 1
if node.parent.balanceFactor != 0:
self.updateBalance(node.parent)新方法 updateBalance 做了大部分工作，它实现了前面描述的递归过程。updateBalance 方法先检查当前节点是否需要再平衡（第 18 行）。如果符合判断条件，就进行再平衡，不需要更新父节点；如果当前节点不需要再平衡，就调整父节点的平衡因子。如果父节点的平衡因子非零，那么沿着树往根节点的方向递归调用 updateBalance 方法。
如果需要进行再平衡，该怎么做呢？高效的再平衡是让 AVL 树发挥作用同时不损性能的关键。为了让 AVL 树恢复平衡，需要在树上进行一次或多次旋转。
要理解什么是旋转，来看一个简单的例子。考虑图 6-28 中左边的树。这棵树失衡了，平衡因子是 -2。要让它恢复平衡，我们围绕以节点 A 为根节点的子树做一次左旋。
本质上，左旋包括以下步骤。
-
将右子节点（节点 B）提升为子树的根节点。
-
将旧根节点（节点 A）作为新根节点的左子节点。
-
如果新根节点（节点 B）已经有一个左子节点，将其作为新左子节点（节点 A）的右子节点。注意，因为节点 B 之前是节点 A 的右子节点，所以此时节点 A 必然没有右子节点。因此，可以为它添加新的右子节点，而无须过多考虑。
左旋过程在概念上很简单，但代码细节有点复杂，因为需要将节点挪来挪去，以保证二叉搜索树的性质。另外，还要保证正确地更新父指针。
我们来看一棵稍微复杂一点的树，并理解右旋过程。图6-29 左边的是一棵左倾的树，根节点的平衡因子是 2。右旋步骤如下。
-
将左子节点（节点 C）提升为子树的根节点。
-
将旧根节点（节点 E）作为新根节点的右子节点。
-
如果新根节点（节点 C）已经有一个右子节点（节点 D），将其作为新右子节点（节点 E）的左子节点。注意，因为节点 C 之前是节点 E 的左子节点，所以此时节点 E 必然没有左子节点。因此，可以为它添加新的左子节点，而无须过多考虑。
了解旋转的基本原理之后，来看看代码。代码清单6-38 给出了左旋的代码。第 2 行创建一个临时变量，用于记录子树的新根节点。如前所述，新根节点是旧根节点的右子节点。既然临时变量存储了指向右子节点的引用，便可以将旧根节点的右子节点替换为新根节点的左子节点。
下一步是调整这两个节点的父指针。如果新根节点有左子节点，那么这个左子节点的新父节点就是旧根节点。将新根节点的父指针指向旧根节点的父节点。如果旧根节点是整棵树的根节点，那么必须将树的根节点设为新根节点；如果不是，则当旧根节点是左子节点时，将左子节点的父指针指向新根节点；当旧根节点是右子节点时，将右子节点的父指针指向新根节点（第 10～13 行）。最后，将旧根节点的父节点设为新根节点。这一系列描述很复杂，所以建议你根据图 6-28 的例子运行一遍函数。rotateRight 与 rotateLeft 对称，所以留作练习。
代码清单6-38 左旋
def rotateLeft(self,rotRoot):
newRoot = rotRoot.rightChild
rotRoot.rightChild = newRoot.leftChild
if newRoot.leftChild != None:
newRoot.leftChild.parent = rotRoot
newRoot.parent = rotRoot.parent
if rotRoot.isRoot():
self.root = newRoot
else:
if rotRoot.isLeftChild():
rotRoot.parent.leftChild = newRoot
else:
rotRoot.parent.rightChild = newRoot
newRoot.leftChild = rotRoot
rotRoot.parent = newRoot
rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)第 16～19 行需要特别解释一下。这几行更新了旧根节点和新根节点的平衡因子。由于其他移动操作都是针对整棵子树，因此旋转后其他节点的平衡因子都不受影响。但在没有完整地重新计算新子树高度的情况下，怎么能更新平衡因子呢？下面的推导过程能证明，这些代码是对的。
图6-30 展示了左旋结果。B 和 D 是关键节点，A、C、E 是它们的子树。针对根节点为 x 的子树，将其高度记为 hx。由定义可知：
\$oldBal(B)=h_A-h_D\$
D 的旧高度也可以定义为 1+max(hC, hE)，即 D 的高度等于两棵子树的高度的大值加一。因为 hC 与 hE 不变，所以代入第 2 个等式，得到 oldBal(B)=hA-(1+max(hC,hE))。然后，将两个等式相减，并运用代数知识简化 newBal(B) 的等式。
\$\n\ewBal(B)-oldBal(B)=h_A-h_C-h_A+(1+max(h_C, h_E))\$
\$\n\ewBal(B)-oldBal(B)=h_A-h_A+1+max(h_C, h_E)-h_C\$
\$\n\ewBal(B)-oldBal(B)=1+max(h_C, h_E)-h_C\$
下面将 oldBal(B) 移到等式右边，并利用性质 max(a, b)-c=max(a-c, b-c) 得到：
由于 hE-hC 就等于-oldBal(D)，因此可以利用另一个性质 max(-a, -b)=-min(a,b)。最后几步推导如下：
\$\n\ewBal(B)=oldBal(B)+1-min(0, oldBal(D))\$
至此，我们已经做好所有准备了。如果还记得 B 是 rotRoot 而 D 是 newRoot，那么就能看到以上等式对应于代码清单 6-38 中的第 16 行：
rotRoot.balanceFactor = rotRoot.balanceFactor + 1 \
- min(newRoot.balanceFactor, 0)通过类似的推导，可以得到节点 D 的等式，以及右旋后的平衡因子。这个推导过程留作练习。
现在你可能认为大功告成了。我们已经知道如何左旋和右旋，也知道应该在什么时候旋转，但请看看图 6-31。节点 A 的平衡因子为 -2，应该做一次左旋。但是，围绕节点 A 左旋后会怎样呢？
左旋后得到另一棵失衡的树，如图 6-32 所示。如果在此基础上做一次右旋，就回到了图 6-31 的状态。
要解决这种问题，必须遵循以下规则。
-
如果子树需要左旋，首先检查右子树的平衡因子。如果右子树左倾，就对右子树做一次右旋，再围绕原节点做一次左旋。
-
如果子树需要右旋，首先检查左子树的平衡因子。如果左子树右倾，就对左子树做一次左旋，再围绕原节点做一次右旋。
图6-33 展示了如何通过以上规则解决图6-31 和图6-32 中的困境。围绕节点 C 做一次右旋，再围绕节点 A 做一次左旋，就能让子树恢复平衡。
rebalance 方法实现了上述规则，如代码清单 6-39 所示。第 2 行的 if 语句实现了规则 1，第 8 行的 elif 语句实现了规则 2。
在 6.11 节中，你将尝试通过先左旋再右旋的方式恢复一棵树的平衡，还会试着为一些更复杂的树恢复平衡。
def rebalance(self,node):
if node.balanceFactor < 0:
if node.rightChild.balanceFactor > 0:
self.rotateRight(node.rightChild)
self.rotateLeft(node)
else:
self.rotateLeft(node)
elif node.balanceFactor > 0:
if node.leftChild.balanceFactor < 0:
self.rotateLeft(node.leftChild)
self.rotateRight(node)
else:
self.rotateRight(node)通过维持树的平衡，可以保证 get 方法的时间复杂度为 \$O(log_2n)\$。但这会给 put 操作的性能带来多大影响呢？我们来看看 put 操作。因为新节点作为叶子节点插入，所以更新所有父节点的平衡因子最多需要 \$log_2n\$ 次操作——每一层一次。如果树失衡了，恢复平衡最多需要旋转两次。每次旋转的时间复杂度是 \$O(1)\$，所以 put 操作的时间复杂度仍然是 \$O(log_2n)\$。
至此，我们已经实现了一棵可用的 AVL 树，不过还没有实现删除节点的功能。我们将删除节点及后续的更新和再平衡的实现留作练习。
