平衡二叉樹算法詳解

1、平衡二叉樹算法詳解寫的有點兒俗，理論性不是很強，不過還算通俗易懂?？傊?，謝謝上位大俠的解釋平衡二叉樹定義(AVL):它或者是一顆空樹，或者具有每以下性質(zhì)的二叉樹：它的左子樹和右子樹的深度之差的絕對值不超過1,且它的左子樹和右子樹都是一顆平衡二叉樹。平衡因子(bf):結點的左子樹的深度減去右子樹的深度，那么顯然-1=bf“兩個結點的變換”如圖：一個二雲(yún)拉序楓：10190100/可不可區(qū)變成逵樣：100可不可比變成遠樣11D09010190101你發(fā)現(xiàn)了件么？100101100變成了進樣變成了這拝就拿第一個來說-點100和101的變換：點101占據(jù)點100的位置，點100換到了101的對面的位置，

2、其他點的相對位置不變。我們可以更直觀的理解為：把101結點“上提”一下！分析：101100,所以100可以作為101的左孩子；也就是在二叉排序樹中，兩個結點這樣的變換操作是可行的，是符合二叉排序樹的性質(zhì)。不僅這個簡單的圖,任何復雜的二叉排序樹都可以,你可以試試,也許你會說如果點101左邊有孩子怎么辦？別著急,當然有辦法下邊正式說這個圖的四種不平衡情況(插入時)及操作：首先還需要明白一個概念-最小不平衡子樹的根結點：也就是當你進行插入操作時，找到該需要插入結點的位置并插入后，從該結點起向上尋找(回溯)，第一個不平衡的結點即平衡因子bf變?yōu)?2或2。為什么要引入這個最小不平衡根結點的概念，因為在插

3、入時，對該子樹進行保持平衡操作后，其它的結點的平衡因子不會變，也就是整棵樹又恢復平衡了。為什么呢？你想想不平衡點的bf定是-2或2吧，經(jīng)過平衡操作后，他會把一邊子樹的一個結點分給另一邊的子樹，也就是一邊的深度分給另一邊，這樣就平衡了！比如，插入前：左邊是深度1,右邊深度是0;插入后左邊深度是2,右邊深度是0,經(jīng)過平衡后左邊深度是1,右邊深度是1;那么你說插入前和插入后該根結點所領導的子樹的深度變沒？仍是1，顯然沒變！那么就仍保持了這棵樹的平衡了！下面即四種情況分別為：左左、右右、左右、右左，每種情況又有兩個圖：、，是該情況的最簡單的圖形，是該情況的一般的圖形;設x為最小不平衡子樹的根結點，y為

4、剛插入的點左左：即在x的左孩子a的左孩子c上插入一個結點y（該結點也可以是c,如圖），即y可以是c,也可以是c的左孩子（如圖），也可以是c的右孩子（不在畫出）圖就不用說了，結點x和結點a變換，則樹平衡了；那么圖就是樹中的一般情況了a結點有右孩子d,那要進行x和a變換，那么a的右孩子放哪啊？很簡單，如圖放在x的左孩子上；分析：xd,da,所以d可作為x的左孩子，且可作為a的右孩子中的孩子。下邊這樣的類似情況不再一一分析，自己分析分析實現(xiàn)：找到根結點x,與它的左孩子a進行交換即可使二叉樹樹再次平衡；右右：即在x的右孩子a的右孩子c上插入一個結點y（該結點也可以是c,如圖），即y可以是c,也可以是c

5、的右孩子（如圖），也可以是c的左孩子（不在畫出）Oxxa/aa-ba-/、b實現(xiàn)：找到根結點x,與它的右孩子a進行交換即可使二叉樹樹再次平衡;左右：即在x的左孩子a的右孩子c上插入一個結點y（該結點也可以是c,如圖），即y可以是c,也可以是c的右孩子（如圖），也可以是c的左孩子（不在畫出）這個左右和下邊的右左，稍微復雜了點，需要進行兩次交換，才能達到平衡，注意這時y是c的右孩子，最終y作為x的左孩子；若y是c的左孩子，最終y作為a的右孩子，畫圖分析一下下邊類似，不再敖述。實現(xiàn)：找到根結點x,讓x的左孩子a與x的左孩子a的右孩子c進行交換，然后再讓x與x此時的左孩子c進行交換，最終達到平衡;右左

