精华内容
下载资源
问答
  • 一直没太弄明白这个到底是怎么旋转的,我是希望自己脑海中可以想象到画面,这样做题就能快些,所以上网找了些资料,不涉及代码。从这篇文章中受到了启发,终于弄明白了。https://www.jianshu.com/p/d802766551ff ...

    一直没太弄明白这个到底是怎么旋转的,我是希望自己脑海中可以想象到画面,这样做题就能快些,所以上网找了些资料,不涉及代码。从这篇文章中受到了启发,终于弄明白了。https://www.jianshu.com/p/d802766551ff

    单旋转很容易,LR双旋转第一步的结果是:将下面两个数字交换;第二步的结果是:与单旋转相似,可以把它想象成三个并排的数字,中间的数字拱上去。

    展开全文
  • 如何将非平衡二叉树调整成平衡二叉树?1. 平衡二叉树是什么鬼?满足如下两个条件的二叉树称为“平衡二叉树”:首先它得是二分查找树然后它的左右子树的高度相差不超过1图1 平衡二叉树图2 非平衡二叉树图1就是一棵...

    引言

    在上一篇《无死角“盘”它!二分查找树》中提到了:平衡二叉树的目的就是使得平均查找长度最短。那么这里就引出两个问题:

    1. 什么是平衡二叉树?
    2. 为什么平衡二叉树的平均查找长度最短?
    3. 如何将非平衡二叉树调整成平衡二叉树?

    1. 平衡二叉树是什么鬼?

    满足如下两个条件的二叉树称为“平衡二叉树”:

    1. 首先它得是二分查找树
    2. 然后它的左右子树的高度相差不超过1
    0067682ab50d19605ce94c7a1ebd4e77.png

    图1 平衡二叉树

    9ba482d85e4a88f9e33123aaeeccc421.png

    图2 非平衡二叉树

    图1就是一棵平衡二叉树,而图2不是平衡二叉树。

    在图2中,对于值为9的节点,它的左子树为空,高度为0,右子树高度为3,两者相差3,不满足平衡二叉树定义的第二条规则。

    2. 如何证明平衡二叉树的平均查找长度最短?

    首先研究一下平衡二叉树与非平衡二叉树的关系。

    图3表示的是一棵平衡二叉树,与它对应的任意一棵非平衡二叉树都可以重复按照如下方式变换而来——在维持二分查找树的前提下,从高度较小的子树中取出一个节点A,插入到高度较大的子树中——如图4所示。

    d6191584e62dbbda0b152af6f0899885.png

    图3 平衡二叉树与非平衡二叉树的转换

    8fd10c902616afc4601172a01a987b9e.png

    图4 平衡二叉树与非平衡二叉树的转换

    接下来用反证法来证明:

    假设平衡二叉树的平均查找长度L并不是最短的,那么必然存在一棵非平衡二叉树的平均查找长度L'

    对应到上面的图示就是:

    图3的平衡二叉树的平均查找长度L>图4的非平衡二叉树的平均查找长度L'(假设1)

    假设1其实是命题1的充分条件,也就是说:只要假设1为真,命题1必为真。

    图3的节点总数=图4的节点总数,设为N;

    设节点A在图3中的查找长度(从根节点到A所需要的比较次数)为La,在图4中的查找长度为La’,则根据平均查查长度的定义

    平均查找长度=每个节点的查找长度之和/节点总数

    得到:

    452a016cfc814b5ec72feffa334a4c9a.png

    显然上式与前面的假设1矛盾,从而证明了平衡二叉树的平均查找长度最短。

    3. 如何将非平衡二叉树调整成平衡二叉树?

    朴素的想法就是:遍历每个节点,检查它的左右子树高度,若高度之差超过1,设法交换一些节点的位置,使得该位置左右子树新的高度差缩减到1以内。

    这里牵扯出3个问题:

    遍历的方向:自顶向下还是自底向上?遍历的时候如何方便地获取左右子树的高度?如何交换节点的位置,使得新的高度差在1以内?

    对于问题1,如果你仔细研究过笔者前几篇文章的话——《神力加身!动态编程》《史上最猛之递归屠龙奥义》——那么你很容易得出结论:

    两个方向都可以:自顶向上的话,写递归式算法;自底向上的话,写非递归式算法。

    这里的“顶”指的是二叉树的根节点,“底”指的是二叉树的尾节点。

    对于问题2,取决于问题1采用哪种方式——如果采用递归式算法,那么在递归的时候,也顺便把高度递归计算了;如果采用非递归式,那么就在自底向上归并的时候,动态计算高度。

    问题3才是真正的新鲜问题。图5和图6分别描述了一般情况。

    992ec2727e5d377bd7e6a37c62bd58f8.png

    图5

    305529fce13dfc43520e3c30bbba136d.png

    图6

    为了解决这个“新鲜问题”,我们先来看一个引理:

    引理12.1

    因为任意非叶子节点A,它的值都比其右孩子B的值小,所以它可以变成B的左孩子。这样变换之后,A、A的左子树下降,B、B的右子树上升,高度差变小。因为任意非叶子节点A,它的值都比其左孩子C的值大,所以它可以变成C的右孩子。这样变换之后,A、A的右子树下降,B、B的左子树上升,高度差变小。
    6d253214555a607863f3488d19b46d4d.png

    图7

    bad753779b22cbf7a0f2c662c68320b4.png

    图8

    上述的变换是不是很像一种“旋转”:)

    那么是不是这样“旋转”之后,调整就OK了呢?答案是否定的。

    看看下面这个例子:

    80311f13b6fb747e98075c2c8bf39bc4.png

    图9

    图9中,B节点一开始的左子树高度比其右子树大,即:

    H(B.Left)=H(B.Right)+∆h (式1)

    “旋转”调整后,B的左子树变成A的右子树,A变成B的左孩子,设高度相对于节点的函数为H,则:

    H(A)=Max(H(B.Left), H(A.Left))+1 ≥H(B.Left)+1 (式2)

    将式1代入式2可得:

    H(A)≥H(B.Right)+∆h+1 =H(B.Right)+∆H (式3)

    当∆h=1时,∆H=2。

    此时H(A)≥H(B.Right)+2,这意味着“旋转”后,B节点的左子树高度与右子树高度相差超过1!

    貌似“旋转”对这种情况不凑效了,怎么办呢?

    先来分析一下不凑效的根因到底是什么。

    从图9可以看出,作为A节点的右孩子,从一开始,B节点的左子树就比其右子树高了一个头,这个是导致后面旋转不凑效的根因。所以很自然地想到:

    在旋转前,先把B节点的左子树高度降低或者把右子树高度升高。

    那么如何实现上述目标呢?我们能利用的仍然是引理12.1:

    先将B节点的左子树展开

    da9a9ac1c13a35fe5db7d155449973e0.png

    图10

    再对展开的子树做一次旋转:

    dbfb4c8cc263717a8a592fade44f7b50.png

    图11

    通过以上两步就达成了把原始B节点位置(现在是D节点)的左子树高度降低的目的。

    至此就转换成了熟悉的老问题。再做一次旋转便可以彻底调整成平衡二叉树了:

    7b7fdfd0f445c9200996cf694c1aa083.png

    图12

    对称地,我们可以用类似的步骤来调整下图的非平衡二叉树:

    5065b51d6e7ba9e182f20c269fada1b3.png

    图13

    步骤一(子树展开):

    7881d831c420b764b4f69ab946d98573.png

    图14

    步骤二(一次旋转):

    ad174ccfc00f128029c14e712de1b23c.png

    图15

    步骤三(二次旋转):

    e5dff43188a0f32ea367b6dd4c7f49c7.png

    图16

    综上所述,自顶向下的、单向链表存储式、递归型平衡二叉树调整算法如下:

    c57ec8575aebf2bc100130a6e4b57f76.png
    bc6855aa059f05d3b1b2e7d2e5caee75.png
    3d82099dc676d12b5b69297371da51e3.png
    f5753549ff3dc8aec2d7e7b2dc662490.png

    为了节省篇幅,自底向上的、单向链表存储式、非递归型平衡二叉树调整算法和自底向上的、数组存储式、非递归型平衡二叉树调整算法放在下一篇文章里单独列示。

    4. 平衡二叉树的节点插入算法

    首先平衡二叉树本质是二分查找树,所以插入新节点时,可遵循《无死角“盘”它!二分查找树》中的节点插入算法;

    但是平衡二叉树还是特殊的二分查找树,它还要满足左右子树高度相差不超过1的要求。当按照上面的算法插入新节点之后,可能会不满足这个要求,因此要进行调整。调整算法仍然是章节3介绍的旋转调整算法。

    5. 平衡二叉树的节点删除算法

    首先平衡二叉树本质是二分查找树,所以删除节点时,可遵循《无死角“盘”它!二分查找树》中的节点删除算法;

    但是平衡二叉树还是特殊的二分查找树,它还要满足左右子树高度相差不超过1的要求。当按照上面的算法删除节点之后,可能会不满足这个要求,因此要进行调整。调整算法仍然是章节3介绍的旋转调整算法。

    若喜欢本篇文章,麻烦打赏、点赞、转发、收藏、点击文末广告!

    支持越猛、原创越猛!

    《算法素颜》系列连载往期回顾:

    《走下神坛吧!算法》

    《扫雷还可以这样玩》

    《KO!大O——时间复杂度》

    《空间复杂度你真的懂了吗?》

    《小白也能玩转数组和链表啦!》

    《再不会"降维打击"你就Out了!》

    《神力加身!动态编程》

    《史上最猛之递归屠龙奥义》

    《菜鸟也能“种”好二叉树!》

    《二叉堆“功夫熊猫”的速成之路》

    《无死角“盘”它!二分查找树》

    展开全文
  • 基本思想就是:当在二叉排序树中插入一个节点时,首先检查是否因插入而破坏了平衡,若 破坏,则找出其中的最小不平衡二叉树,在保持二叉排序树特性的情况下,调整最小不平衡子树中节点之间的关系,以达 到新的平衡。...

     

    在数据结构的教材中,对二叉平衡树的旋转操作叙述很是模糊,为此经过在网上查询了解并收藏了以下操作方法。

     

    平衡二叉树的操作

    二叉查找树如何在添加数据的同时保持平衡呢?基本思想就是:当在二叉排序树中插入一个节点时,首先检查是否因插入而破坏了平衡,若 破坏,则找出其中的最小不平衡二叉树,在保持二叉排序树特性的情况下,调整最小不平衡子树中节点之间的关系,以达 到新的平衡。所谓最小不平衡子树 指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树

    1. 查找操作

           平衡二叉树的查找基本与二叉查找树相同。

     

    2. 插入操作

           在平衡二叉树中插入结点与二叉查找树最大的不同在于要随时保证插入后整棵二叉树是平衡的。那么调整不平衡树的基本方法就是: 旋转 。 下面我们归纳一下平衡旋转的4中情况

    1) 绕某元素左旋转  

                                     80                                    90  

                                     /  \             左旋               /    \ 

                                   60 90          ---- ->         80     120 

                                        /  \                               /  \       / 

                                      85 120                    60  85 100 

                                           

                                          100     

                                   a)  BST树                              b ) AVL树

         分析一下:在插入数据100之前,a图的B ST树只有80节点的平衡因子是-1(左高-右高),但整棵树还是平衡的。加入100之后,80节点的平衡因子就成为了-2,此时平衡被破坏。需要左旋转成b 图。

         当树中节点X的右孩子的右孩子上插入新元素,且平衡因子从-1变成-2后,就需要绕节点X进行左旋转。

     

    2) 绕某元素右旋转  

                                    100                                   85 

                                     /  \               右旋              /    \ 

                                  85  120         ------ ->     60    100  

                                  /  \                                      \      /   \ 

                                60 90                                 80  90 120 

                                 

                                  80

                                 a) B ST树                                b) AVL树

         当树中节点X的左孩子的左孩子上插入新元素,且平衡因子从1变成2后,就需要绕节点X进行右旋转。

     

    3) 绕某元素的左子节点左旋转,接着再绕该元素自己右旋转。 此情况下就是左旋与右旋 的结合,具体操作时可以分 解成这两种操作,只是围绕点不一样而已。

                                                           

                                100                             100                                90 

                                 /  \             左旋            /  \              右旋           /    \ 

                              80  120       ------>      90  120        ------>     80   100  

                              / \                                  /                                    /  \      \ 

                           60 90                            80                              60  85  120 

                                /                               / \ 

                              85                            60 85 

          当树中节点X的左孩子的右孩子上插入新元素,且 平衡因子从1变成2后,就需要 先绕X的左子节点Y左旋转,接着再绕X右旋转

     

    4) 绕某元素的右子节点右旋转,接着再绕该元素自己左旋转。 此情况下就是 右旋与左旋 的结合,具体操作时可以分解 成这两种操作,只是围绕点不一样而已 。

     

                                   80                               80                                       85  

                                   /   \             旋          /  \                             /  \     

                                60  100      ------>      60 85            ------->          80 100 

                                       /  \                                 \                                   /     /   \       

                                    85  120                        100                           60    90 120 

                                       \                                   /  \ 

                                       90                           90  120

           当树中节点X的右孩子的左孩子上插入新元素,且 平衡因子从-1变成-2后,就需要 先绕X的右子节点Y右旋转,接着再绕X左旋转

     

    转载于:https://www.cnblogs.com/hu-yewen/p/5542591.html

    展开全文
  • 具体如何旋转平衡二叉树保持继续平衡的,可以参考如下的两个博客和一本书。 https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm http://btechsmartclass.com/DS/U5_T2.html ...

    平衡二叉树的旋转

    理解清楚平衡二叉树的概念。具体如何旋转是平衡二叉树保持继续平衡的,可以参考如下的两个博客和一本书。

    https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm

    http://btechsmartclass.com/DS/U5_T2.html

    《数据结构C++》作者王红梅等

    上面两个博客的讲的4种旋转类型与我们国内数据结构相关书籍的概念表述上有点差异,看完一定可以解惑。

    展开全文
  • 平衡二叉树 ​ 平衡二叉搜索树,又被称为...那么平衡二叉树如何保持”平衡“呢?根据定义,有两个重点,一是左右两子树的高度差的绝对值不能超过1,二是左右两子树也是一颗平衡二叉树。  如下图所示,左图是一棵平.
  • 平衡二叉树旋转

    2017-04-05 09:08:00
    1、 如何回溯修改祖先结点的平衡因子 我们知道,在AVL树上插入一个新结点后,有可能导致其他结点BF值的改变,哪些结点的BF值会被改变?如何计算新的BF值呢?要解决这些问题,我们必须理解以下几个要点: l 只有根...
  •   我们知道在二叉查找树中,如果插入元素的顺序接近有序,那么二叉查找树将退化...如何使得二叉查找树无论在什么样情况下都能使它的形态最大限度地接近满二叉树以保证它的查找效率呢? 前苏联科学家G.M. Adels...
  • 一、基本概念:平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。二、四种旋转情况...
  • 问题1:如何构建一颗平衡二叉树? ​ 在构建二叉排序树的时候,每添加一个结点,判断根结点的左右子树的高度差,若大于1,则需要进行相应的处理。 问题2:处理分为哪几种情况,每种情况需要做什么处理? ​ 当当前...
  • avl树的平衡是通过旋转平衡子树完成的,旋转如何完成的?这有幅不错的图http://upload.wikimedia.org/wikipedia/en/1/15/Tree_Rotations.gif 转载于:https://www.cnblogs.com/argb/p/3174227.html...
  • 一棵平衡的二叉树的平衡因子只能是1,0,-1如何构建一棵平衡二叉树呢?对一棵平衡的二叉树进行插入操作,插入后,可能导致不平衡,对不平衡的二叉树应该进行旋转操作,将其旋转平衡二叉树平衡二叉树应该具有...
  • 平衡二叉树的创建,RR旋转,LL旋转,RL旋转,LR旋转,插入、删除和一些其他操作。 平衡二叉树只是一种特殊的二叉排序树,其左右子树的高度差小于1。 左旋、右旋、左旋后右旋、右旋后左旋的理解:实际就是通过左右...
  • 平衡二叉树:或者是一棵空树,或是具有下列性质的二叉树:它的左子树和右...那如何使二叉排序树变为平衡二叉树呢?通过各种旋转 LL顺时针,RR逆时针,LR:先RR再LL,RL:先LL再RR 什么时候需要单旋转,而什么时候...
  • 平衡二叉树 AVL 的插入节点后旋转方法分析

    千次阅读 多人点赞 2013-10-28 21:02:11
    平衡二叉树 AVL( 发明者为Adel'son-Vel'skii 和 Landis)是一种二叉排序树,其中每一个节点的左子树和右子树的高度至多等于1。 首先我们知道,当插入一个节点,从此插入点到树根节点路径上的所有节点的平衡都可能被...
  • AVL 自平衡二叉树

    2020-08-13 11:46:06
    平衡二叉树平衡二叉树也叫平衡二叉搜索树(self-balancing binary search tree),又被称为AVL树,可以保证查询效率较高。平衡二叉树的左右两颗子树的高度差的绝对值不超过1,并且左右子树都是平衡二叉树。如下...
  • 今天来学习一下,给定一颗二叉树,如何判断这个二叉树是否为平衡二叉树。不平衡二叉树给出如上二叉树,它是不平衡的,输出 false。判断一颗二叉树是否平衡,就要看它的所有节点是否平衡;而判断一个节点是否平衡就是...
  • 平衡二叉树的插入:方法一、LL平衡旋转(右单旋转)方法二、RR平衡旋转(左单旋转)方法三、LR平衡旋转(先右后左双旋转)方法四、RL平衡旋转(先右后左双旋转平衡二叉树的定义: 如何计算高度为h的最小平衡...
  • 平衡二叉树 AVL( 发明者为Adel'son-Vel'skii 和 Landis)是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1。 首先我们知道,当插入一个节点,从此插入点到树根节点路径上的所有节点的平衡都...
  • 这里就不一一解释了,网上好多介绍如何旋转的。 ps:对于我来说的难点。函数里面调用函数,始终有点晕,搞不清楚原理。从网上看了好多代码,最后终于搞清了原理,也最终写出了平衡二叉树。 直接上代码: #include...
  • 平衡二叉树

    2018-10-23 23:18:32
    那么如何优化,AVL树(源于发明者的名字)。之前对于其左旋右旋一知半解,现在想记录一下自己现在的想法: 首先应该明白左旋右旋的基本操作。左旋:旋转节点的右子树不变,左子树变为根节点的右子树。右旋:旋转节点...
  • 一棵平衡的二叉树的平衡因子只能是1,0,-1如何构建一棵平衡二叉树呢?对一棵平衡的二叉树进行插入操作,插入后,可能导致不平衡,对不平衡的二叉树应该进行旋转操作,将其旋转平衡二叉树平衡二叉树应该具有...
  • 如何构建平衡二叉树(AVL树)

    万次阅读 2013-10-19 16:38:07
     平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 二、四种旋转情况 ...
  • 平衡二叉树实战 **题目描述:**输入一系列权值,按输入顺序构成平衡二叉树,输出根节点的权值。...如何构成平衡二叉树? 顺序插入节点,当发现不满足平衡二叉树的性质,则对树进行旋转旋转规则如下: 1)LL(...
  • 不管是从根节点还是从最小不平衡二叉树开始旋转平衡,可能都会出现一次遍历无法平衡的情况(会出现连锁反应)。 如果整棵树可以做到随时完全平衡处理,那就可以实现增加子树及删除子树的操作了。
  • 什么叫平衡二叉树 为什么要平衡二叉树如何判断失衡情况(RR、LL、RL、LR) 平衡二叉树的四种情况? 失衡: 失衡树: 失衡子树: RR型:整颗失衡树向左旋转一个单位 LL型:整颗失衡树向右旋转一个单位 RL...

空空如也

空空如也

1 2 3 4 5
收藏数 93
精华内容 37
关键字:

平衡二叉树如何旋转