2. AVL 树¶
AVL 树（以其发明者 Adelson-Velskii 和 Landis 的名字命名）应被视为具有以下附加性质的 二叉搜索树（BST）：对于每个结点，其左子树和右子树的高度之差至多为 1。 只要树保持这一性质，那么如果树包含 \(n\) 个结点，它的深度至多为 \(O(\log n)\)。 因此，查找任何结点的代价为 \(O(\log n)\)； 如果更新操作能在与插入或删除结点深度成正比的时间内完成， 那么即使在最坏情况下，更新操作的代价也为 \(O(\log n)\)。
使 AVL 树得以正常工作的关键在于修改插入和删除的例程，以维持平衡性质。 当然，为了实用，我们必须能够在 \(\Theta(\log n)\) 时间内实现修订后的更新例程。
Figure 26.2.1: 一个违反 AVL 树平衡性质的插入操作示例。 在插入操作之前，树的所有结点都是平衡的 （即每个结点的左子树和右子树的深度之差至多为 1）。 插入值为 5 的结点之后，值为 7 和 24 的结点不再平衡。¶
考虑插入键值为 5 的结点时会发生什么，如图 26.2.1 所示。 左图所示的树满足 AVL 树的平衡要求。 插入之后，有两个结点不再满足要求。 由于原始树满足平衡要求，新树中的结点失衡时子树高度之差至多为 2。 对于最底部的失衡结点，记为 \(S\)，有 4 种情况：
多余结点位于 \(S\) 的左孩子的左孩子中。
多余结点位于 \(S\) 的左孩子的右孩子中。
多余结点位于 \(S\) 的右孩子的左孩子中。
多余结点位于 \(S\) 的右孩子的右孩子中。
情况 1 与情况 4 是对称的，情况 2 与情况 3 也是如此。 还要注意，失衡结点必然位于从根到新插入结点的路径上。
我们现在的问题是，如何以 \(O(\log n)\) 的时间平衡这棵树。 事实证明，我们可以通过一系列被称为 旋转 的局部操作来做到这一点。 情况 1 和情况 4 可以用 单旋转 修复， 如图 26.2.2 所示。 情况 2 和情况 3 可以用 双旋转 修复， 如图 26.2.3 所示。
Figure 26.2.2: AVL 树中的单旋转。 当多余结点（在子树 \(A\) 中）位于失衡结点 \(S\) 的左孩子的左孩子中时，会发生这种操作。 按图中所示重新排列结点，我们既保持了 BST 性质， 又使树重新平衡，从而保持了 AVL 树的平衡性质。 多余结点位于失衡结点的右孩子的右孩子中的情况， 处理方法相同。¶
Figure 26.2.3: AVL 树中的双旋转。 当多余结点（在子树 \(B\) 中）位于失衡结点 \(S\) 的左孩子的右孩子中时，会发生这种操作。 按图中所示重新排列结点，我们既保持了 BST 性质， 又使树重新平衡，从而保持了 AVL 树的平衡性质。 多余结点位于 \(S\) 的右孩子的左孩子中的情况， 处理方法相同。¶
AVL 树的插入算法从一次普通的 BST 插入开始。 然后，随着递归沿树向上返回，我们对任何被发现有失衡的结点执行相应的旋转。 删除与此类似；不过，对失衡结点的检查必须从 deletemin 操作所在的层级开始。
