平衡二叉樹的講解.doc

一、平衡二叉樹的概念 平衡二叉樹(Balanced binary tree)是由阿德爾森-維爾斯和蘭迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又稱為AVL樹。定義：平衡二叉樹或為空樹,或為如下性質(zhì)的二叉排序樹: （1）左右子樹深度之差的絕對值不超過1; （2）左右子樹仍然為平衡二叉樹. 平衡因子BF=左子樹深度右子樹深度.平衡二叉樹每個結(jié)點的平衡因子只能是1，0，-1。若其絕對值超過1，則該二叉排序樹就是不平衡的。如圖所示為平衡樹和非平衡樹示意圖：二、平衡二叉樹算法思想若向平衡二叉樹中插入一個新結(jié)點后破壞了平衡二叉樹的平衡性。首先要找出插入新結(jié)點后失去平衡的最小子樹根結(jié)點的指針。然后再調(diào)整這個子樹中有關(guān)結(jié)點之間的鏈接關(guān)系，使之成為新的平衡子樹。當(dāng)失去平衡的最小子樹被調(diào)整為平衡子樹后，原有其他所有不平衡子樹無需調(diào)整，整個二叉排序樹就又成為一棵平衡二叉樹。 失去平衡的最小子樹是指以離插入結(jié)點最近，且平衡因子絕對值大于1的結(jié)點作為根的子樹。假設(shè)用A表示失去平衡的最小子樹的根結(jié)點，則調(diào)整該子樹的操作可歸納為下列四種情況。1）LL型平衡旋轉(zhuǎn)法由于在A的左孩子B的左子樹上插入結(jié)點F，使A的平衡因子由1增至2而失去平衡。故需進(jìn)行一次順時針旋轉(zhuǎn)操作。 即將A的左孩子B向右上旋轉(zhuǎn)代替A作為根結(jié)點，A向右下旋轉(zhuǎn)成為B的右子樹的根結(jié)點。而原來B的右子樹則變成A的左子樹。（2）RR型平衡旋轉(zhuǎn)法 由于在A的右孩子C 的右子樹上插入結(jié)點F，使A的平衡因子由-1減至-2而失去平衡。故需進(jìn)行一次逆時針旋轉(zhuǎn)操作。即將A的右孩子C向左上旋轉(zhuǎn)代替A作為根結(jié)點，A向左下旋轉(zhuǎn)成為C的左子樹的根結(jié)點。而原來C的左子樹則變成A的右子樹。（3）LR型平衡旋轉(zhuǎn)法 由于在A的左孩子B的右子數(shù)上插入結(jié)點F，使A的平衡因子由1增至2而失去平衡。故需進(jìn)行兩次旋轉(zhuǎn)操作（先逆時針，后順時針）。即先將A結(jié)點的左孩子B的右子樹的根結(jié)點D向左上旋轉(zhuǎn)提升到B結(jié)點的位置，然后再把該D結(jié)點向右上旋轉(zhuǎn)提升到A結(jié)點的位置。即先使之成為LL型，再按LL型處理。 如圖中所示，即先將圓圈部分先調(diào)整為平衡樹，然后將其以根結(jié)點接到A的左子樹上，此時成為LL型，再按LL型處理成平衡型。（4）RL型平衡旋轉(zhuǎn)法 由于在A的右孩子C的左子樹上插入結(jié)點F，使A的平衡因子由-1減至-2而失去平衡。故需進(jìn)行兩次旋轉(zhuǎn)操作（先順時針，后逆時針），即先將A結(jié)點的右孩子C的左子樹的根結(jié)點D向右上旋轉(zhuǎn)提升到C結(jié)點的位置，然后再把該D結(jié)點向左上旋轉(zhuǎn)提升到A結(jié)點的位置。即先使之成為RR型，再按RR型處理。如圖中所示，即先將圓圈部分先調(diào)整為平衡樹，然后將其以根結(jié)點接到A的左子樹上，此時成為RR型，再按RR型處理成平衡型。平衡化靠的是旋轉(zhuǎn)。參與旋轉(zhuǎn)的是3個節(jié)點（其中一個可能是外部節(jié)點NULL），旋轉(zhuǎn)就是把這3個節(jié)點轉(zhuǎn)個位置。注意的是，左旋的時候p-right一定不為空，右旋的時候p-left一定不為空，這是顯而易見的。如果從空樹開始建立，并時刻保持平衡，那么不平衡只會發(fā)生在插入刪除操作上，而不平衡的標(biāo)志就是出現(xiàn)bf = 2或者 bf = -2的節(jié)點。 三、二叉排序數(shù)的操作及C語言描述插入刪除是互為鏡像的操作。我們可以采用前面對二叉排序樹的刪除操作來進(jìn)行。然后，在刪除掉結(jié)點后，再對平衡樹進(jìn)行平衡化處理。刪除操作需要的平衡化可能比插入時次數(shù)多，就是因為平衡化不會增加子樹的高度，但是可能會減少子樹的高度。有可能使樹增高的插入操作中，一次平衡化能抵消掉增高；有可能使樹減低的刪除操作中，平衡化可能會帶來祖先節(jié)點的不平衡。四、二叉排序數(shù)的C語言實現(xiàn)#include stdio.h#include stdlib.h#include string.h#define LH +1 /左高#define EH 0 /等高 #define RH -1 /右高#define TRUE 1#define FALSE 1#define EQ(a,b) (a)=(b)#define LT(a,b) (a) (b)#define LQ(a,b) (a) (b)typedef int KeyType;typedef int info;typedef int Boolean;typedef struct ElemTypeKeyType key;/info otherinfo;typedef struct BSTNode ElemType data; int bf; BSTNode *lchild,*rchild; / 左右孩子指針 BSTNode,*BSTree; void R_Rotate(BSTree &p) /右旋 BSTree lc; lc=p-lchild; p-lchild=lc-rchild; lc-rchild=p; p=lc; /p指向新的根結(jié)點 /R_Rotate void L_Rotate(BSTree &p) /左旋 BSTree rc; rc=p-rchild; p-rchild=rc-lchild; rc-lchild=p; p=rc; /p指向新的根結(jié)點 /L_Rotate void LeftBalance(BSTree &T)/作平衡旋轉(zhuǎn)處理BSTree lc,rd;lc=T-lchild;switch(lc-bf) case LH: T-bf=lc-bf=EH; R_Rotate(T); break; case RH: rd=lc-rchild; switch(rd-bf) case LH:T-bf=RH;lc-bf=EH;break; case EH:T-bf=lc-bf=EH; break; case RH:T-bf=EH;lc-bf=LH;break; /switch rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch/LeftBalancevoid RightBalance(BSTree &T)/作平衡旋轉(zhuǎn)處理BSTree rc,ld;rc=T-rchild;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=LH;rc-bf=EH;break; case EH:T-bf=rc-bf=EH; break; case RH:T-bf=EH;rc-bf=RH;break; /switch ld-bf=EH; R_Rotate(T-rchild); L_Rotate(T); /switch/RightBalanceint InsertAVL(BSTree &T,ElemType e,int &taller) / 若在平衡的二叉排序樹T中不存在和e有相同關(guān)鍵字的結(jié)點，則插入一個 / 數(shù)據(jù)元素為e的新結(jié)點，并返回1，否則返回0。若因插入而使二叉排序樹 / 失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變量taller反映T長高與否 if(!T) / 插入新結(jié)點，樹“長高”，置taller為TRUE T=(BSTree)malloc(sizeof(BSTNode); T-data=e; T-lchild=T-rchild=NULL; T-bf=EH; taller=TRUE; else if EQ(e.key,T-data.key) / 樹中已存在和e有相同關(guān)鍵字的結(jié)點則不再插入 taller=FALSE; return FALSE; if LT(e.key,T-data.key) / 應(yīng)繼續(xù)在*T的左子樹中進(jìn)行搜索 if(!InsertAVL(T-lchild,e,taller) / 未插入 return FALSE; if(taller) / 已插入到*T的左子樹中且左子樹“長高” switch(T-bf) / 檢查*T的平衡度 case LH: / 原本左子樹比右子樹高，需要作左平衡處理 LeftBalance(T); taller=FALSE; break; case EH: / 原本左、右子樹等高，現(xiàn)因左子樹增高而使樹增高 T-bf=LH; taller=TRUE; break; case RH: T-bf=EH; / 原本右子樹比左子樹高，現(xiàn)左、右子樹等高 taller=FALSE; else / 應(yīng)繼續(xù)在*T的右子樹中進(jìn)行搜索 if(!InsertAVL(T-rchild,e,taller) / 未插入 return FALSE; if(taller) / 已插入到T的右子樹且右子樹“長高” switch(T-bf) / 檢查T的平衡度 case LH: T-bf=EH; / 原本左子樹比右子樹高，現(xiàn)左、右子樹等高 taller=FALSE; break; case EH: / 原本左、右子樹等高，現(xiàn)因右子樹增高而使樹增高 T-bf=RH; taller=TRUE; break; case RH: / 原本右子樹比左子樹高，需要作右平衡處理 RightBalance(T); taller=FALSE; return TRUE; BSTree SearchBST(BSTree T,KeyType key) / 在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素， / 若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點的指針,否則返回空指針。 if(!T)|EQ(key,T-data.key) return T; / 查找結(jié)束 else if LT(key,T-data.key) / 在左子樹中繼續(xù)查找 return SearchBST(T-lchild,key); else return SearchBST(T-rchild,key); / 在右子樹中繼續(xù)查找 /SearchBSTvoid DestroyDSTable(BSTree &DT) / 初始條件: 動態(tài)查找表DT存在。操作結(jié)果: 銷毀動態(tài)查找表DT if(DT) / 非空樹 if(DT-lchild) / 有左孩子 DestroyDSTable(DT-lchild); / 銷毀左孩子子樹 if(DT-rchild) / 有右孩子 DestroyDSTable(DT-rchild); / 銷毀右孩子子樹 free(DT); / 釋放根結(jié)點 DT=NULL; / 空指針賦0 /if /DestroyDSTableint InitDSTable(BSTree &DT) / 操作結(jié)果: 構(gòu)造一個空的動態(tài)查找表DT DT=NULL; return 1; /InitDSTablevoid Visit(BSTree DT)/printf(DT-data.key:-%dnT-bf:%dn,DT-data.key,DT-bf);printf(DT-data.key:-%dn,DT-data.key);/Visit void TraverseDSTable(BSTree &DT,void(*Visit)(BSTree) / 初始條件: 動態(tài)查找表DT存在，Visit是對結(jié)點操作的應(yīng)用函數(shù) / 操作結(jié)果: 按關(guān)鍵字的順序?qū)T的每個結(jié)點調(diào)用函數(shù)Visit()一次且至多一次 if(DT) TraverseDSTable(DT-lchild,Visit); / 先中序遍歷左子樹 Visit(DT); / 再訪問根結(jié)點 TraverseDSTable(DT-rchild,Visit); / 最后中序遍歷右子樹 int InsertAVLD(BSTree &T)ElemType e;Boolean taller;printf(input the data until -1n);scanf(%d,&e.key);while(e.key!=-1) InsertAVL(T,e,taller); printf(input the data until -1n); scanf(%d,&e.key); return 1;/InsertAVLDvoid LeftBalanceD(BSTree T,int &shorter)BSTree lc=T-lchild,rd;switch(lc-bf) case LH: T-bf=lc-bf=EH; R_Rotate(T);break; case EH: T-bf=LH; lc-bf=RH; R_Rotate(T);break; case RH: rd=lc-rchild; switch(rd-bf) case RH: T-bf=EH;lc-bf=LH;shorter=0;break; case EH: T-bf=EH;lc-bf=EH;shorter=1;break; case LH: T-bf=RH;lc-bf=EH;shorter=1;break; /switch rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch/LeftBalanceDvoid RightBalanceD(BSTree T,int &shorter)BSTree rc=T-rchild,ld;switch(rc-bf) case RH: T-bf=rc-bf=EH; R_Rotate(T);break; case EH: T-bf=RH; rc-bf=RH; L_Rotate(T);shorter=0;break; case LH: ld=rc-lchild; switch(ld-bf) case RH: T-bf=EH;rc-bf=RH;break; case EH: T-bf=EH;rc-bf=EH;break; case LH: T-bf=LH;rc-bf=EH;break; /switch ld-bf=EH; R_Rotate(T-rchild); L_Rotate(T); /switch/RightBalanceDint SearchBSTD(BSTree &T)ElemType e;printf(nplease input the number you want to search:n);scanf(%d,&e.key);if(SearchBST(T,e.key)!=NULL) printf(%d,e.key);else printf(failed!);return 1;/SearchBSTDint Delete(BSTree &T,KeyType key,int &shorter)int success=0;/標(biāo)志成功刪除與否if(T) if(EQ(key,T-data.key) /相等，即當(dāng)前結(jié)點就是要刪除的結(jié)點 if(T-lchild!=NULL&T-rchild!=NULL) /要刪除結(jié)點的左右子樹都不空 BSTree q,r; /接下來，找到要刪除數(shù)據(jù)的前驅(qū)結(jié)點，并且將數(shù)據(jù)與直接前驅(qū)/交換。這樣我們將其前驅(qū)刪除掉后，再調(diào)整平衡樹就好了。 q=T-lchild; r=q;/用r來指向其前驅(qū)接點。 while(q) r=q; q=q-rchild; /while(q) KeyType temp=T-data.key; T-data.key=r-data.key; r-data.key=temp; /接下來，在左子樹上刪除其前驅(qū)接點 success=Delete(T-lchild,key,shorter); if(shorter) /由于刪除操作導(dǎo)致了樹變小了 switch(T-bf) case LH:T-bf=EH;break; case EH:T-bf=RH;break; case RH:RightBalanceD(T,shorter);break; /switch /if /if-要刪除結(jié)點左右子樹都不空 else /要刪除接點有一個子樹不為空 BSTree p=T; T=(T-lchild!=NULL)?T-lchild:T-rchild; delete p; success=1;/刪除成功 shorter=1;/樹變短了。 /else /if= else if(LT(key,T-data.key) /在左子樹上查詢要刪除的結(jié)點 success=Delete(T-lchild,key,shorter); if(shorter) switch(T-bf) case LH: T-bf=EH; shorter=0;break; case EH: T-bf=RH; break; case RH: RightBalanceD(T,shorter); break; /switch /if-shorter /ifdata.key) /在右子樹上查詢要刪除的結(jié)點 success=Delete(T-rchild,key,shorter); if(shorter) switch(T-bf) case LH: LeftBalanceD(T,shorter); break; case EH: T-bf=LH; break; case RH: T-bf=EH; shorter=0;break; /switch /if-shorter /else if /if(T)return success;/Deleteint DeleteD(BSTree &T)ElemType e;int shorter;printf(ninput the data you want to delete:n);scanf(%d,&e.key);Delete(T,e.key,shorter);return 1;/Deleteint main()BSTree T;InitDSTable(T);InsertAVLD(T);TraverseDSTable(T,Visit);SearchBSTD(T);DeleteD(T);TraverseDSTable(T,Visit);DestroyDSTable(T);return 1;五、復(fù)雜度分析在平衡二叉樹上進(jìn)行查找的過程與二叉排序樹的查找算法相同。因此，在查找過程中和關(guān)鍵字進(jìn)行比較的次數(shù)不超過樹的深度。含有n個結(jié)點的平衡樹的最大深度為： 上述討論，都是在等概率情形下的。如果不是，則為了提高效率，需對等查記錄先進(jìn)行排序，然后構(gòu)造次優(yōu)查找樹。但是次優(yōu)查找樹不能在查找過程中生成。二叉排序樹是動態(tài)的，次優(yōu)查找樹是靜態(tài)的。六、語法知識點1、函數(shù)名作為參數(shù)傳遞關(guān)于這一點，前面有過討論。/zhoumhan_0351/blog/static/3995422720093267341920/今天我們再做一個總結(jié)。a)一個函數(shù)在編譯時，也會給它分配一個入口地址。這個入口地址就稱為函數(shù)的指針。可用一個指針變量指向函數(shù)，然后通過該指針變量來調(diào)用此函數(shù)。如int max(int x,int y)int (*p)(); /定義一個函數(shù)指針變量p.p=max;/將max函數(shù)的起始地址賦給指針p.c=(*p)(a,b); /等價于c=max(a,b);注意：對于函數(shù)指針來說，*(p+1)等操作是違法的。b)指向函數(shù)指針變量的定義格式：數(shù)據(jù)類型 （*指針變量名）（）;這里的數(shù)據(jù)類型是函數(shù)返回值的數(shù)據(jù)類型。這個指針變量就是專門用來存放函數(shù)入口地址的。在一個程序中，一個指針變量可以先后指向返回類型不同的函數(shù)。在給函數(shù)指針賦值時，只需給出函數(shù)名而不必給出參數(shù)。再如double (*f)(double)=exp; or f=log10;我們在程序中的函數(shù)TraverseDSTable(BSTree &DT,void(*Visit)(ElemType)便是這樣。其為返回值為空型，只有一個參數(shù)的指指變量，定調(diào)用時：TraverseDSTable(T,Visit);其中，Visit便是函數(shù)名。2、帶參數(shù)的宏定義 一般形式為： #define 宏名（參數(shù)表） 字符串 在程序中，在編譯前，按宏定義命令行中指定的字符串從左到右進(jìn)行置換，并不分配內(nèi)存單元，也沒有返回值的說法。如：#define EQ(a,b) (a)=(b)則凡是程序中出現(xiàn)有EQ(a,b)的地方，則替換成(a)=(b)表達(dá)式。七、弦外之音 關(guān)于二叉平衡樹的插入的刪除的討論，網(wǎng)上一位網(wǎng)友曾有如下論述，原網(wǎng)址為/data/2009/0825/article_3877.htm，在這里貼出來，以作思考。插入和刪除 AVL樹體現(xiàn)了一種平衡的美感，兩種旋轉(zhuǎn)是互為鏡像的，插入刪除是互為鏡像的操作，沒理由會有那么大的差別。實際上，平衡化可以統(tǒng)一的這樣來操作：1、while (current != NULL)修改current的平衡因子。（1）插入節(jié)點時current-bf += (current-data *p)?1:-1;（2）刪除節(jié)點時current-bf -= (current-data *p)?1:-1;（3）current指向插入節(jié)點或者實際刪除節(jié)點的父節(jié)點，這是普通二叉搜索樹的插入和刪除操作帶來的結(jié)果。*p初始值是插入節(jié)點或者實際刪除節(jié)點的data。因為刪除操作可能實際刪除的不是data。2、判斷是否需要平衡化if (current-bf = -2) L_Balance(c_root);else if (current-bf = 2) R_Balance(c_roo