平衡二叉樹10.3.2.ppt

1、平衡二叉樹(AVL),平衡二叉樹的概念,平衡二叉樹的查找,平衡二叉樹中結(jié)點的插入與建立,平衡二叉樹中結(jié)點的刪除,平衡二叉樹(AVL),結(jié)點的平衡因子（balancdfactor用bf表示）:二叉樹中某結(jié)點左子樹的高度與右子樹的高度之差稱為該結(jié)點的平衡因子.平衡二叉樹是另一種形式的二叉查找樹。其特點是：左右子樹深度之差的絕對值不大于1稱有這種特性的二叉樹為平衡二叉樹。在算法中，可以通過平衡因子來具體實現(xiàn)平衡二叉樹的定義。從平衡因子的角度可以說，若一棵二叉樹中所有結(jié)點的平衡因子的絕對值小于或等于1，則該樹稱為平衡二叉樹。,96,38,24,88,28,11,25,98,0,1,0,1,1,1,0,

2、0,-1,-2,0,1、平衡二叉樹插入結(jié)點的調(diào)整方法,若向平衡二叉樹中插入一個新結(jié)點后破壞了平衡二叉樹的平衡性，首先從根結(jié)點到該新插入結(jié)點的路徑之逆向根結(jié)點方向找第一個失去平衡的結(jié)點，然后以該失衡結(jié)點和它相鄰的剛查找過的兩個結(jié)點構(gòu)成調(diào)整子樹(最小不平衡子樹)，即調(diào)整子樹是指以離插入結(jié)點最近,且平衡因子絕對值大于1的結(jié)點為根結(jié)點的子樹,使之成為新的平衡子樹。,96,38,24,88,28,11,25,98,2,(1)LL型調(diào)整,A,B,f,d,e,h,h,0,1,h,1,2,調(diào)整方法：單向右旋平衡，即將A的左孩子B向右上旋轉(zhuǎn)代替A成為根結(jié)點，將A結(jié)點向右下旋轉(zhuǎn)成為B的右子樹的根結(jié)點，而B的原右子

3、樹則作為A結(jié)點的左子樹。,B,A,d,e,f,lc=p-lchild;/*lc指向Bp-lchild=lc-rchild;/*把B結(jié)點的右子樹掛接為A的左子樹lc-rchild=p;/*A結(jié)點成為B的右孩子p=lc;/*p指向新的根結(jié)點,p,p,(2)RR型調(diào)整,A,a,B,b,c,h,h,0,1,調(diào)整方法：單向左旋平衡：即將A的右孩子B向左上旋轉(zhuǎn)代替A成為根結(jié)點，將A結(jié)點向左下旋轉(zhuǎn)成為B的左子樹的根結(jié)點，而B的原左子樹則作為A結(jié)點的右子樹。,B,A,c,a,b,-1,-2,lc=p-rchild;/*lc指向B*/p-rchild=lc-lchild;/*把B結(jié)點的左子樹掛接為A的右子樹*/

4、lc-lchild=p;/*A結(jié)點成為B的左孩子*/p=lc;/*p指向新的根結(jié)點*/,p,p,(3)LR型調(diào)整,A,B,C,n,m,i,e,h,h1,h1,0,0,1,1,1,2,C,B,A,n,m,i,e,調(diào)整方法：先左旋轉(zhuǎn)后右旋轉(zhuǎn)平衡,即將A結(jié)點的左孩子（即B結(jié)點）的右子樹的根結(jié)點（即C結(jié)點）向左上旋轉(zhuǎn)提升到B結(jié)點的位置，然后再把該C結(jié)點向右上旋轉(zhuǎn)提升到A結(jié)點的位置。,p,b,c,p-lchild=c-rchild;/*把C的右子樹掛接成A的左子樹*/b-rchild=c-lchild;/*把C的左子樹掛接成B的右子樹*/c-lchild=b;/*把B掛接成C的左子樹*/c-rchild

5、=p;/*把A掛接成C的右子樹*/,（4）RL型調(diào)整,A,B,m,C,f,n,t,C,A,B,m,n,t,f,h1,h,h1,調(diào)整方法：先右旋轉(zhuǎn)后左旋轉(zhuǎn)平衡,即先將A結(jié)點的右孩子B結(jié)點的左子樹的根結(jié)點C結(jié)點向右上旋轉(zhuǎn)提升到B結(jié)點的位置，然后再把該C結(jié)點向左上旋轉(zhuǎn)提升到A結(jié)點的位置。,0,0,1,-1,1,-2,p-rchild=c-lchild;/*把C的左子樹掛接成A的右子樹*/b-lchild=c-rchild;/*把C的右子樹掛接成B的左子樹*/c-rchild=b;/*把B掛接成C的右子樹*/c-lchild=p;/*把A掛接成C的左子樹*/,p,b,c,平衡二叉樹的查找,BSTNod

