1、算法導(dǎo)論思考題 P177: 13-3:AVL 樹主要思路：實(shí)現(xiàn)AVL樹的關(guān)鍵在于維持樹的平衡性。為了保證平衡， AVL樹中的每個(gè)結(jié) 點(diǎn)都有一個(gè)平衡因子，它表示這個(gè)結(jié)點(diǎn)的左、右子樹的高度差，也就是左子樹的 高度減去右子樹的高度的結(jié)果值。AVL樹上所有結(jié)點(diǎn)的平衡因子bal值只能是-1、 0、1。反之，只要二叉樹上一個(gè)結(jié)點(diǎn)的 bal的絕對(duì)值大于1，則該二叉樹就不是 平衡二叉樹。每當(dāng)插入一個(gè)節(jié)點(diǎn)或刪除都有可能破壞了樹的平衡性 。因此首先檢查是否破 壞了樹的平衡性，如果因插入結(jié)點(diǎn)而破壞了二叉查找樹的平衡， 則找出離插入點(diǎn) 最近的不平衡結(jié)點(diǎn)，然后將該不平衡結(jié)點(diǎn)為根的子樹進(jìn)行旋轉(zhuǎn)操作，稱該不平衡 結(jié)點(diǎn)為旋轉(zhuǎn)

2、根，以該旋轉(zhuǎn)根為根的子樹稱為最小不平衡子樹。要對(duì)樹進(jìn)行翻轉(zhuǎn)， 以滿足平衡性。翻轉(zhuǎn)使用的方法是紅黑樹中提到的左旋和右旋。 根據(jù)出現(xiàn)的不同 情況對(duì)樹進(jìn)行旋轉(zhuǎn)。歸納為4種旋轉(zhuǎn)類型：LL型旋轉(zhuǎn)、RR型旋轉(zhuǎn)、LR型旋轉(zhuǎn)、 RL型旋轉(zhuǎn)。1、LL型旋轉(zhuǎn):樹入結(jié)點(diǎn)2、LR型旋轉(zhuǎn):Bl Cl Cr Am3、RR型旋轉(zhuǎn):插入結(jié)點(diǎn)Al Bl &4、RL型旋轉(zhuǎn):醫(yī)入結(jié)點(diǎn)(d)上圖(a) (b) (c) (d)為四種類型的旋轉(zhuǎn)圖示證明:假設(shè)Nh是一顆高度為h的AVL樹中最小的節(jié)點(diǎn)數(shù):Nh Nh i Nh 21, No 0,Ni 1可以看到Nh的定義與斐波那契數(shù)列的定義非常相似FhFh i Fh 2, Fo 0,

