第14章：二进制搜索树
二进制搜索树，或BST，是一种便于快速查找、插入和删除操作的数据结构。考虑下面的决策树，选择一方就放弃了另一方的所有可能性，将问题减半。
一旦你做出决定并选择了一个分支，就不会再回头了。你一直走下去，直到你在一个叶子节点上做出最终决定。二叉树让你做同样的事情。具体来说，二进制搜索树对你在前一章看到的二进制树施加了两条规则。
-
左侧子节点的值必须小于其父节点的值。
-
因此，右边的子项的值必须大于或等于其父项的值。
二进制搜索树使用这个属性，使你不必进行不必要的检查。因此，查找、插入和删除的平均时间复杂度为O(log n)，比线性数据结构如数组和链表快得多。
在本章中，你将了解BST相对于数组的优点，并像往常一样，从头实现数据结构。
案例研究：数组与BST
为了说明使用BST的力量，你将看一些常见的操作，并比较数组与二进制搜索树的性能。
考虑以下两个集合。
查询
对于一个未排序的数组，只有一种方法可以进行元素查找。你需要从一开始就检查数组中的每个元素。
这就是为什么array.contains(_:)是一个O(n)操作。
而二进制搜索树则不是这样。
每次搜索算法访问BST中的一个节点时，它可以安全地做出这两个假设。
-
如果搜索值小于当前值，那么它一定在左子树中。
-
如果搜索值大于当前值，那么它一定在右边的子树中。
通过利用BST的规则，你可以避免不必要的检查，并在每次做决定时将搜索空间减半。这就是为什么BST中的元素查找是一个O（log n）操作。
插入
插入操作的性能优势与此类似。假设你想在一个集合中插入0。
向数组中插入数值就像插入到一个现有的行中。在你选择的位置后面的队伍中的每个人都需要通过洗牌来为你腾出空间。
在上面的例子中，0被插入到数组的前面，导致所有其他元素向后移动一个位置。插入一个数组的时间复杂度为O(n)。
插入到二进制搜索树中则要舒服得多。
通过利用BST的规则，你只需要进行三次遍历就可以找到插入的位置，而且你不需要对所有的元素进行洗牌! 在BST中插入元素也是一个O(log n)的操作。
移除
与插入类似，在一个数组中移除一个元素也会引发元素的洗牌。
这种行为也与排队的比喻相得益彰。如果你离开了队伍的中间，你后面的人就需要向前洗牌以占据空位。
这就是从BST中删除一个值的样子。
很好，很简单 当你要删除的节点有子节点时，会有一些复杂的情况需要处理，但你会在后面研究这个问题。即使有这些复杂情况，从BST中删除一个元素仍然是一个O(log n)的操作。
二进制搜索树极大地减少了添加、删除和查找操作的步骤。现在你已经了解了使用二进制搜索树的好处，你可以继续进行实际的实现。
实现
打开本章的启动项目。在其中，你会发现你在前一章创建的 BinaryNode 类型。创建一个名为 BinarySearchTree.swift 的新文件，并在该文件中添加以下内容。
根据定义，二进制搜索树只能容纳具有可比性的值。
注意：你可以通过使用闭包进行比较来放松可比较的要求。在这里使用Comparable是为了让事情变得简单，并将注意力集中在二叉树的核心概念上。
接下来，你会看到插入方法。
插入元素
根据BST的规则，左边子节点的节点必须包含小于当前节点的值。右边子节点必须包含大于或等于当前节点的值。你将在尊重这些规则的前提下实现插入方法。
在 BinarySearchTree.swift 中添加以下内容。
第一个插入方法是暴露给用户的，而第二个方法将作为一个私有的帮助方法使用。
-
这是一个递归方法，所以它需要一个终止递归的基例。如果当前节点为nil，你已经找到了插入点，可以返回一个新的BinaryNode。
-
因为元素类型是可比较的，你可以进行比较。这个if语句控制下一个插入调用应该以何种方式遍历。如果新值小于当前值，你就在左边的子节点上调用插入。如果新值大于或等于当前值，你就在右边的子节点上调用插入。
-
返回当前节点。这使得node = insert(from: node, value: value)这种形式的赋值成为可能，因为insert将创建node（如果它是nil）或者返回node（它不是nil）。
回到playground页面，在底部添加以下内容。
你应该看到以下输出。
那棵树看起来有点不平衡，但它确实符合规则。然而，这种树的布局有不理想的后果。在处理树木时，你总是想实现平衡的格式。
一个不平衡的树会影响性能。如果你在你创建的不平衡树中插入5，就会变成一个O(n)操作。
你可以创建被称为自平衡树的结构，使用巧妙的技术来保持平衡的结构，但我们会把这些细节留到第16章 "AVL树"。现在，你将建立一个样本树，并注意防止它变得不平衡。
在playground页面的顶部添加以下计算变量。
example(of: "building a BST") {
print(exampleTree)
}
你应该在控制台看到以下内容。
好多了!
寻找元素
在BST中寻找一个元素需要你遍历其节点。通过使用你在上一章学到的现有的遍历机制，可以想出一个相对简单的实现。
在 BinarySearchTree.swift 的底部添加以下内容。
接下来，回到playground页面，测试一下这个。
你应该在控制台看到以下内容。
顺序内遍历的时间复杂度为O(n)；因此，contains的这种实现的时间复杂度与通过未排序数组的穷举搜索相同。然而，你可以做得更好。
优化contains
你可以依靠 BST 的规则来避免不必要的比较。回到 BinarySearchTree.swift 中，将 contains 方法更新为以下内容。
-
开始时，将电流设置为根节点。
-
当current不为零时，检查当前节点的值。
-
如果该值等于你要找的东西，返回true。
-
否则，决定你是要检查左边的还是右边的孩子。在平衡的二进制搜索树中，contains的这个实现是一个O(log n)操作。
移除元素
移除元素就比较麻烦了，因为你需要处理几种不同的情况。
情况1：叶子结点
删除一个叶子节点是很简单的，只要把叶子节点分离出来就可以了。
然而，对于非叶子节点，有一些额外的步骤你必须采取。
情况2：有一个孩子的节点
当移除有一个孩子的节点时，你需要将这一个孩子与树的其他部分重新连接。
案例3：有两个孩子的节点
有两个子节点的情况比较复杂，所以用一个更复杂的树的例子可以更好地说明如何处理这种情况。假设你有下面这棵树，你想删除25这个值。
简单地删除这个节点就会出现两难的局面。
你有两个子节点（12和37）需要重新连接，但父节点只有一个子节点的空间。为了解决这个问题，你将通过执行交换来实现一个巧妙的变通方法。
当删除一个有两个子节点时，用其右子树中最小的节点替换你删除的节点。根据BST的规则，这就是右子树的最左边的节点。
值得注意的是，这产生了一个有效的二进制搜索树。因为新节点是右子树中最小的节点，所以右子树中的所有节点仍然会大于或等于新节点。因为新节点来自右子树，所以左子树中的所有节点都将小于新节点。
执行交换后，你可以简单地删除你复制的值，只是一个叶子节点。
这将照顾到删除有两个孩子的节点。
实现
打开 BinarySearchTree.swift 来实现删除。在文件的底部添加以下代码。
这对你来说应该很熟悉。你使用了与插入方法相同的递归设置和一个私有辅助方法。你还为BinaryNode添加了一个递归的min属性，以找到子树中的最小节点。在if value == node.value子句中处理了不同的移除情况。
-
如果该节点是一个叶子节点，你只需返回nil，从而删除当前节点。
-
如果该节点没有左子，你返回node.rightChild来重新连接右子树。
-
如果节点没有右边的子节点，你返回node.leftChild来重新连接左边的子树。
-
这种情况下，要删除的节点既有左子又有右子。
你用右子树中最小的值替换该节点的值。然后你在右边的子节点上调用remove来移除这个被替换的值。
你用右子树中最小的值替换该节点的值。然后你在右边的子节点上调用remove来移除这个被替换的值。
回到playground页面，通过编写以下内容测试remove。
你应该在控制台看到以下输出。
关键点
-
二进制搜索树是一种强大的数据结构，用于保存排序的数据。
-
二进制搜索树的元素必须是可比较的。你可以使用一个通用约束或者通过提供闭包来执行比较来实现这一点。
-
在BST中插入、移除和包含方法的时间复杂度是O(log n)。
-
当树变得不平衡时，性能将下降到O(n)。这是不可取的，所以你会在第16章中了解到一种叫做AVL树的自平衡二进制搜索树。
| 上一章 | 目录 | 下一章 |
|---|