练习 20：二叉搜索树

原文：Exercise 20: Binary Search Trees

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

在本练习中，我将让你将数据结构的中文描述翻译成工作代码。你已经知道如何使用“大师复制”方法，分析算法或数据结构的代码。你还可以了解如何阅读算法的伪代码描述。现在你将结合二者，并学习如何拆分一个相当松散的二进制搜索树的英文描述。

我打算马上开始，并提醒你，当你做这个练习的时候，不要访问维基百科页面。维基百科的二进制搜索树描述拥有可以工作的 Python 代码，因此它会使此练习失败。如果你卡住了，那么你可以阅读任何你可以使用的资源，但是首先尝试按照这里我的描述来实现。

二叉搜索树

在练习 16 中，你了解了“归并排序”接受扁平的链表，将其转换为已排序部分的树。它将列表切成小块，然后通过排序左侧较小值的部分，以及右侧较大值的部分，将其重新组合在一起。在某种程度上，二叉搜索树（BSTree）是一种数据结构，本身就是有序的，并且不会使用列表来储存元素。BSTree的一个主要用途是，用一棵树来组织key = value节点的偶对，在你插入或者删除它们的时候，保持它们有序。

最开始，BSTree拥有一个key=value根节点，它拥有左子节点或者右子节点（都是链接）。如果插入一个新的key=value，那么BSTree的任务是，从根节点开始，将key与每一个节点进行比较：如果新的键小于或等于它，走左边；如果新的键大于它，走右边。最终，BSTree在树中找到一个位置，如果你遵循原始路径，你应该按照相同的过程找到它。之后的所有操作都是一样的，通过将任何键与每个节点，左移或者右移，直到找到节点或到达末尾。

这样，BSTree是练习 17 中的Dictionary的替代品，因此它应该具有相同的操作。基本的BSTreeNode将需要left，right，key和value属性来创建树结构。你可能还需要parent属性，具体取决于你如何执行此操作。（译者注：如果你在遍历过程中记录父节点，就不用这个属性。）然后，BSTree需要在根 BSTreeNode上进行以下操作：

get

提供一个键，遍历树，找到节点，或者如果到达末尾，返回None。如果提供的键是小于等于节点的键，走左边。如果键大于节点的键，走右边。如果你碰到一个没有左子节点或右子节点的节点，那么你已经遍历完了，并且该节点不存在。可以使用递归或使用while循环。

set

这和get几乎一样，除了一旦你到达末尾的节点，你只需将一个新的BSTreeNode挂载到左子节点或右子节点，从而将树向下延伸了一个分支。

delete

从BSTree删除节点是一个复杂的操作，所以我有一个完整的部分只是讲删除。简而言之有三个情况：节点是叶子（没有子节点），有一个子节点，或者有两个子节点。如果它是叶子，那么只是删除它。如果有一个子节点，然后将其替换为子节点。如果它有两个子节点，那么它变得非常复杂，因此请阅读下面删除的部分。

list

遍历树，打印一切东西。list 的重要内容是，你可以以不同的方式遍历树，Kauai产生不同的输出。如果你遍历left，之后是right，那么你会得到一些不同于反着执行的东西。如果你走了所有到底部的路，然后当你朝着root向上走的时候，打印结果，你会得到另一种类型的输出。你也可以在向下遍历树的时候打印节点，从root到“叶子”。尝试不同的风格，看看它们都做了什么。

删除

记住，删除节点时我们需要处理三个情况（我称之为D）：

• D节点是“叶子”节点，因为它有没有子节点（左子节点或者右子节点）。只需从父节点删除它。
• D节点只有一个子节点（左子节点或者右子节点，但不是二者）。在这种情况下，你可以将该子节点的值移动到D节点，然后删除该子节点。这有效地替换了D节点与子节点（或“将子节点向上移动”）。
• D节点有左子节点和右子节点，这意味着这时候需要做一些大的操作。首先，找到的D.right节点的最小子节点，成为successor。将D.key赋为successor.key，然后对successor的子节点使用它的键，做相同的删除操作。

你最有可能还需要find_minimum和replace_node_in_parent操作，来执行这两个操作。我提到你可能需要parent 属性，具体取决于你实现它的方式。我会假设使用parent 节点，因为这在大多数情况下更容易。

注意

每个人都讨厌树的删除操作。这是一个复杂的操作，甚至是我最喜欢的参考书，Steven S. Skiena 的《算法设计手册》都跳过了它，因为实现“看起来有点可怕”。如果你很难弄清楚delete，不要气馁。

挑战练习

你将使用这个故意模糊的描述实现你的BSTree。当你第一次尝试时，尝试不要看太多的参考，然后当你卡住时，去阅读他人的实现方式。这个练习的重点是，尝试从一个糟糕的描述中解决一个复杂的问题。

解决这个问题的窍门是，首先将英文段落翻译成粗糙的伪代码。然后将粗糙的伪代码转换为更精确的伪代码。一旦你有了更精确的伪代码，你可以把它翻译成 Python 代码。特别注意具体的单词，例如单个英文单词可能意味着 Python 中的很多东西。有时你只需要猜测并运行你的测试，看看是否正确。

测试也非常重要，对这个问题应用“测试第一”的方法，可能是一个好主意。你知道这些操作应该做什么，所以你可以为它编写一个测试，然后让测试工作。

研究性学习

• 你是否可以开发一个病态的测试，以某种方式插入元素，使BSTree只不过是一个花式链表？
• 当你尝试删除这个BSTree的“极点”时，会发生什么？
• 与你的最近优化的Dictionary相比，BSTree的速度如何？
• 使用你的性能分析和调整流程，你能多快实现BSTree？