6、：即在x的右孩子a的左孩子c上插入一個結點y（該結點也可以是c,如圖），即y可以是c,也可以是c的右孩子（如圖），也可以是c的左孩子（不在畫出）實現(xiàn)：找到根結點x,讓x的右孩子a與x的右孩子a的左孩子c進行交換，然后再讓x與x此時的右孩子c進行交換，最終達到平衡;上邊的四種情況包含了所有插入時導致不平衡的情況，上面給出的僅僅是一棵大樹中的最小不平衡子樹，一定要想清楚，別迷了！另外一定要注意這個交換操作，比如a與b交換（a在上，b在下），b定要占據(jù)a的位置！什么意思？就是b要放在（覆蓋）儲存a的那塊內(nèi)存上,再通俗點說，若a是x的左孩子，則交換后b要做x的左孩子；這就是所謂的b占據(jù)a的位置！那么如

7、何找到最小不平衡子樹的根結點x,并判斷出它是屬于那種情況的？插入一個結點時，我們首先找到需要插入的位置，并插入；數(shù)據(jù)結構上用的是遞歸，不要說遞歸太浪費時空，你想想一個含2人31個結點的平衡二叉樹的深度大約是31吧，它遞歸再多也不就是31層！而且遞歸代碼短小、精悍、富含藝術之美！所以我認為對于這個平衡二叉樹，用遞歸很合適！顯然插入之后就要檢查是否出現(xiàn)不平衡的結點,那么如何檢查？我們知道,你插入的時候用的是遞歸,一條線找到要插的位置,并插入；那么誰的平衡因子的有可能變呢？不難想象，只有該條線上的結點的平衡因子有可能改變！那么我們在回溯的時候不就可以找到第一個不平衡的子樹的結點？！可是我們?nèi)绾闻袛嘣?/p>

8、結點的平衡因子是否應該改變，顯然要看它被插入結點的一邊的深度是否增加；如何看它被插入結點的一邊的深度是否增加？x:bf=-lx:bf=-lx:b=-2Va:sf=O-a:b1-a:bf=-1如上圖，如何看x的右孩子a（即被插入結點的一邊）的深度增加？我們知道在a的右孩子上插入了結點y那么a的bf是一定要減1那么x結點的bf?可根據(jù)a的bf決定是否改變！若a:bf=-1或1,那么a之前一定為0,表示a的深度增加了，那么x的bf可根據(jù)a是x哪一邊的孩子決定+1或-1;若a:bf=0,那么a之前一定為-1或1,表示a的深度沒增加，那么不僅x的bf就不用變，該條線上的所有結點的bf都不用變，直接返回即

9、可；當然了，那么找到最小不平衡子樹的根結點x了，如何判斷它屬于哪種不平衡呢？根據(jù)上邊的幾種情況，我們需要知道兩個方向，在回溯時可以記錄一下該結點到下一個結點的方向0:左、1:右為第二個方向，傳遞給上一層中，那么上層中的方向就是一個方向，有了這兩個方向就能確定是哪種不平衡了。還就上邊的圖說吧可以定義一個全局變量secdirection（第二個方向），也可在遞歸中定義一個局部變量，返回給上一層。在回溯到a中時，secdirection=1,到x的時候x-a的方向也為1,定義firdirection=1;而這時x:bf=-2;那么就找到了最小不平衡子樹的根結點x,又知道了兩個方向，那么進行相應的平衡

10、操作不就行了。其實我代碼中的就是按照寫的，可是剛又想了，其實不用用個變量記錄第二個方向，可以根據(jù)a的bf確定它的第二個方向，a:bf=-1說明右孩子的深度增加，y加到右孩子上；a:bf=1;說明左孩子的深度增加，y加到左孩子上；好了，找到了最小不平衡子樹的根結點x了，也知道了那種不平衡，調(diào)用keepbalance（.J就使樹平衡了，可是某些結點的平衡因子在變換是變了咋辦？我就是一種一種情況推出來的，不知道別人怎么變的，每一種情況都有固定的幾個點變了，變成了一個固定的值！誰有更好的辦法，請多多指教！下邊一一列出（插入操作中）變換后bf改變的結點及值：左左：前a-bf=1后x-bf=0,a-bf=

11、0；右右：前a-bf=-1后x-bf=0,a-bf=0；顯然左左與右右的x與a變換后的bf都為0；左右、右左中結點bf的改變要根據(jù)之前c的bf！左右：若c-bf=1,則x-bf=-1,a-bf=0,c-bf=0；若c-bf=-1,則x-bf=0,a-bf=1,c-bf=0；若c-bf=0,則x-bf=0,a-bf=0,c-bf=0；右左：若c-bf=1,則x-bf=0,a-bf=-1,c-bf=0；若c-bf=-1,則x-bf=1,a-bf=0,c-bf=0；若c-bf=0,則x-bf=0,a-bf=0,c-bf=0；可以發(fā)現(xiàn)，當左右、右左的c-bf相同時x與a的bf剛好取相反的值。好了，到現(xiàn)