6、e*SearchBST(BSTNode*bt,KeyTypek)/在以bt為根的平衡二叉樹中,查找關(guān)鍵字為k的結(jié)點,找到返回指向該結(jié)點的/指針,否則返回NULLif(bt=NULL|bt-key=k)returnbt;if(kkey)returnSearchBST(bt-lchild,k);elsereturnSearchBST(bt-rchild,k);,平均查找長度為：O(log2n),平衡二叉樹中結(jié)點的插入與建立,在平衡二叉樹BBST中插入一個結(jié)點x的大體步驟如下：像一般的二叉排序樹那樣插入x；,若BBST為空樹，則插入一個數(shù)據(jù)元素為x的新結(jié)點作為BBST的根結(jié)點；若x的關(guān)鍵字和BBST

7、的根結(jié)點的關(guān)鍵字相等，不能進行插入；若x的關(guān)鍵字小于BBST的根結(jié)點的關(guān)鍵字，而且在BBST的左子樹中不存在和x有相同關(guān)鍵字的結(jié)點，則將x插入在BBST的左子樹上；若x的關(guān)鍵字大于BBST的根結(jié)點的關(guān)鍵字，而且在BBST的右子樹中不存在和x有相同關(guān)鍵字的結(jié)點，則將x插入在BBST的右子樹上；,沿著插入x的路線返回，逐層回溯，必要時修改x祖先的平衡因子，因為插入x后會使某些子樹的高度增加。回溯途中，一旦發(fā)現(xiàn)x的某個祖先p失衡，即由pbf=1變成p-bf=2或由p-bf=-1變成p-bf=-2,則旋轉(zhuǎn)以*p為根的子樹結(jié)構(gòu),使之平衡。,例1輸入關(guān)鍵字序列16,3,7,11,9,26,18,14,15

8、,給出構(gòu)造一棵AVL樹的步驟。,16,0,3,1,0,7,0,1,2,屬于“”型,應(yīng)該進行RL調(diào)整先右旋轉(zhuǎn)后左旋轉(zhuǎn)平衡,RL調(diào)整后,11,7,18,3,9,16,26,14,-1,2,0,1,-1,0,0,0,15,1,屬于“l(fā)child;If(p1-bf=1)p-lchild=p1-rchild;p1-rchild=p;p-bf=p1-bf=0;p=p1;elseif(p1-bf=-1)p2=p1-rchild;p1-rchild=p2-lchild;p2-lchild=p1;p-lchild=p2-rchild;p2-rchild=p;if(p2-bf=0)p-bf=p1-bf=0;els

9、eif(p2-bf=1)p1-bf=0;p-bf=-1;elsep1-bf=1;p-bf=0;p=p2;p-bf=0;Taller=0;,P-bf=1,要作LL調(diào)整,要作LR調(diào)整,平衡二叉樹中結(jié)點的刪除,在平衡二叉樹上刪除結(jié)點x（假定平衡二叉樹有且僅有一個結(jié)點的值等于x）的大體步驟如下：用一般的二叉排序樹的刪除算法找到并刪除結(jié)點x；沿根到被刪除結(jié)點的路線之逆逐層向上回溯，必要時，修改x祖先結(jié)點的平衡因子；回溯途中，一旦發(fā)現(xiàn)x的某個祖先p失衡，就要找到并調(diào)整其最小不平衡子樹，使之平衡；如果旋轉(zhuǎn)之后，子樹的總高度（比旋轉(zhuǎn)前）降低了，回溯不能停止。即在平衡二叉樹上刪除一個結(jié)點有可能引起多次旋轉(zhuǎn)。,若

10、x結(jié)點為葉子結(jié)點，由于刪去葉子結(jié)點不破壞整棵樹的結(jié)構(gòu)，則可直接刪去該結(jié)點；若x結(jié)點只有左子樹而無右子樹，根據(jù)二叉排序樹的特點，可以直接將其左子樹的根結(jié)點放在被刪去的結(jié)點的位置；若x結(jié)點只有右子樹而無左子樹，同樣根據(jù)二叉排序樹的特點，可以直接將其右子樹的根結(jié)點放在被刪去的結(jié)點的位置；若x結(jié)點同時有左子樹和右子樹，則根據(jù)二叉排序樹的特點，可以從其左子樹中選擇關(guān)鍵字最大的結(jié)點或者從其右子樹中選擇關(guān)鍵字最小的結(jié)點放在被刪去結(jié)點的位置。,平衡二叉樹的刪除,p,1,h,h,1,0,（a）,（a）pbf=1時在左子樹中刪除結(jié)點,刪除后,p-bf變?yōu)?.這時,*p結(jié)點仍平衡,但*p的高度降低,需要繼續(xù)向上回溯

