平衡二叉树 爱被打了一巴掌 2022-05-19 04:21 238阅读 0赞 *** 请要相信我,30分钟让你掌握AVL树(平衡二叉树)*** 前言:本文不适合 给一组数据15分钟就能实现AVL的插入和删除操作的大牛(也请大牛不要打击小菜) 本文适合,对avl还不了解,还没有亲自实现avl的插入和删除操作的同学 ps,你在嘲笑楼主的题目时,你已证明了自己正在嘲笑自己的智商。我们要善于征服陌生的事物。你如果有半个小时时间就心无杂念的开始吧,建议那些读10分钟文章就心燥还是关闭浏览器吧。 文章结构: ![Center][] *什么是二叉排序树(bst)* 二叉排序树(Binary Sort Tree)又称二叉查找树。 它或者是一棵空树;或者是具有下列性质的 [二叉树][Link 1]: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; ![Center 1][] ![Center 1][] 好了二叉排序树定义很好理解(如果还不理解,为了不浪费时间,先暂停一下,去google or baidu 下,理解了再继续),再此就不举别的例子了,下面我实现下BST的一些基本操作算法。 ***BST的基本操作*** typedef struct _BitNode { int data; struct _BitNode *lchild,*rchild; }BitNode,*BiTree; 1.1 ,BST的搜索: 为什么先实现搜索呢?一般BST里面没有重复的元素,你增添或者删除元素,都必须要先查找一下,看有没有呀,所以BST搜索要先实现,这个搜索是很简单的,慢慢看我讲解吧, 我们先看这张图 ![SouthEast][] 假如你想找到数值为3的节点并给你这个树的根节点,且规定你只能看到这个根节点左右孩子(其他你们权限看到,也看不到)。那不就是很容易啦,先用3和根节点(此为6)比,显然比6小。那我就去找他的左孩子比,注意,此时4就是6的左子树的根了,那我们就和4这个新的树根比吧,显然又比4小。那我们就继续找这个新根的左孩子比,而此时3就是4的左子树的根了,那我们就和这个根比,哇塞,我们顺藤摸瓜,终于找到了哦!!,那我们就提炼一下这个过程吧,注意哦,我们每次都是和 *树根*相比较的哦! 规则: 1.先和这棵树的根比 2.如果比这个树根小就和这个树根的左子树的根比,否则就和这个树根的右子树比。 3.重复2过程,直到根为空为止。 根据3个步骤很容易实现递归代码。 //搜索元素,参数依次为0: 根节点,1: 查找的元素,2: 找到目标元素的前一个节点指针,初始值为NULL // 3:如果返回真把目标到元素的指针指向n,返回假,就把pre复制给n)(参数如果不明白,先不要细究,往下看吧) bool SearchBST(BiTree T,int key,BiTree pre,BiTree&n); bool SearchBST(BiTree T,int key,BiTree pre,BiTree&n) { if(!T) { n=pre; //如果此数为空树,那我们就把前一个元素指针pre(此时为NULL)复制给n,注意树为空时,n才为NULL。 return false; //返回假没有找到 } else if(key==T->data) { n=T; //找到了就把目标元素指针给n return true; } if(key<T->data) SearchBST(T->lchild,key,T,n) ;//去找他的左子树根比 else { SearchBST(T->rchild,key,T,n);//去找他的右子树根比。 } } 1.2 BST的增添元素算法实现 有了搜索这个功能,那我们的增添元素的功能就很容易实现了, 算法描述: 1.先搜所以下所增添的key,在不在此树里面。 2.如果没有找到,则申请空间,把key加入里面返回true,否则返回false。 bool InsetBST(BiTree &T,int k) { BitNode* p; if(!SearchBST(T,k,NULL,p)) { BitNode * temp=new BitNode; temp->data=k; temp->lchild=temp->rchild=NULL; if(!p) //只有树为空时,此时的p才为NULL。看到这里应该明白SearchBST(T,k,pre,p)这些参数的意义了吧 { T=temp; } else { if(k<p->data) //如果不为空树,加入的key值就和p相比较,小于就是他的左孩子,否子为右孩子 p->lchild=temp; else { p->rchild=temp; } } return 0; } else { return false; } } 1.3BST删除元素的算法实现 既然看到这里了,证明你的好奇心很强,这一节看完,我们就离成功不远了,那我们继续吧! 删除总共有3种情况,1只有左子树;2,只有右子树;3,左右子树都有。 先看第一种 ![SouthEast 1][] 如上图所示 我们要删除4这个节点,我们就把他双亲节点的左孩子指向4的左子树。简单吧!。那我么看第二种吧 ![SouthEast 2][] 如上图所示我们所要删除的7节点只有右子树,想必一定想到了,那我们就把他双亲节点的右孩子指向7节点的右孩子,那不就ok啦,太棒了!!。现在看第三种情况吧。 ![Center 2][] ![Center 3][] ![Center 4][] 大家看出这三幅图的变化了吗?我们所要删除节点4,为了要保持树的顺序我们就要找比4大的且要离4最近的,那就是他的后继,当然你找前继也是可以的。此图是找他的后继。我们找到后就用4的后继替换4,最后删除后继这个节点。ok,大家看完并理解了这3种情况,那代码实现就很easy啦。 bool DeleElement(BiTree&T,int key) { if(!T) { return 0; //树是空树的话就返回假 } if(T->data==key) { BitNode*s,*p; if(T->rchild==NULL) //只有右子树,情况2 { s=T; T=T->lchild; free(s); } else if(T->lchild==NULL) { s=T; //只有左子树,情况1 T=T->rchild; free(s); } else { //情况3,左右子树都有 p=T; s=T->rchild; while (s->lchild) { p=s; //找到所要删除节点的后继,那就是他的右孩子的 s=s->lchild; } T->data=s->data; //用删除节点的后继替换所删除的节点 if(p!=T) { p->lchild=NULL; //所删除的节点的右孩子不是叶结点 } else p->rchild=NULL; //所删除的节点的右孩子是叶节点 free(s); } return 1; } else if(key<T->data) DeleElement(T->lchild,key); //去和他的左子树根去比较 else DeleElement(T->rchild,key); //去和他的右子树根去比较 } //中序遍历并输出元素 void InorderReverse(BiTree T) { if(T) { InorderReverse(T->lchild); cout<<T->data<<endl; InorderReverse(T->rchild); } } 终于搞完啦,咱也立马上机去测试吧,如果理解了,就自己测试吧,看能不能自己写出来哦!下面是我自己的测试 int main() { BiTree tree=NULL; int a[]={60,86,50,40,35,74,51,100,37,90}; for(int i=0;i<10;i++) InsetBST(tree,a[i]); InorderReverse(tree); cout<<" "<<endl<<endl; DeleElement(tree,62); InorderReverse(tree); return 0; } 到这为止二叉排序树已经搞定了,如果你自己也实现了上述功能,那证明你有很强的好奇心并且很有天赋(因为楼主搞了好几天才明白,你十几分就搞定了,那不是最好的证明吗?ps:楼主是那种很迟钝但很有毅力),有了前面的基础,AVL就是手到擒来,不要灰心哦,鼓足劲就继续征程吧。如果没有理解,先暂停会,避免浪费不必要的时间,就不要往下看了,建议反复认真看几遍,如果还不理解,可能这篇文章不适合你,建议参考其它文章。 什么是AVL 定义: 平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。 平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1,这里我们定义: \#define EH 0,\#define LH 1,\#define RH -1.依次为等高,左高,右高。 typedef struct \_BitNode \{ int data; int bf;//平衡因子 struct \_BitNode \*lchild,\*rchild; \}BitNode,\*BiTree; 我们都知道,平衡二叉树是在二叉排序树(BST)上引入的(这一点很重要哦,下图为例),就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降,那么AVL就保持住了(BST)的最好时间复杂度O(logn),所以每次的插入和删除都要确保二叉树的平衡,那么怎么保持平衡呢?如果还不理解看看下面的图吧。 ![Center 5][] 看看AVL的魅力吧。有它就有它存在的价值,看下图便知。 图一和图二都是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,如图: ![Center 6][], 平衡因子为0. 2, 插入3,如图: ![Center 7][],4的平衡因子因为4的左子树增长了,1-0=1, 3, 插入2,如图 ![Center 8][],显然4的平衡因子大于1了,为了保持平衡那我们就这样做:让4节点的左孩子指向3的右子树(此时为NULL),让3的右孩子指向4,让树根指向3,如图 ![Center 9][],这种操作我们规定为右旋操作,此图是以4为根进行旋转。 代码如下 void R_Rotate(BiTree&T) { BiTree p; // p=T->lchild; //假如此时T指向4,则p指向3; T->lchild=p->rchild; //把3的右子树挂接到4的左子树上(此例子3右子树为空) p->rchild=T; //让3的右孩子指向4. T=p; //根指向节点3 } 4,插入7,如图: ![Center 10][] 5,插入9,如图: ![Center 11][]显然节点4不平衡了。那我们就把4的右孩子7的左子树(此时为NULL),让7的左孩子指向4,让3的右孩子指向7,如图: ![Center 12][] ,我们规定此操作为左旋操作,此图是以4为根进行旋转,代码如下: void L_Rotate(BiTree&T) { BiTree p; p=T->rchild; //假如此时T指向4,则p指向7. T->rchild=p->lchild; //让7的左子树挂接到4的右子树上 p->lchild=T; //让7的左孩子指向4 T=p; //树根指向7 } 6.我们插入11,如图:![Center 13][] 显然3节点,不平衡了,大家都应该知道以3为根进行左旋。让3的右孩子指向7的左子树(此时为4)。7的左孩子指向3,根指向7,如下图所示: ![Center 13][] 7.我们插入10,如图:![Center 14][] 显然节点9不平衡,且是右边高,那我们左旋吧,左旋后的效果是上图右图所示。显然这是不对的,10比11小,但在11的右孩子上。(根本原因是9和11的平衡因子符号不同)那我们在怎么办呢,看下图吧: ![Center 15][] 成功离我们不远了,我们很容易的把这组数据拼出了AVl 树,是不是很有成就感呀。好啦,我们总结下插入元素的有哪些规律吧 1,如上所述的第3步,当插入元素后导致左边高,右边低,并且为4和3的平衡因子符号相同,则右旋。 2, 如上所诉的第5步,当插入节点9后,导致以4为根的树右边高,左边低,4和7的平衡因子符号相同,则左旋 3,如上所述的第7步,当插入节点10后,导致以9为根的树右边高,左边低,由于9和11的平衡因子符号不同(也就是根和他的右孩子的平衡因子符号不同)不能进行左旋,正确操作:需要先右旋在左旋,要让根和根的右孩子平衡因子符号相同。 4,第4种旋转和3相反,当左边高于右边的话,且根和他的左孩子,平衡因子符号不同,需要先左旋再右旋 恩,就是这么简单。在实现插入函数之前,我们先封装2个函数。 RightBalance():当右高时需要右平衡时调用; LeftBalance()功能:当左高时需要左平衡时调用; 右平衡函数代码: void RightBalance(BiTree&T) { BiTree R,rl; //调用此函数时,以T为根的树,右边高于左边,则T->bf=RH。 R=T->rchild; //R是T的右孩子 switch (R->bf) { case RH: //如果 T的右孩子和T他们的平衡因子符号相同时,则直接左旋,这是总结中的第2项 T->bf=R->bf=EH; L_Rotate(T); break; case EH: T->bf=RH; R->bf=LH; L_Rotate(T); break; case LH: //如果T的右孩子和T他们的平衡因子符合不同时,需要先以T的右孩子为根进行右旋,再以T为根左旋。 //rl为T的右孩子的左孩子 rl=R->lchild; //2次旋转后,T的右孩子的左孩子为新的根 。注意:rl的右子树挂接到R的左子树上,rl的左子树挂接到T的右子树上 switch (rl->bf) //这个switch 是操作T和T的右孩子进行旋转后的平衡因子。 { case EH: T->bf=R->bf=EH; //这些平衡因子操作,大家可以自己画图操作理解 下面的注解 break; 2次旋转后,T的右孩子的左孩子为新的根 。 //并且rl的右子树挂接到R的左子树上,rl的左子树挂接到T的右子树上,rl为新根 case RH: R->bf=EH; T->bf=LH; break; case LH: R->bf=RH; T->bf=EH; break; default: break; } rl->bf=EH; R_Rotate(T->rchild); //先左旋,以T->rchild为根左旋。 L_Rotate(T); //右旋,以T为根, 左旋后 T是和rl想等,rl是新根 break; } } void LeftBalance(BiTree&T) { BiTree L,lr; L=T->lchild; switch (L->bf) { case EH: L->bf=RH; T->bf=LH; R_Rotate(T); break; case LH: L->bf=T->bf=EH; R_Rotate(T); break; case RH: lr=L->rchild; switch (lr->bf) { case EH: L->bf=L->bf=EH; case RH: T->bf=EH; L->bf=LH; break; case LH: L->bf=EH; T->bf=RH; break; default: break; } lr->bf=EH; L_Rotate(T->lchild); R_Rotate(T); break; default: break; } } //哈哈,两元猛将我们已经找到了,但是你看到这有点累了,但不要灰心,成功就在我们脚下,现在放弃,岂不是很可惜啦。那我们就实现插入元素的功能 bool InsertAVLtree(BiTree&T,int key,bool&taller) { if(!T) //此树为空 { T=new BitNode; //直接作为整棵树的根。 T->bf=EH; T->lchild=T->rchild=NULL; T->data=key; taller=true; return true; } else { if(key==T->data) //已有元素,不用插入了,返回false; { taller=false; return false; } if(key<T->data) //所插元素小于此根的值,就找他的左孩子去比 { if(!InsertAVLtree(T->lchild,key,taller)) //所插元素小于此根的值,就找他的左孩子去比 return false; if(taller) //taller为根,则树长高了,并且插入到了此根的左子树上。 { switch (T->bf) //此根的平衡因子 { case EH: //原先是左右平衡,等高 T->bf=LH; //由于插入到左子树上,导致左高=》》LH taller=true; //继续往上递归 break; case LH: LeftBalance(T); //原先LH,由于插入到了左边,这T这个树,不平衡需要左平衡 taller=false; //以平衡,设taller为false,往上递归就不用进入此语句了, break; case RH: T->bf=EH; //原先RH,由于插入到左边,导致此T平衡 taller=false; break; default: break; } } } else { if(!InsertAVLtree(T->rchild,key,taller)) return false; if(taller) { switch (T->bf) { case EH: T->bf=RH; taller=true; break; case LH: T->bf=EH; taller=false; break; case RH: RightBalance(T); taller=false; break; default: break; } } } } //中序遍历输出 void InOrderReverse(BiTree&T) { if(T) { InOrderReverse(T->lchild); cout<<T->data<<endl; InOrderReverse(T->rchild); } } 看到这了,自己出一组数据或按照我刚才用一组数据拼成avl的过程,看代码走一遍,你会有不一样的收货的哦(这其实非常重要),并插入了成功了,你已经成功99%了,没有想到自己这么厉害吧,我们接下来完成它的删除操作,我们就完美了。如果你有追求完美的目标,那就跟我走吧 2.2AVL的删除操作 ![Center 16][] 下面我会贴出代码,根据代码把上图的元素删除掉吧,你会成功的 为了更好的理解,建议先把插入代码先实现。 删除代码和BST的删除相似,AVL删除元素后还要照顾好平衡。 bool DeletElement(BiTree&T,int key,bool&lower)//参数(0)树根,(1)删除的元素,(3)此树是否降低标志位 \{ bool L,R;//删除的是左子树还是右子树,作为标志。 L=R=false; if(T==NULL) // 判断树根是否为空 return false; if(key==T->data)//找到了所要删除的节点 \{ BitNode\* p,\*s; p=T->rchild; s=p; lower=true; //找到了必定删除,lower为真 if(T->rchild==NULL) // 如果所要删除的节点的右孩子为空 \{ p=T; T=T->lchild; //直接删除比如删除上图的 4,9,10, free(p); lower=true; return true; \} else \{ while (s)//如果所要删除的T节点右子树不为空,就找T的后继,也就是T的右孩子左子树的最左叶节点 \{ p=s; s=s->lchild; \} T->data=p->data;//替换T DeletElement(T->rchild,p->data,lower);//删除掉T的后继 R=true; \} \} else if(key<T->data) \{ DeletElement(T->lchild,key,lower); L=true; \} else \{ DeletElement(T->rchild,key,lower); R=true; \} if(lower)//如果有节点删除 \{ if(L)//删除的是左节点 \{ switch (T->bf) \{ case LH://没删之前LH,删后T->bf=EH; T->bf=EH; lower=true; break; case RH://没删之前RH,删后导致右不平衡, RightBalance(T); lower=false; break; case EH://没删之前EH,删后RH; T->bf=RH; lower=false; break; default: break; \} \} else \{ switch (T->bf) \{ case EH: T->bf=LH; lower=false; break; case RH: T->bf=EH; lower=true; break; case LH: LeftBalance(T); lower=false; break; default: break; \} \} \} \} 好吧,请原谅我骗了你,你看到这时,已不止半小时了。但为你使你相信你是有能力看完的,我不得不做这个下贱的谎言。 我不期望你能全部都能按照我的思路写下去,因为我写的还不够好,哪怕你有一点收获,楼主也是值得的。 [Center]: /images/20220519/d16fb09240554a9dac4b8716caa0e8df.png [Link 1]: http://baike.baidu.com/view/88806.htm [Center 1]: /images/20220519/a21f74631e4f454f952c096b5b0dee2b.png [SouthEast]: /images/20220519/0bbb84d74bc040b9a591d656218ca353.png [SouthEast 1]: /images/20220519/23d619d562164a7e8c4c23f346833369.png [SouthEast 2]: /images/20220519/c903d13b2ade418b857d69a270ea599f.png [Center 2]: https://img-blog.csdn.net/20130816112714125?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveW91cmVuaGVsbG8=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center [Center 3]: https://img-blog.csdn.net/20130816112750781?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveW91cmVuaGVsbG8=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center [Center 4]: /images/20220519/54ec48f3143d497e88219ec9914307be.png [Center 5]: /images/20220519/33422600d38748e08daad44fc5ce4f22.png [Center 6]: /images/20220519/ba5796b45b564897a6ff9353035dede7.png [Center 7]: /images/20220519/00435c7a060140f7a43b7d2ae5f8f8b6.png [Center 8]: https://img-blog.csdn.net/20130816113213500?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveW91cmVuaGVsbG8=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center [Center 9]: /images/20220519/65f613dedd31454c9b6437e8a857e7e2.png [Center 10]: /images/20220519/4e77c7d304004c62b8ee7bf39ea078e4.png [Center 11]: https://img-blog.csdn.net/20130816113409562?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveW91cmVuaGVsbG8=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center [Center 12]: /images/20220519/fb44e6d460254693ab79c7945dfb02e4.png [Center 13]: /images/20220519/8af1340cd3994352881a02e017a35af5.png [Center 14]: /images/20220519/d10a1ea712014b14bf252e69b5feaa14.png [Center 15]: /images/20220519/148a24dfbf0f429e8424bf1f1b222023.png [Center 16]: /images/20220519/056370e368514153ab017b83ea355dad.png
相关 平衡二叉树 <table style="width:1615px; margin-bottom:20px; background-color:transparent"> <tbody> 淡淡的烟草味﹌/ 2022年06月02日 07:59/ 0 赞/ 225 阅读
相关 平衡二叉树 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. 墨蓝/ 2022年05月28日 08:57/ 0 赞/ 395 阅读
相关 平衡二叉树 请要相信我,30分钟让你掌握AVL树(平衡二叉树) 前言:本文不适合 给一组数据15分钟就能实现AVL的插入和删除操作的大牛(也 爱被打了一巴掌/ 2022年05月19日 04:21/ 0 赞/ 239 阅读
相关 平衡二叉树 写在前面 > 剑指offer:平衡二叉树 题目要求 > 输入一棵二叉树,判断该二叉树是否是平衡二叉树。平衡二叉树要求任意一个节点的左右字数之间的高度差不超过1。 浅浅的花香味﹌/ 2022年05月17日 01:54/ 0 赞/ 266 阅读
相关 平衡二叉树 平衡二叉树又称AVL树。它或者是颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定 骑猪看日落/ 2022年05月17日 01:24/ 0 赞/ 239 阅读
相关 平衡二叉树 时间限制:1秒 空间限制:32768K 热度指数:160212 [ 算法知识视频讲解][Link 1] 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 向右看齐/ 2022年03月08日 01:44/ 0 赞/ 283 阅读
相关 平衡二叉树 平衡二叉树介绍 是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出,因此一般也称作AVL树,AVL树本质还是一棵二叉查找树,只是在其基础 青旅半醒/ 2022年02月24日 07:54/ 0 赞/ 323 阅读
相关 平衡二叉树 (平衡查找树) 平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上 小咪咪/ 2021年10月29日 07:24/ 0 赞/ 439 阅读
相关 平衡二叉树 package com.avl; / @Auther: 大哥的叔 @Date: 2019/8/18 06:12 @ 忘是亡心i/ 2021年10月15日 05:37/ 0 赞/ 386 阅读
相关 二叉平衡树 二叉平衡树 说起这个树,我找了整整两天的时间,刚开始考虑的不周全,然后就一直该一直该,一直加一直加。 定义: 它是一颗空疏或它的左右两个子树的高度差的绝对值不超过 Dear 丶/ 2021年09月22日 09:42/ 0 赞/ 440 阅读
还没有评论,来说两句吧...