12、在插入一個結點的二叉樹終于平衡了，相應的平衡因子也修改了！插入算是完成了！刪除時：刪除類似插入的操作，蛋又不同，刪除會有一些特殊情況需要特殊處理，當然核心操作“保持平衡”是不變的！刪除時少一個結點，也就是該結點所在的子樹深度可能會減小，而插入時多一個結點，該結點所在的子樹深度可能會增加,所以遞歸刪除一個結點時，回溯時找到最小不平衡子樹的根結點時，要向相反的方向去找屬于哪種情況；如圖：y為要刪除的結點；TOC o 1-5 h z/a/Ya-/aY/xcfb匚cb圖：y結點刪除后，回溯到x結點x:bf=-1變?yōu)閤:bf=-2;則需從相反方向即從x的右孩子的方向向下檢查屬于哪種情況，顯然第一個方向為

13、1：右；第二個方向看a:bf的值一一若為1時，那就相當于插入時右左的情況；若為-1時，那就相當于插入時左左的情況；可現(xiàn)在a:bf既不是1也不是-1而是0,這就是刪除的特殊情況了！我們不妨試試對他進行類似于插入時的右右操作，看怎么樣如上圖，經(jīng)過變換后該子樹平衡了！但是因子的修改就跟插入時的右右不一樣了！此時變?yōu)椋簒:bf=-1,a:bf=1；所以我們不妨就把a:bf=0也歸納為刪除的右右或左左（如圖，不再敖述）操作；那么刪除時因子的改變需在插入時因子的改變中添加上：左左：前a:bf=0后x:bf=1,a:bf=-1；右右：前a:bf=0后x:bf=-1,a:bf=1；其他不變！插入時結束結點平衡

14、因子的修改，直接返回（也就是該樹已經(jīng)平衡了）：回溯時發(fā)現(xiàn)兒子結點的平衡因子為0（當發(fā)現(xiàn)不平衡結點，并進行平衡操作后，平衡后根結點的bf定為0,也結束了）但是刪除時結束結點平衡因子的修改，直接返回，就與插入時不一樣了：回溯時發(fā)現(xiàn)兒子結點的平衡因子為-1或1!再刪除操作中,平衡一個子樹后,該子樹的深度不一定不變,而只有上邊那種特殊情況該子樹的深度不變,其他都會變！可以想象，其實是很簡單的道理：除了特殊情況其他都與插入的情況一模一樣，說白了就是把深度大的子樹（根結點的其中一個）向深度小子樹貢獻一個深度,那么這樣一來，該子樹（對于根結點所領導的樹）的深度是不是比原來的小1了？！所以要繼續(xù)向上一個一個進

15、行檢索，直到根結點為止！好了，到這里刪除也算是說完了，可以貼代碼了吧平衡二叉樹的C實現(xiàn):ViewCode#include#include#includetypedefintElemtype;typedefstructBalanced_Binary_TreeElemtypee;intbf;structBalanced_Binary_Tree*child2;*AVL;/簡單的位操作voidsetbit(char*i,charval,charpos)if(pos=1)(*i)=(*i)|1;elseif(val=1)(*i)=(*i)|2;else(*i)=(*i)&1;chargetbit(cha

