和记娱乐


网站导航

联系我们

和记娱乐

联系人: 

电 话:021-64057486

公司网址:http://www.happy123456789.com

   址:成都市松江区漕河泾松江新兴产业园区研展路丰产支路55号B座803室

邮编:201165


通信科技

您的当前位置: 和记娱乐主页 > 通信科技 >

30分钟让你掌握AVL树(平衡二叉树)

发布日期:2020-02-02 07:35 来源:和记h88 发布人:和记娱乐 点击:

  前言:本文不适合 给一组数据15分钟就能实现AVL的插入和删除操作的大牛(也请大牛不要打击小菜)。

  ps,你在嘲笑楼主的题目时,你已证明了自己正在嘲笑自己的智商。我们要善于征服陌生的事物。你如果有半个小时时间就心无的开始吧,那些读10分钟文章就心燥还是关闭浏览器吧。

  什么是二叉排序树(bst)二叉排序树(Binary Sort Tree)又称二叉查找树。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树;

  好了二叉排序树定义很好理解(如果还不理解,为了不浪费时间,先暂停一下,去google or baidu 下,理解了再继续),再此就不举别的例子了,下面我实现下BST的一些基本操作算法。BST的基本操作

  1.1 ,BST的搜索:为什么先实现搜索呢?一般BST里面没有重复的元素,你增添或者删除元素,都必须要先查找一下,看有没有呀,所以BST搜索要先实现,这个搜索是很简单的,慢慢看我吧,我们先看这张图

  假如你想找到数值为3的节点并给你这个树的根节点,且你只能看到这个根节点左右孩子(其他你们权限看到,也看不到)。那不就是很容易啦,先用3和根节点(此为6)比,显然比6小。那我就去找他的左孩子比,注意,此时4就是6的左子树的根了,那我们就和4这个新的树根比吧,显然又比4小。那我们就继续找这个新根的左孩子比,而此时3就是4的左子树的根了,那我们就和这个根比,哇塞,我们顺藤摸瓜,终于找到了哦!!,那我们就提炼一下这个过程吧,注意哦,我们每次都是和树根相比较的哦!规则:1.先和这棵树的根比2.如果比这个树根小就和这个树根的左子树的根比,否则就和这个树根的右子树比。3.重复2过程,直到根为空为止。 根据3个步骤很容易实现递归代码。//搜索元素,参数依次为0: 根节点,1: 查找的元素,2: 找到目标元素的前一个节点指针,初始值为NULL

  // 3:如果返回真把目标到元素的指针指向n,返回假,就把pre复制给n)(参数如果不明白,先不要细究,往下看吧)

  1.2 BST的增添元素算法实现有了搜索这个功能,那我们的增添元素的功能就很容易实现了,算法描述:1.先搜所以下所增添的key,在不在此树里面。2.如果没有找到,则申请空间,把key加入里面返回true,否则返回lse。

  如上图所示 我们要删除4这个节点,我们就把他双亲节点的左孩子指向4的左子树。简单吧!。那我么看第二种吧

  如上图所示我们所要删除的7节点只有右子树,想必一定想到了,那我们就把他双亲节点的右孩子指向7节点的右孩子,那不就ok啦,太棒了!!。现在看第三种情况吧。

  大家看出这三幅图的变化了吗?我们所要删除节点4,为了要保持树的顺序我们就要找比4大的且要离4最近的,那就是他的后继,当然你找前继也是可以的。此图是找他的后继。我们找到后就用4的后继替换4,最后删除后继这个节点。ok,大家看完并理解了这3种情况,那代码实现就很easy啦。

  终于搞完啦,咱也立马上机去测试吧,如果理解了,就自己测试吧,看能不能自己写出来哦!下面是我自己的测试

  到这为止二叉排序树已经搞定了,如果你自己也实现了上述功能,那证明你有很强的好奇心并且很有天赋(因为楼主搞了好几天才明白,你十几分就搞定了,那不是最好的证明吗?ps:楼主是那种很迟钝但很有毅力),有了前面的基础,AVL就是手到擒来,不要灰心哦,鼓足劲就继续征程吧。如果没有理解,先暂停会,避免浪费不必要的时间,就不要往下看了,反复认真看几遍,如果还不理解,可能这篇文章不适合你,参考其它文章。

  平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。

  平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1,这里我们定义:

  我们都知道,平衡二叉树是在二叉排序树(BST)上引入的(这一点很重要哦,下图为例),就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降,那么AVL就保持住了(BST)的最好时间复杂度O(logn),所以每次的插入和删除都要确保二叉树的平衡,那么怎么保持平衡呢?如果还不理解看看下面的图吧。

  图一和图二都是BST,但图是AVL,图一是AVL Tree,如果我们要找到10,图一比较次数为3,而图二比较次数为7次,很显然,在规模比较大的话AVL优势就很突出了。既然AVL这么强大,牛叉。那我们就把它拿下吧。2.1 AVL增添元素 这里搜索和BST搜索一样,我就不浪费时间介绍了,我们先实现增加元素的,实现然后删除元素的。可是每次的插入和删除都要确保二叉树的平衡,那么怎么保持平衡呢?我们就引入平衡因子。注意这里再看下平衡因子的定义我先演示下给一组数据,怎么组成一棵AVl Tree。。int a[]={4,3,2,7,9,11,10};1, 插入4,如图:

  ,显然4的平衡因子大于1了,为了保持平衡那我们就这样做:让4节点的左孩子指向3的右子树(此时为NULL),让3的右孩子指向4,让树根指向3,如图

  显然节点4不平衡了。那我们就把4的右孩子7的左子树(此时为NULL),让7的左孩子指向4,让3的右孩子指向7,如图:

  显然3节点,不平衡了,大家都应该知道以3为根进行左旋。让3的右孩子指向7的左子树(此时为4)。7的左孩子指向3,根指向7,如下图所示:

  显然节点9不平衡,且是右边高,那我们左旋吧,左旋后的效果是上图右图所示。显然这是不对的,10比11小,但在11的右孩子上。(根本原因是9和11的平衡因子符号不同)那我们在怎么办呢,看下图吧:

  成功离我们不远了,我们很容易的把这组数据拼出了AVl 树,是不是很有成就感呀。好啦,我们总结下插入元素的有哪些规律吧 1,如上所述的第3步,当插入元素后导致左边高,右边低,并且为4和3的平衡因子符号相同,则右旋。

  2, 如上所诉的第5步,当插入节点9后,导致以4为根的树右边高,左边低,4和7的平衡因子符号相同,则左旋 3,如上所述的第7步,当插入节点10后,导致以9为根的树右边高,左边低,由于9和11的平衡因子符号不同(也就是根和他的右孩子的平衡因子符号不同)不能进行左旋,正确操作:需要先右旋在左旋,要让根和根的右孩子平衡因子符号相同。 4,第4种旋转和3相反,当左边高于右边的话,且根和他的左孩子,平衡因子符号不同,需要先左旋再右旋恩,就是这么简单。在实现插入函数之前,我们先封装2个函数。RightBalance():当右高时需要右平衡时调用;

  //哈哈,两元猛将我们已经找到了,但是你看到这有点累了,但不要灰心,成功就在我们脚下,现在放弃,岂不是很可惜啦。那我们就实现插入元素的功能

  看到这了,自己出一组数据或按照我刚才用一组数据拼成avl的过程,看代码走一遍,你会有不一样的收货的哦(这其实非常重要),并插入了成功了,你已经成功99%了,没有想到自己这么厉害吧,我们接下来完成它的删除操作,我们就完美了。如果你有追求完美的目标,那就跟我走吧

  while (s)//如果所要删除的T节点右子树不为空,就找T的后继,也就是T的右孩子左子树的最左叶节点

  好吧,请原谅我骗了你,你看到这时,已不止半小时了。但为你使你相信你是有能力看完的,我不得不做这个下贱的谎言。 我不期望你能全部都能按照我的思写下去,因为我写的还不够好,哪怕你有一点收获,楼主也是值得的。

      和记娱乐,和记h88,h88平台官网