3、 Fi1h f-)，則利用歸納法證明：當(dāng)h 0時(shí)Nh斤2 1，而Fh八5 (其中Nhh 2 / < 5 1。反之，含有n個(gè)結(jié)點(diǎn)的平衡樹的最大深度為log (、.5(n 1) 21.44log2(n 2) O(log n)。在平衡的的平衡二叉查找樹 Bala need BST上插入一個(gè)新的數(shù)據(jù)元素 e的遞 歸算法可描述如下：(1)若BBST為空樹，則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)作為BBST的根結(jié)點(diǎn)， 樹的深度增1； 若e的關(guān)鍵字和BBST的根結(jié)點(diǎn)的關(guān)鍵字相等，貝U不進(jìn)行；(3)若e的關(guān)鍵字小于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在 BBST的左子樹中不 存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在B

4、BST的左子樹上，并且當(dāng)插入之 后的左子樹深度增加(+1)時(shí)，分別就下列不同情況處理之：a、BBST的根結(jié)點(diǎn)的平衡因子為-1 (右子樹的深度大于左子樹的深度，則將 根結(jié)點(diǎn)的平衡因子更改為0，BBST的深度不變；b、BBST的根結(jié)點(diǎn)的平衡因子為0 (左、右子樹的深度相等)：則將根結(jié)點(diǎn)的 平衡因子更改為1，BBST的深度增1;c、BBST的根結(jié)點(diǎn)的平衡因子為1 (左子樹的深度大于右子樹的深度)：若 BBST的左子樹根結(jié)點(diǎn)的平衡因子為1：則需進(jìn)行單向右旋平衡處理，并且在右旋 處理之后，將根結(jié)點(diǎn)和其右子樹根結(jié)點(diǎn)的平衡因子更改為 0，樹的深度不變；(4)若e的關(guān)鍵字大于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在

5、BBST的右子樹中 不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在BBST勺右子樹上，并且當(dāng)插入 之后的右子樹深度增加（+1）時(shí)，分別就不同情況處理之。算法實(shí)現(xiàn)：#i nclude<stdio.h>#i nclude<malloc.h>#defi ne LH +1 / 左高#defi ne EH 0 /等高#defi ne RH -1 /右高typedef int ElemType;typedef struct BSTNodeElemType data;int bf;struct BSTNode *LChild,*RChild;BSTNode,*BSTree;/ LL型平衡

6、化旋轉(zhuǎn)void L_Rotate(BSTree &p) /對(duì)以*p為根的二叉查找樹作左旋處理，處理之后旋轉(zhuǎn)處理之前的右子樹的根結(jié)點(diǎn)BSTNode *rc;rc=p->RChild;p->RChild=rc->LChild;rc->LChild=p;p->bf=rc->bf=EH; /平衡因子修改p=rc;/p指向新的根結(jié)點(diǎn)/ RR 型平衡化旋轉(zhuǎn)void R_Rotate(BSTree &p) /對(duì)以*p為根的二叉查找樹作右旋處理，處理之后 旋轉(zhuǎn)處理之前的左子樹的根結(jié)點(diǎn)BSTNode *lc;lc=p->LChild;p->LChi

7、ld=lc->RChild;lc->RChild=p;p->bf=lc->bf=EH;p=lc;p指向新的樹根結(jié)點(diǎn)，即H指向新的樹根結(jié)點(diǎn)，即 void LeftBala nce(BSTree &T)指向新的根結(jié)點(diǎn)BSTree lc,rd;lc=T->LChild; /lc指向*T的左子樹根結(jié)點(diǎn)switch(lc->bf) / 檢查*T的左子樹平衡度，并作相應(yīng)平衡處理case LH: / 新結(jié)點(diǎn)插入在*T的左孩子的左子樹上，需要作單右旋處 理T->bf=lc->bf=EH;R_Rotate(T);break;case RH: / 新結(jié)點(diǎn)插入

8、在*T的左孩子的右子樹上，要作雙旋處理rd=lc->RChild; /rd指向*T的左孩子的右子樹的根switch(rd->bf) / 修改*T及其左孩子的平衡因子case LH:T->bf=RH;lc->bf=EH;break;case EH:T->bf=EH;lc->bf=EH;break;case RH:T->bf=EH;lc->bf=LH;break;rd->bf=EH;L_Rotate(T->LChild); /對(duì)*T的左子樹作左旋平衡處理R_Rotate(T); /對(duì)*T作右旋平衡處理 void RightBalance(

9、BSTree &T)BSTree ld,rc;rc=T->RChild;rc指向*T的左子樹根結(jié)點(diǎn)switch(rc->bf) case RH:T->bf=rc->bf=EH;L_Rotate(T);break;case LH: ld=rc->LChild; switch(ld->bf)case LH:T->bf=EH; rc->bf=LH; break;case EH:T->bf=EH; rc->bf=EH; break;case RH:T->bf=RH; rc->bf=EH; break;ld->bf=E

10、H;R_Rotate(T->RChild); L_Rotate(T);break;int In sert_AVL(BSTree & T,ElemType e,bool & taller) /若在平衡的二叉樹T中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元 素為e的新結(jié)點(diǎn)，并返回1,否則返回0.若因插入而使二叉排序樹失去平衡， 則 作平衡旋轉(zhuǎn)處理，布爾變量taller 反映T長(zhǎng)高與否if(!T) /插入新結(jié)點(diǎn)，樹“長(zhǎng)高”，置taller為trueT=(BSTree)malloc(sizeof(BSTNode);T->data=e;T->LChild=T->

11、;RChild=NULL;T->bf=EH; taller=true;else樹中已存在和e有相同關(guān)鍵字的結(jié)點(diǎn)不再插入if(e=T->data) /taller=false; /return 0;if(e<T->data) /應(yīng)繼續(xù)在T的左子樹中進(jìn)行搜索未插入if(!Insert_AVL(T->LChild,e,taller) /return 0;if(taller) /已插入到T的左子樹中且左子樹“長(zhǎng)高”switch(T->bf)/ 檢查T的平衡度case LH:LeftBala nce(T);taller=false;break;case EH:T-&g

12、t;bf=LH;taller=true;break;case RH:T->bf=EH;taller=false;break;else/應(yīng)繼續(xù)在T的右子樹中進(jìn)行搜索if(!I nsert_AVL(T->RChild,e,taller) /未插入return 0;if(taller) /已插入到T右子樹且右子樹長(zhǎng)高switch(T->bf)/ 檢查T的平衡度case LH:T->bf=EH;taller=false;break;case EH:T->bf=RH;taller=true;break;case RH: /原本右子樹比左子樹高，需要作右平衡處理RightBa

13、la nce(T);taller=false;break;return 1;void In OrderTraverse(BSTree &T)if(T)In OrderTraverse(T->LChild);prin tf("%dt%d",T->data,T->bf);prin tf("n");In OrderTraverse(T->RChild);void PreOrderTrave(BSTree & T,BSTree & HT,ElemType e)bool flag;if(T)if(T->data

14、!=e)In sert_AVL(HT,T->data,flag);PreOrderTrave(T->LChild,HT,e);PreOrderTrave(T->RChild,HT,e);void mai n()int i;bool flag;ElemType e;BSTree HT;HT=NULL;printf("請(qǐng)輸入數(shù)值(0為空樹):");sea nf("%d",&e);for(i=1;e!=0;i+)In sert_AVL(HT,e,flag);printf(" 請(qǐng)輸入數(shù)值(0為空樹):"); scan f("%d",&e);=n");=n");prin tf("n=中序遍歷平衡二叉樹In OrderTraverse(HT);prin tf("n");prin tf("n=指定查找平衡二