课程咨询 :13623629309

太原PHP培训 > 达内新闻 > 太原php培训机构:Python数据结构——二叉搜索树的实现(下二)
  • 太原php培训机构:Python数据结构——二叉搜索树的实现(下二)

    发布:太原PHP培训      来源:伯乐在线      时间:2016-06-22

  • Listing 11

    太原达内php培训

    我们还需要看看二叉搜索树的最后一个接口。假设我们已经按顺序简单地遍历了子树上所有的键值,就肯定是用字典实现的,就会有疑问:为什么不是树?我们已经知道如何使用中序遍历二叉树的算法,然而,写一个迭代器需要更多的操作,因为每次调用迭代器时,一个迭代器只返回一个节点。

    Python提供了一个创建迭代器的非常强大的功能。这个功能就是yield。yield类似于return,返回一个值给调用者。然而,yield也需要额外的步骤来暂停函数的执行,以便下次调用函数时继续执行时做准备。它的功能是创建可迭代的对象,称为生成器。

    二叉树迭代器的代码如下所示。仔细观察这些代码:乍一看,你可能会认为代码是非递归的。但是请记住,__iter__重写了for x in的操作符进行迭代,所以它确实是递归!因为它是__iter__方法在TreeNode类中定义的TreeNode的实例递归。

      太原达内php培训

    在此,你可能想下载包含BinarySearchTree和TreeNode类完整代码的文档。    

      太原达内php培训

      太原达内php培训

      太原达内php编程培训

      太原达内科技

      太原达内科技

    搜索树分析

    通过二叉搜索树实现的完成,我们将对我们已经实现的方法进行一个快速的分析。让我们先看一下put这个方法。对它的执行效果造成限制的是二叉树的高度。回想一下语法阶段,树的高度指的是根和最深的叶节点之间的边的数目。高度作为一种限制因素是因为当我们在树中寻找一个合适的位置插入节点时,我们最多将会对树的每一级做比较。

    二叉树的高度可能是多少呢?这个问题的答案取决于键是怎么被添加到树中的。如果键是以一个随机的顺序加到树中的,那么当节点的数目为n时,树的高度大概是 log2n。 这是因为键是随机地散布的,大约有一半的节点会比根节点大,另一半会比它小。记住在二叉树中,根上有一个节点,下一级有两个,再下一级有四个。当级数为d时,这一级的节点 数目为 2d。当h表示树的高度时,一个满二叉树中节点的总数是 2h+1-1。

    一个满二叉树中的节点数目和一个平衡二叉树中的左子树和右子树的数目是一样多的。当树中有n个节点时put执行的最差结果的时间复杂度是 O(log2n)。要注意到这与上一段所说的是逆运算的关系。所以 log2n 代表树的高度,这表示把一个新节点插入到一个合适位置前,在搜索中需要比较的次数。

    不巧的是,通过插入排序过后的键,建造一个高度为n的搜索树是可能的。图 6 就展示了这种树的一个例子,在这种情形下,这时put方法的时间复杂度为 O(n)。

    太原达内php培训班

    图 6:一个倾斜的二叉搜索树性能会低下

    现在你已经理解了put方法的效率会受到树的高度的限制,你可能猜测其他的方法,get,in和del也是受限制的,因为要在树上寻找键,最坏的情形就是一直搜索树最后却找不到键。乍一看del也许看上去更复杂,因为它也许需要在删除操作完成之前一直查找后继节点。但是记得,寻找后继节点的最坏情形也是取决于树的高度,这意味着只需要简单地把工作量加倍,因为加倍是乘以一个常数因子,所以它不会改变最坏情形的复杂度。

上一篇:太原php培训班:Python数据结构——二叉搜索树的实现(下一)

下一篇:太原php培训班:每个程序员都应该收藏的算法复杂度速查表

最新开班日期  |  更多

php高级开发名企定制班(剩2个名额)

php高级开发名企定制班(剩2个名额)

开班日期:12-30

php高级开发周末班(剩5个名额)

php高级开发周末班(剩5个名额)

开班日期:12-30

php高级开发免费试听(剩5个名额)

php高级开发免费试听(剩5个名额)

开班日期:12-30

更多高级开发工程师精品班

更多高级开发工程师精品班

开班日期:12-30

  • 地址:山西省太原市小店区学府街长治路高新国际A座24层
  • 课程培训电话:13623629309     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56

    在线客服系统