11、;,(b),p,0,-1,h,-1,(b)p-bf=0時在左子樹中刪除結(jié)點,刪除后,p-bf變成-1,*p仍平衡,且*p高度不變,回溯至此停止;,(c),p,-1,-2,h,-1,h+1,平衡二叉樹的刪除,例:對下列AVL樹,給出刪除結(jié)點11,9,15的步驟.,刪除結(jié)點11,待刪除的結(jié)點同時有左子樹和右子樹，則根據(jù)二叉排序樹的特點，可以從其左子樹中選擇關(guān)鍵字最大的結(jié)點或者從其右子樹中選擇關(guān)鍵字最小的結(jié)點放在被刪去結(jié)點的位置。,7,18,3,9,15,26,14,16,11,9,voidDelete1(BSTNode*p,BSTNode*/*找到了最右下的結(jié)點,將其關(guān)鍵字賦給待刪除結(jié)點,并將其左

12、子樹的根結(jié)點放在被刪結(jié)點的位置上*/,7,18,15,26,14,16,9,7,-2,1,1,0,0,0,0,p,p1,p2,if(p2-bf=1)p-bf=0;p1-bf=-1;p2-bf=0;p=p2;,需作RL調(diào)整,RL調(diào)整后,7,18,3,14,16,26,刪除結(jié)點15,15,14,平衡二叉樹,#include#includetypedefintKeyType;/*定義關(guān)鍵字類型*/typedefcharInfoType;typedefstructnode/*記錄類型*/KeyTypekey;/*關(guān)鍵字項*/intbf;/*平衡因子*/InfoTypedata;/*其他數(shù)據(jù)域*/str

13、uctnode*lchild,*rchild;/*左右孩子指針*/BSTNode;,voidLeftProcess(BSTNode*,else/*原本左子樹比右子樹高,需作左子樹的平衡處理*/p1=p-lchild;/*p指向*p的左子樹根結(jié)點*/if(p1-bf=1)/*新結(jié)點插入在*b的左孩子的左子樹上,要作LL調(diào)整*/p-lchild=p1-rchild;p1-rchild=p;p-bf=p1-bf=0;p=p1;elseif(p1-bf=-1)/*新結(jié)點插入在*b的左孩子的右子樹上,要作LR調(diào)整*/p2=p1-rchild;p1-rchild=p2-lchild;p2-lchild=p

14、1;p-lchild=p2-rchild;p2-rchild=p;if(p2-bf=0)/*新結(jié)點插在*p2處作為葉子結(jié)點的情況*/p-bf=p1-bf=0;elseif(p2-bf=1)/*新結(jié)點插在*p2的左子樹上的情況*/p1-bf=0;p-bf=-1;else/*新結(jié)點插在*p2的右子樹上的情況*/p1-bf=1;p-bf=0;p=p2;p-bf=0;/*仍將p指向新的根結(jié)點,并置其bf值為0*/taller=0;,voidRightProcess(BSTNode*,elseif(p1-bf=1)/*新結(jié)點插入在*p的右孩子的左子樹上,要作RL調(diào)整*/p2=p1-lchild;p1-l

15、child=p2-rchild;p2-rchild=p1;p-rchild=p2-lchild;p2-lchild=p;if(p2-bf=0)/*新結(jié)點插在*p2處作為葉子結(jié)點的情況*/p-bf=p1-bf=0;elseif(p2-bf=-1)/*新結(jié)點插在*p2的右子樹上的情況*/p1-bf=0;p-bf=1;else/*新結(jié)點插在*p2的左子樹上的情況*/p1-bf=-1;p-bf=0;p=p2;p-bf=0;/*仍將p指向新的根結(jié)點,并置其bf值為0*/taller=0;,intInsertAVL(BSTNode*,voidDispBSTree(BSTNode*b)/*以括號表示法輸出A

16、VL*/if(b!=NULL)printf(%d,b-key);if(b-lchild!=NULL|b-rchild!=NULL)printf();DispBSTree(b-lchild);if(b-rchild!=NULL)printf(,);DispBSTree(b-rchild);printf();,voidLeftProcess1(BSTNode*,else/*需作RL調(diào)整*/p2=p1-lchild;p1-lchild=p2-rchild;p2-rchild=p1;p-rchild=p2-lchild;p2-lchild=p;if(p2-bf=0)p-bf=0;p1-bf=0;els

17、eif(p2-bf=-1)p-bf=1;p1-bf=0;elsep-bf=0;p1-bf=-1;p2-bf=0;p=p2;taller=1;,voidRightProcess1(BSTNode*,voidDelete2(BSTNode*q,BSTNode*,intDeleteAVL(BSTNode*,voidmain()BSTNode*b=NULL;inti,j,k;KeyTypea=16,3,7,11,9,26,18,14,15,n=9;/*例10.5*/printf(創(chuàng)建一棵AVL樹:n);for(i=0;in;i+)printf(第%d步,插入%d元素:,i+1,ai);InsertAVL(b,ai,j);DispBSTree(b);printf(n);printf(AVL:);DispBSTre