万博体育max手机版即(左-右或右-左)

当前位置:万博man手机客户端 > 万博体育max手机版 > 万博体育max手机版即(左-右或右-左)
作者: 万博man手机客户端|来源: http://www.shiketool.com|栏目:万博体育max手机版

文章关键词:万博man手机客户端,二叉树

  不同于顺时针跟逆时针变换这种方式去记忆上面两个动态图特别方便记忆跟理解

  左旋就是将节点的右支往左拉右子节点变成父节点并把晋升之后多余的左子节点出让给降级节点的右子节点

  而右旋就是反过来将节点的左支往右拉左子节点变成了父节点并把晋升之后多余的右子节点出让给降级节点的左子节点。

  即左旋就是往左变换右旋就是往右变换。不管是左旋还是右旋旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。

  举个例子像上图是否平衡二叉树的图里面左图在没插入前”19“节点前该树还是平衡二叉树但是在插入”19“后导致了”15“的左右子树失去了”平衡“所以此时可以将”15“节点进行左旋让”15“自身把节点出让给”17“作为”17“的左树使得”17“节点左右子树平衡而”15“节点没有子树左右也平衡了。如下图

  由于在构建平衡二叉树的时候当有新节点插入时都会判断插入后时候平衡这说明了插入新节点前都是平衡的也即高度差绝对值不会超过1。当新节点插入后有可能会有导致树不平衡这时候就需要进行调整而可能出现的情况就有4种分别称作左左左右右左右右。

  左左即为在原来平衡的二叉树上在节点的左子树的左子树下有新节点插入导致节点的左右子树的高度差为2如上即为”10“节点的左子树”7“的左子树”4“插入了节点”5“或”3“导致失衡。

  注意如果对左右旋变换还不是很懂或不是很熟练的可以对照着前面的那两个动图去想象自己动手变换几次就明白了。

  左右即为在原来平衡的二叉树上在节点的左子树的右子树下有新节点插入导致节点的左右子树的高度差为2如上即为”11“节点的左子树”7“的右子树”9“插入了节点”10“或”8“导致失衡。

  左右的调整就不能像左左一样进行一次旋转就完成调整。我们不妨先试着让左右像左左一样对”11“节点进行右旋结果图如下右图的二叉树依然不平衡而右图就是接下来要讲的右左即左右跟右左互为镜像左左跟右右也互为镜像。

  右右跟左左一样只需要旋转一次就能把树调整平衡而左右跟右左也一样都要进行旋转两次才能把树调整平衡所以首先上图的这种调整是错误的正确的调整方式是将左右进行第一次旋转将左右先调整成左左然后再对左左进行调整从而使得二叉树平衡。

  即先对上图的节点”7“进行左旋使得二叉树变成了左左之后再对”11“节点进行右旋此时二叉树就调整完成如下图

  右左即为在原来平衡的二叉树上在节点的右子树的左子树下有新节点插入导致节点的左右子树的高度差为2如上即为”11“节点的右子树”15“的左子树”13“插入了节点”12“或”14“导致失衡。万博体育max手机版

  前面也说了右左跟左右其实互为镜像所以调整过程就反过来先对节点”15“进行右旋使得二叉树变成右右之后再对”11“节点进行左旋此时二叉树就调整完成如下图

  右右即为在原来平衡的二叉树上在节点的右子树的右子树下有新节点插入导致节点的左右子树的高度差为2如上即为”11“节点的右子树”13“的左子树”15“插入了节点”14“或”19“导致失衡。

  右右只需对节点进行一次左旋即可调整平衡如下图对”11“节点进行左旋。

  平衡二叉树构建的过程就是节点插入的过程插入失衡情况就上面4种算简单了下面讲下平衡二叉树节点的删除删除的情况会复杂一点复杂的原因主要在于删除了节点之后要维系二叉树的平衡但是删除二叉树节点总结起来就两个判断①删除的是什么类型的节点②删除了节点之后是否导致失衡

  节点的类型有三种1.叶子节点2.只有左子树或只有右子树3.既有左子树又有右子树。

  2删除的节点只有左子树或只有右子树这种情况其实就比删除叶子节点的步骤多一步就是将节点删除然后把仅有一支的左子树或右子树替代原有结点的位置后面的步骤就一样了从父节点开始判断是否失衡如果没有失衡则再判断父节点的父节点是否失衡直到根节点如果中间过程发现失衡则根据失衡的类型进行调整。

  3删除的节点既有左子树又有右子树这种情况又比上面这种多一步就是中序遍历找到待删除节点的前驱或者后驱都行然后与待删除节点互换位置然后把待删除的节点删掉后面的步骤也是一样判断是否失衡然后根据失衡类型进行调整。

  最后总结一下平衡二叉树是一棵高度平衡的二叉树所以查询的时间复杂度是 O(logN)。插入的线c;左右右左右右即一旦插入新节点导致失衡需要调整最多也只要旋转2次所以插入复杂度是 O(1)但是平衡二叉树也不是完美的也有缺点从上面删除处理思路中也可以看到就是删除节点时有可能因为失衡导致需要从删除节点的父节点开始不断的回溯到根节点如果这棵平衡二叉树很高的线c;那中间就要判断很多个节点。所以后来也出现了综合性能比其更好的树—-红黑树后面再讲。

  ,如图: 在删除节点的时候我们只需考虑一下三种情况: (1)要删除的节点是叶子结点,如图: (2)要删除的节点有左节点但是没有右节点,或者有右节点但是没有左节点,如图: (3)要删除的节点既有...

  的结构是很均匀的排列的,别急,当依次插入13,14数据后,如下图:...

  高度1 操作: 1. 创建一个新的节点,值等于当前根的节点的值 2. 新节点的左子

  4. 当前根节点的值 = 当前根节点右子节点的值 5. 当前根节点的右子

  已知如下所示长度为12的表: (Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec) 按表中元素顺序构造一棵

  每个节点的子节点不允许超过两个。通过将子节点的个数限定为2,可以写出高效的程序在

  ,相对较小的值保存在左节点中,较大的值保存在右节点中。 那么,如何实现二叉

  呢? 1、定义Node对象 Node 对象既保存数据,也保存和其他节点的链接(left 和right),show() 方法用来显示保存在节点中的数据。 functio...

  实现的实例 选取一组数据分别为2,1,0,3,4,5,6,9,8,7的10个结点来构造

  ,这里的操作一般称为旋转。第一种情况是插入的节点在外面,即(左-左或右-右)、另一种是节点插在里面,即(左-右或右-左), 对于第一种情况我们采用单旋转,第二种采...

  写在前面:博主是一位普普通通的19届双非软工在读生,平时最大的爱好就是听听歌,逛逛B站。博主很喜欢的一句话花开堪折直须折,莫待无花空折枝:博主的理解是头一次为人,就应该做自己想做的事,做自己不后悔的事,做自己以后不会留有遗憾的事,做自己觉得有意义的事,不浪费这大好的青春年华。博主写博客目的是记录所学到的知识并方便自己复习,在记录知识的同时获得部分浏览量,得到更多人的认可,满足小小的成就感,同时在写博客的途中结交更多志同道合的朋友,让自己在技术的路上并不孤单。 目录: 1.

  就是通过关键字key找到数据元素的地址。本质上是确定关键字集合K到地址空间A的映射:H:K--A。所有的算法都是在计算H(k)的值的过程。大多数

  算法没有一个简单直接的对应关系。 而散列函数就是一个映射关键字到散列表的压缩函数。通过一个简单的映射关系,直接通过key计算出地址。数据元素存放的地方称为散列表。 对于给定的关键字集合,散列函数(hash)计算的地址要分布均匀,这样...

  ,是由Adelson-Velskii和Landis于1962年首先提出的,所以又称为AVL

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!