## 练习 20：二叉搜索树 > 原文：[Exercise 20: Binary Search Trees](https://learncodethehardway.org/more-python-book/ex20.html) > 译者：[飞龙](https://github.com/wizardforcel) > 协议：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻译](https://translate.google.cn/) 在本练习中，我将让你将数据结构的中文描述翻译成工作代码。你已经知道如何使用“大师复制”方法，分析算法或数据结构的代码。你还可以了解如何阅读算法的伪代码描述。现在你将结合二者，并学习如何拆分一个相当松散的二进制搜索树的英文描述。 我打算马上开始，并提醒你，当你做这个练习的时候，不要访问维基百科页面。维基百科的二进制搜索树描述拥有可以工作的 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 的[《算法设计手册》](http://amzn.to/2qIA3ai)都跳过了它，因为实现“看起来有点可怕”。如果你很难弄清楚`delete`，不要气馁。 ## 挑战练习 你将使用这个故意模糊的描述实现你的`BSTree`。当你第一次尝试时，尝试不要看太多的参考，然后当你卡住时，去阅读他人的实现方式。这个练习的重点是，尝试从一个糟糕的描述中解决一个复杂的问题。 解决这个问题的窍门是，首先将英文段落翻译成粗糙的伪代码。然后将粗糙的伪代码转换为更精确的伪代码。一旦你有了更精确的伪代码，你可以把它翻译成 Python 代码。特别注意具体的单词，例如单个英文单词可能意味着 Python 中的很多东西。有时你只需要猜测并运行你的测试，看看是否正确。 测试也非常重要，对这个问题应用“测试第一”的方法，可能是一个好主意。你知道这些操作应该做什么，所以你可以为它编写一个测试，然后让测试工作。 ## 研究性学习 + 你是否可以开发一个病态的测试，以某种方式插入元素，使`BSTree`只不过是一个花式链表？ + 当你尝试删除这个`BSTree`的“极点”时，会发生什么？ + 与你的最近优化的`Dictionary`相比，`BSTree`的速度如何？ + 使用你的性能分析和调整流程，你能多快实现`BSTree`？