16、ri,charpos)/調(diào)試時，發(fā)現(xiàn)這里能返回2/return(i&pos);出錯的地方return(i&pos)&1;/生成一個結點AVLcreatenode(Elemtypee)AVLnode=NULL;node=(AVL)malloc(sizeof(structBalanced_Binary_Tree);node-e=e;node-bf=0;node-child0=node-child1=NULL;returnnode;/AVL的核心操作*/保持平衡改變因子函數(shù)voidsetfactor(AVLf,intbutton)charfir=button/10,sec=button%10;AVL

17、s=f-childfir,ss=s-childsec;charchoice=ss-bf;inta=1,b=0;調(diào)試時發(fā)現(xiàn)，刪除時的特殊情況/插入時，不會有這種情況，若button=O,則s-bf=1/若button=11,則s-bf=-1;然而刪除時，卻會出現(xiàn)/button=0或者button=11時s-bf=0/那么這種特殊情況，平衡后所得的因子就跟一般的7/那么這種特殊情況，平衡后所得的因子就跟一般的/不一樣了如下/if(button=0&s-bf=O)f-bf=1,s-bf=-1;elseif(button=11&s-bf=O)f-bf=-1,s-bf=1;/elseif(button=

18、0|button=11)f-bf=0;s-bf=0;else/寫博客時，發(fā)現(xiàn)這里有問題/if(button=1)choice=-choice;/但是為什么我測試的時候怎么都對?!/經(jīng)再次測試，上邊確實錯了/改為下邊應該就對了口吧if(button=1)aA=b,bA=a,aA=b;if(choice=-1)f-bf=a,s-bf=b;elseif(choice=0)f-bf=s-bf=0;elsef-bf=-b,s-bf=-a;ss-bf=0;兩節(jié)點變換函數(shù)voidconversion(AVL*T,chardirection)AVLf=*T,s=f-childdirection;f-child

19、direction=s-child!direction;s-child!direction=f;*T=s;保持平衡函數(shù)voidkeepbalance(AVL*T,charfir,charsec)AVL*s=&(*T)-childfir);intbutton=fir*10+sec;if(button=0|button=11)setfactor(*T),button);conversion(T,fir);elsesetfactor(*T),button);conversion(s,sec);conversion(T,fir);/插入時的選向操作voidselectforInsert(AVL*T,c

20、har*info,intdirection)AVLcur=*T;charfirdirection,secdirection;if(direction=0)(cur-bf)+;else(cur-bf)-;if(cur-bf=0)setbit(info,1,1);if(cur-bf=O)setbit(info,1,1);elseif(cur-bf=-1|cur-bf=1)setbit(info,direction,2);elsefirdirection=direction;secdirection=getbit(*info,2);keepbalance(T,firdirection,secdire

21、ction);setbit(info,1,1);/*插入操作*/charInsertAVL(AVL*T,Elemtypee)/可用于查詢charinfo;if(!(*T)(*T)=createnode(e);return0;elseif(*T)-e=e)return-1;elseif(*T)-ee)/左info=InsertAVL(&(*T)-child0),e);if(getbit(info,1)returninfo;selectforInsert(T，&info,0);else右info=InsertAVL(&(*T)-child1),e);if(getbit(info,1)returni

22、nfo;selectforInsert(T，&info,1);returninfo;*、/刪除時的選向操作voidselectforDelete(AVL*T,char*info,chardirection)AVLcur=(*T);charfirdirection,secdirection;if(direction=0)(cur-bf)-;else(cur-bf)+;if(cur-bf=0)*info=0;elseif(cur-bf=-1|cur-bf=1)*info=1;elsefirdirection=!direction;/調(diào)試時，發(fā)現(xiàn)這里少寫了一個等號/if(cur-childfirdi

23、rection-bf=1)secdirection=0;草，真帥氣!原來1=a這樣寫確實有必要!if(1=cur-childfirdirection-bf)secdirection=0;/elsesecdirection=1;keepbalance(T,firdirection,secdirection);/調(diào)試時，發(fā)現(xiàn)經(jīng)過子樹平衡操作后，*info不一定都是0,就是那個特殊情況，在setfactor中/調(diào)試時，發(fā)現(xiàn)經(jīng)過子樹平衡操作后，*info不一定都是0,就是那個特殊情況，在setfactor中/的那種特殊情況時，這S*info應改為1!所以代碼改如下：/*info=1;寫代碼時：這跟插入

24、可不一樣啊該子樹平衡了，它父節(jié)點的因子比變！/*info=0;因此，這還沒完還要是0!啊這里不一定是0!還是那個特殊情況搞的鬼!/if(cur-bf=0)*info=0;else*info=1;/變向遞歸-輔助刪點charfind(AVL*gogal,AVL*p)charinfo;AVLtp=NULL;if(NULL!=(*p)-child0)info=find(gogal,&(*p)-child0);if(info!=0)returninfo;selectforDelete(p,&info,0);else(*gogal)-e=(*p)-e;tp=(*p)-child1;free(*p);*p

25、=tp;info=0;returninfo;/charDeleteAVL(AVL*T,Elemtypee)/*操*/charinfo;AVLtp=NULL;if(!(*T)return-1;/原if(!T)return-1;于2011年11月29日8:59:15修改elseif(*T)-e=e)if(NULL!=(*T)-child1)info=find(T,&(*T)-child1);if(info!=0)returninfo;selectforDelete(T,&info,1);else調(diào)試時，發(fā)現(xiàn)這樣寫不對7/(*T)=(p=(*T)-child0)-(free(*T),0);/Just

26、saveavariable!這里出問題/(*T)=p-(free(*T),0);可以/(*T)=(p=(*T)-child0)+(free(*T),0);不可以tp=(*T)-child0);free(*T);*T=tp;調(diào)試時，發(fā)現(xiàn)這里漏了給info賦值info=0;/elseif(*T)-ee)info=DeleteAVL(&(*T)-childO,e);if(info!=0)returninfo;selectforDelete(T,&info,0);elseinfo=DeleteAVL(&(*T)-child1,e);if(info!=0)returninfo;selectforDelete(T,&info,1);returninfo;*jUstFORTEST*/#defineMOVE(x)(x=(x+1)%1000)AVLqueue1000;voidprint(AV