算法導(dǎo)論AVL樹(shù)

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

2、最小不平衡子樹(shù)。要對(duì)樹(shù)進(jìn)行翻轉(zhuǎn)，以滿足平衡性。翻轉(zhuǎn)使用的方法是紅黑樹(shù)中提到的左旋和右旋。根據(jù)出現(xiàn)的不同情況對(duì)樹(shù)進(jìn)行旋轉(zhuǎn)。歸納為4種旋轉(zhuǎn)類(lèi)型：LL型旋轉(zhuǎn)、RR型旋轉(zhuǎn)、LR型旋轉(zhuǎn)、RL型旋轉(zhuǎn)。1、LL型旋轉(zhuǎn)：2、LR型旋轉(zhuǎn)：3、RR型旋轉(zhuǎn)：4、RL型旋轉(zhuǎn)：上圖（a）（b）（c）（d）為四種類(lèi)型的旋轉(zhuǎn)圖示。證明： 假設(shè) 是一顆高度為h的AVL樹(shù)中最小的節(jié)點(diǎn)數(shù)：可以看到的定義與斐波那契數(shù)列的定義非常相似利用歸納法證明：當(dāng)時(shí)，而（其中），則。反之，含有n個(gè)結(jié)點(diǎn)的平衡樹(shù)的最大深度為。 在平衡的的平衡二叉查找樹(shù)Balanced BST上插入一個(gè)新的數(shù)據(jù)元素e的遞歸算法可描述如下：(1)若BBST為空樹(shù)，則插

3、入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)作為BBST的根結(jié)點(diǎn)，樹(shù)的深度增1； (2)若e的關(guān)鍵字和BBST的根結(jié)點(diǎn)的關(guān)鍵字相等，則不進(jìn)行； (3)若e的關(guān)鍵字小于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在BBST的左子樹(shù)中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在BBST的左子樹(shù)上，并且當(dāng)插入之后的左子樹(shù)深度增加（+1）時(shí)，分別就下列不同情況處理之：a、BBST的根結(jié)點(diǎn)的平衡因子為-1（右子樹(shù)的深度大于左子樹(shù)的深度，則將根結(jié)點(diǎn)的平衡因子更改為0，BBST的深度不變；b、BBST的根結(jié)點(diǎn)的平衡因子為0（左、右子樹(shù)的深度相等）：則將根結(jié)點(diǎn)的平衡因子更改為1，BBST的深度增1；c、BBST的根結(jié)點(diǎn)的平衡因子為1（左子樹(shù)的

4、深度大于右子樹(shù)的深度）：若BBST的左子樹(shù)根結(jié)點(diǎn)的平衡因子為1：則需進(jìn)行單向右旋平衡處理，并且在右旋處理之后，將根結(jié)點(diǎn)和其右子樹(shù)根結(jié)點(diǎn)的平衡因子更改為0，樹(shù)的深度不變；（4） 若e的關(guān)鍵字大于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在BBST的右子樹(shù)中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在BBST的右子樹(shù)上，并且當(dāng)插入之后的右子樹(shù)深度增加（+1）時(shí)，分別就不同情況處理之。算法實(shí)現(xiàn)： #include#include#define LH +1 /左高#define EH 0 /等高#define RH -1 /右高typedef int ElemType;typedef struct BSTNodeE

5、lemType data;int bf; struct BSTNode *LChild,*RChild; BSTNode,*BSTree;/ LL型平衡化旋轉(zhuǎn)void L_Rotate(BSTree &p) /對(duì)以*p為根的二叉查找樹(shù)作左旋處理，處理之后p指向新的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的右子樹(shù)的根結(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為根的二叉查找樹(shù)作右旋處理

6、，處理之后H指向新的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的左子樹(shù)的根結(jié)點(diǎn)BSTNode *lc;lc=p-LChild; p-LChild=lc-RChild; lc-RChild=p; p-bf=lc-bf=EH; p=lc; void LeftBalance(BSTree &T) /對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，函數(shù)結(jié)束時(shí)，指針T指向新的根結(jié)點(diǎn)BSTree lc,rd;lc=T-LChild; /lc指向*T的左子樹(shù)根結(jié)點(diǎn)switch(lc-bf) /檢查*T的左子樹(shù)平衡度，并作相應(yīng)平衡處理case LH: /新結(jié)點(diǎn)插入在*T的左孩子的左子樹(shù)上，需要作單右旋處理T-bf=lc-bf=

7、EH;R_Rotate(T);break;case RH: /新結(jié)點(diǎn)插入在*T的左孩子的右子樹(shù)上，要作雙旋處理rd=lc-RChild; /rd指向*T的左孩子的右子樹(shù)的根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的左子樹(shù)作左旋平衡處理R_Rotate(T); /對(duì)*T作右旋平衡處理void RightBalance(BSTree

8、 &T)BSTree ld,rc;rc=T-RChild; /rc指向*T的左子樹(shù)根結(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=EH;R_Rotate(T-RChild);L_Rotate(T);break;int Insert_AVL(BSTree &T,ElemT

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

10、edata) /應(yīng)繼續(xù)在T的左子樹(shù)中進(jìn)行搜索 if(!Insert_AVL(T-LChild,e,taller) /未插入 return 0;if(taller) /已插入到T的左子樹(shù)中且左子樹(shù)“長(zhǎng)高”switch(T-bf) /檢查T(mén)的平衡度case LH: LeftBalance(T);taller=false;break;case EH: T-bf=LH;taller=true;break;case RH: T-bf=EH;taller=false;break;else /應(yīng)繼續(xù)在T的右子樹(shù)中進(jìn)行搜索if(!Insert_AVL(T-RChild,e,taller) /未插入return

11、 0;if(taller) /已插入到T右子樹(shù)且右子樹(shù)長(zhǎng)高switch(T-bf) /檢查T(mén)的平衡度case LH:T-bf=EH;taller=false;break;case EH:T-bf=RH;taller=true;break;case RH: /原本右子樹(shù)比左子樹(shù)高，需要作右平衡處理RightBalance(T); taller=false;break; return 1;void InOrderTraverse(BSTree &T)if(T) InOrderTraverse(T-LChild);printf(%dt%d,T-data,T-bf);printf(n);InOrder

12、Traverse(T-RChild);void PreOrderTrave(BSTree &T,BSTree &HT,ElemType e)bool flag;if(T)if(T-data!=e)Insert_AVL(HT,T-data,flag);PreOrderTrave(T-LChild,HT,e);PreOrderTrave(T-RChild,HT,e);void main()int i;bool flag;ElemType e;BSTree HT;HT=NULL;printf(請(qǐng)輸入數(shù)值（0為空樹(shù)）：);scanf(%d,&e);for(i=1;e!=0;i+)Insert_AVL(HT,e,flag);printf(請(qǐng)輸入數(shù)值（0為空樹(shù)）：);scanf(%d,&e);printf(n= 中序遍歷平衡二叉樹(shù) =