练习 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将需要leftrightkeyvalue属性来创建树结构。你可能还需要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_minimumreplace_node_in_parent操作,来执行这两个操作。我提到你可能需要parent属性,具体取决于你实现它的方式。我会假设使用parent节点,因为这在大多数情况下更容易。

注意

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

挑战练习

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

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

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

研究性学习

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