第16章：AVL树
在上一章中，你了解了二进制搜索树的O(log n)性能特征。然而，你也了解到，不平衡的树会使树的性能恶化，一直到O(n)。1962年，Georgy Adelson-Velsky和Evgenii Landis想出了第一个自平衡二进制搜索树。AVL树。在这一章中，你将深入研究二进制搜索树的平衡性如何影响性能，并从头开始实现AVL树!
了解平衡
平衡树是优化二进制搜索树性能的关键。在本节中，你将了解到平衡的三种主要状态。
完美平衡
二进制搜索树的理想形式是完全平衡状态。在技术术语中，这意味着树的每一层都充满了节点，从上到下。
完美平衡的树
这棵树不仅是完全对称的，而且底层的节点也完全被填满。这就是完美平衡的要求。
足够好的二叉树
虽然实现完美平衡是最理想的，但它很少可能。一棵完全平衡的树必须包含确切数量的节点来填充每一层到底部，所以它只能用特定数量的元素来实现完美。
例如，一棵有1、3或7个节点的树可以是完美平衡的，但一棵有2、4、5或6个节点的树不可能是完美平衡的，因为树的最后一层将不会被填满。
平衡树的定义是，树的每一层都必须被填满，除了最底层。在大多数二叉树的情况下，这是你能做的最好的事情。
不平衡
最后，还有一种不平衡状态。在这种状态下的二进制搜索树会有不同程度的性能损失，这取决于不平衡的程度。
保持树的平衡使查找、插入和删除操作的时间复杂度为O(log n)。AVL树通过在树变得不平衡时调整树的结构来保持平衡。你会在本章中了解到这是如何进行的。
实施
在本章的启动项目中，有一个上一章创建的二进制搜索树的实现。唯一的区别是，所有对二进制搜索树的引用都改名为AVL树。
二进制搜索树和AVL树有很多相同的实现；事实上，你所要添加的只是平衡组件。打开启动器项目开始。
测量平衡
为了保持二叉树的平衡，你需要一种方法来测量树的平衡。AVL树通过每个节点的高度属性实现了这一点。用树的语言来说，一个节点的高度是当前节点到叶子节点的最长距离。
打开本章的启动游戏，在编译后的源文件夹中为AVLNode添加以下属性。
public var height = 0
你将使用一个节点的子节点的相对高度来确定一个特定的节点是否平衡。每个节点的左右两个子节点的高度最多只能相差1，这个数字被称为平衡系数。
在AVLNode的高度属性下面写上以下内容。
balanceFactor计算左右两个孩子的高度差。如果某个孩子是nil，它的高度就被认为是-1。
下面是一个AVL树的例子。
图中显示的是一棵平衡树--除了底层之外，所有的层次都被填充。节点右边的数字代表每个节点的高度，而左边的数字代表平衡因子（balanceFactor）。
下面是一个插入了40的更新图。
在树中插入40，就变成了一棵不平衡的树。请注意balanceFactor的变化。BalanceFactor为2或-2或更极端的数值表明是一棵不平衡的树。不过，通过在每次插入或删除后进行检查，你可以保证它永远不会比2的幅度更极端。
尽管不止一个节点可能有不好的平衡系数，但你只需要对包含无效平衡系数的最底层节点执行平衡程序：包含25的节点。
这就是旋转的作用。
旋转
用来平衡二进制搜索树的程序被称为旋转。一棵树有四种不同的方式可以变得不平衡，总共有四种旋转方式。这些被称为左旋转、左-右旋转、右旋转和右-左旋转。
左旋转
在树中插入40个节点造成的不平衡可以通过左旋转来解决。节点x的一般左旋看起来像这样。
在讨论具体细节之前，从这个前后对比中可以得到两个启示。
-
这些节点的顺序内遍历保持不变。
-
旋转之后，树的深度减少了一级。
在AVLTree中添加以下方法，就在insert(from:value:)下面。
private func leftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
// 1
let pivot = node.rightChild!
// 2
node.rightChild = pivot.leftChild
// 3
pivot.leftChild = node
// 4
node.height = max(node.leftHeight, node.rightHeight) + 1
pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
// 5
return pivot
}
以下是进行左旋所需的步骤。
-
选择右边的子节点作为支点。这个节点将取代被旋转的节点作为子树的根（它将向上移动一级）。
-
被旋转的节点将成为支点的左端子节点（它将向下移动一级）。这意味着当前枢轴的左端子节点必须被移到其他地方。在前面图片中显示的通用例子中，这是节点b。因为b比y小，但比x大，它可以取代y成为x的右子。
-
枢轴的leftChild现在可以被设置为旋转的节点。
-
你更新旋转节点和枢轴的高度。
-
最后，你返回支点，这样它就可以取代树中的旋转节点。下面是前一个例子中25的左旋转前后的效果。
右旋转
右转是左转的对称性反面。当一系列左边的孩子造成不平衡时，就是右旋转的时候了。
节点x的一般右旋转看起来像这样。
为了实现这一点，在leftRotate之后添加以下代码。
这个算法与leftRotate的实现几乎相同，只是对左、右子节点的引用被交换了。
右-左旋转
你可能已经注意到，左旋和右旋会平衡那些全部为左子节点或全部为右子节点的结点。考虑一下36被插入到原始示例树中的情况。
左右旋转。
在这种情况下，做左旋转不会产生一个平衡的树。处理这种情况的方法是，在做左旋转之前，先对右边的孩子进行右旋转。下面是这个程序的样子。
-
你对37应用一个右旋。
-
现在，节点25、36和37都是右边的子节点；你可以应用一个左旋转来平衡树。
在rightRotate之后添加以下代码。
private func rightLeftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
guard let rightChild = node.rightChild else {
return node
}
node.rightChild = rightRotate(rightChild)
return leftRotate(node)
}
先不要担心什么时候打这个电话。一会儿你就会知道了。你首先需要处理最后一种情况，左右旋转。
左-右旋转
左右旋转是左右旋转的对称反面。这里有一个例子。
-
你对节点10应用一个左旋转。
-
现在，节点25、15和10都是左边的子节点；你可以应用右旋转来平衡树。
在rightLeftRotate之后添加以下代码。
这就是旋转的情况。接下来，你要弄清楚何时在正确的位置应用这些旋转。
平衡
下一个任务是设计一个方法，使用balanceFactor来决定一个节点是否需要平衡。在leftRightRotate下面写上以下方法。
有三种情况需要考虑。
-
balanceFactor为2，表明左边的孩子比右边的孩子 "更重"（包含更多的节点）。这意味着你要使用右旋转或左旋转。
-
平衡因子为-2时，表明右边的孩子比左边的孩子更重。这意味着你要使用左旋转或右-左旋转。
-
默认情况下，表明该特定节点是平衡的。这里除了返回节点，没有什么可做的。
balanceFactor的符号可以用来确定是否需要单旋转或双旋转。
将平衡函数更新为以下内容。
balanced检查balanceFactor以确定适当的行动方案。剩下的就是在适当的地方调用balance。
重新审视插入
你已经完成了大部分的工作。其余的部分是相当直接的。将insert(from:value:)更新为以下内容。
你不是在插入后直接返回节点，而是将其传入平衡。传递它可以确保调用栈中的每个节点都被检查出平衡问题。你还可以更新节点的高度。
这就是它的全部内容! 进入playground页面并测试它。在playground上添加以下内容。
你应该在控制台看到以下输出。
花点时间来欣赏一下节点的均匀分布。如果不应用旋转，这将成为一个长的、不平衡的右子链接。
重新审视移除操作
改造remove操作以实现自我平衡，就像修复insert一样简单。在AVLTree中，找到remove并将最后的返回语句替换为以下内容。
回到playground页面，在文件的底部添加以下代码。
你应该看到下面的控制台输出。
去掉10导致15的左转。请随意尝试一些你自己的测试案例。
呜呼! AVL树是你寻找终极二进制搜索树的巅峰之作。自平衡特性保证了插入和删除操作的最佳性能，其时间复杂度为O（log n）。
关键点
-
自平衡树通过在树中添加或删除元素时执行平衡程序来避免性能下降。
-
AVL树通过在树不再平衡时重新调整树的一部分来保持平衡。
-
平衡是通过在节点插入和移除时的四种树的旋转来实现的。
今后的发展方向是什么？
虽然AVL树是BST的第一个自我平衡的实现，但其他的，如红黑树和splay树，后来也加入了这个行列。如果你有兴趣，你可以在raywenderlich.com Swift算法俱乐部中查看这些。找到它们的地址分别是：https://github.com/raywenderlich/swift-algorithm-club/tree/master/RedBlack%20Tree 和 https://github.com/raywenderlich/swift-algorithm-club/tree/master/Splay%20Tree。
| 上一章 | 目录 | 下一章 |
|---|