江苏龙网

  1. 主页 > 生活百科 > >

实现树结构的基本算法和相应的数据结构( 七 )

算法树结构

可以看到，这段代码里，f代表着客户端想要应用于BST对象里的每一个元素的任意函数 。这个函数通过f(root.item)这一行代码来执行 。与之前一样，这段代码只是我们的通用递归遍历算法的一个变体而已 。
要使用visit方法，我们只需要构造一个适用于每个元素的函数 。比如，假设我们仍然想按照顺序来输出整个BST的内容，我们现在可以通过访问者模式来完成：
def prnt(item):print item...myBST.visit(prnt)这里需要注意的一件事是，在调用visit方法的时候，prnt后面并没有跟上一对括号 。只有在我们真正单独调用这个函数的时候，才需要加上这对括号 。而在此刻，调用visit方法的时候，我们实际上并没有直接调用prnt函数，而是将这个函数对象本身传递给了将会实际执行调用的visit方法 。
访问者模式为客户端代码提供了一种很好的方式来执行容器的遍历，而且还包含了一个不需要查看细节的抽象屏障 。但是编写一个恰当的函数来进行处理，在有些时候会很麻烦，并且这样的代码并不是很像Python的风格 。与我们的其他容器类一样，Python里的理想解决方案是：使用Python的生成器机制来为我们的BST类定义一个迭代器 。它的基本思路是：我们将只需要编写一个通用的中序遍历，然后一次一个地yield树结构里的元素 。在这个时候，你肯定已经非常清楚这段代码应该怎么写了：
def __iter__(self):"""in-order iterator for binary search tree"""return self._inorderGen(self.root)def _inorderGen(self, root):if root is not None:# yield all the items in the left subtreefor item in self._inorderGen(root.left):yield itemyield root.item# yield all the items from the right subtreefor item in self._inorderGen(root.right):yield item这段代码唯一与之前不一样的地方是生成器函数的递归形式 。记住，当你调用生成器的时候，你并没有立刻获得这个元素，而是获得了一个按需提供元素的迭代器对象 。例如，为了从左子树里实际得到元素，我们必须要遍历self._inorderGen(root.left)提供的迭代器，然后输出每一个元素 。
这样一来，就有了一个可以非常方便地迭代我们的BST容器的方法了 。我们按照顺序来输出所有元素的代码不能更简单了：
for item in myBST:print item顺便说一句，既然我们有一个BST类的迭代器，那么我们就不再需要单独的asList方法了 。Python可以通过代码list(myBST)来使用迭代器从BST对象中生成整个元素的列表 。如果能够创建包含BST里所有元素的列表，在为BST类编写单元测试的时候将会特别方便，因为它提供了一种在断言里检查树结构的内容的简单方法 。当然，从BST对象中获得的有序列表并不能保证树结构具有正确的形式 。为了保证树结构的正确，用另一种遍历方法（前置或后置）将会提供不少帮助 。通过检查两个不同的遍历序列来推导出二叉树的真实结构是可行的，因此如果两个遍历都正确的话，那么我们就知道树的结构与我们所期望的结构是相同的了 。
7.5.4　二叉搜索树（BST）的运行时分析在这一部分内容的介绍里，我们提到了二叉搜索树可以非常高效地维护有序集合 。我们已经展示了二叉搜索树是如何为我们提供有序集合的了，但是我们还没有仔细检查各个操作的运行时效率 。由于许多和树结构相关的算法都是通过递归来编写的，因此分析它们可能会看起来比较麻烦 。但是，如果我们只考虑底层结构里发生的事情的话，那么，分析起来就很容易了 。
让我们先从遍历整个树的操作开始考虑 。由于我们在每个节点上必须要完成的工作量是不变的，因此遍历的时间与树里的节点的数量是成正比的，也就是集合中的元素数量 。因此，那些操作的时间复杂度将会是Θ (n)，其中n是集合的大小 。
对于只会检查树的一部分（例如，搜索、插入以及删除）的算法，我们的分析将会取决于树结构的形状 。所有的这些方法的最坏情况都需要走一条从树的根节点到其“底部”的路径 。很明显，这样做所需的步骤数量将和树的高度成正比 。于是，一个有趣的问题出现了，一个二叉树有多高？显然，这取决于树结构的确切形状 。如果我们假设这个树是按照排序的顺序来插入的一组数字的话，这个树将会是一个链表，这是因为每个节点都被添加为前一个数字的右子节点 。对于具有n个元素的树结构来说，插入需要n步才能到达树的底部 。
如果树结构里的数据分布得很好的话，那么我们可以估计：对于任意给定的子树来说，都有大约一半的元素位于它的左子树，而剩下的大约一半的元素位于右子树 。我们称这样的树为“平衡”树 。相对平衡的树将具有log2n的近似高度 。在这种情况下，必须在树中找到特定的节点的操作将会有Θ (lgn)的复杂度 。好在，如果数据是按照随机的方式插入树里的话，那么当我们从根节点向下执行的时候，对于每一个节点来说，这个元素具有同样的可能性进入左子树或者右子树 。平均来说，这个结果将会是一个非常平衡的树 。


推荐阅读


上一篇：新手淘宝开店需要多少钱可以做起来 新手开淘宝店需要多少资金

下一篇：记一次CPU使用率低负载高的排查过程