前言：本文不適合 給一組數(shù)據(jù)15分鐘就能實(shí)現(xiàn)AVL的插入和刪除操作的大牛(也請(qǐng)大牛不要打擊小菜)。
本文適合，對(duì)avl還不了解，還沒(méi)有親自實(shí)現(xiàn)avl的插入和刪除操作的同學(xué)。
ps，你在嘲笑樓主的題目時(shí)，你已證明了自己正在嘲笑自己的智商。我們要善于征服陌生的事物。你如果有半個(gè)小時(shí)時(shí)間就心無(wú)雜念的開(kāi)始吧，建議那些讀10分鐘文章就心燥還是關(guān)閉瀏覽器吧。
文章結(jié)構(gòu)：
什么是二叉排序樹(bst)二叉排序樹(Binary Sort Tree)又稱二叉查找樹。 它或者是一棵空樹;或者是具有下列性質(zhì)的二叉樹： (1)若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值; (2)若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值; (3)左、右子樹也分別為二叉排序樹;
好了二叉排序樹定義很好理解(如果還不理解,為了不浪費(fèi)時(shí)間，先暫停一下，去google or baidu 下，理解了再繼續(xù))，再此就不舉別的例子了，下面我實(shí)現(xiàn)下BST的一些基本操作算法。BST的基本操作
typedef struct _BitNode{ int data; struct _BitNode *lchild,*rchild;}BitNode,*BiTree;
1.1 ,BST的搜索:為什么先實(shí)現(xiàn)搜索呢?一般BST里面沒(méi)有重復(fù)的元素，你增添或者刪除元素，都必須要先查找一下，看有沒(méi)有呀，所以BST搜索要先實(shí)現(xiàn)，這個(gè)搜索是很簡(jiǎn)單的，慢慢看我講解吧,我們先看這張圖
假如你想找到數(shù)值為3的節(jié)點(diǎn)并給你這個(gè)樹的根節(jié)點(diǎn)，且規(guī)定你只能看到這個(gè)根節(jié)點(diǎn)左右孩子(其他你們權(quán)限看到，也看不到)。那不就是很容易啦，先用3和根節(jié)點(diǎn)(此為6)比，顯然比6小。那我就去找他的左孩子比，注意，此時(shí)4就是6的左子樹的根了，那我們就和4這個(gè)新的樹根比吧，顯然又比4小。那我們就繼續(xù)找這個(gè)新根的左孩子比，而此時(shí)3就是4的左子樹的根了，那我們就和這個(gè)根比，哇塞，我們順藤摸瓜，終于找到了哦!!，那我們就提煉一下這個(gè)過(guò)程吧，注意哦，我們每次都是和樹根相比較的哦!規(guī)則：1.先和這棵樹的根比2.如果比這個(gè)樹根小就和這個(gè)樹根的左子樹的根比，否則就和這個(gè)樹根的右子樹比。3.重復(fù)2過(guò)程，直到根為空為止。 根據(jù)3個(gè)步驟很容易實(shí)現(xiàn)遞歸代碼。//搜索元素，參數(shù)依次為0: 根節(jié)點(diǎn),1: 查找的元素,2: 找到目標(biāo)元素的前一個(gè)節(jié)點(diǎn)指針，初始值為NULL
// 3:如果返回真把目標(biāo)到元素的指針指向n，返回假，就把pre復(fù)制給n)(參數(shù)如果不明白，先不要細(xì)究，往下看吧)
bool SearchBST(BiTree T,int key,BiTree pre,BiTree&n);
bool SearchBST(BiTree T,int key,BiTree pre,BiTree&n) { if(!T) { n=pre; //如果此數(shù)為空樹，那我們就把前一個(gè)元素指針pre(此時(shí)為NULL)復(fù)制給n，注意樹為空時(shí)，n才為NULL。 return false; //返回假?zèng)]有找到 } else if(key==T->data) { n=T; //找到了就把目標(biāo)元素指針給n return true; } if(keydata) SearchBST(T->lchild,key,T,n) ;//去找他的左子樹根比 else { SearchBST(T->rchild,key,T,n);//去找他的右子樹根比。 } }
1.2 BST的增添元素算法實(shí)現(xiàn)有了搜索這個(gè)功能，那我們的增添元素的功能就很容易實(shí)現(xiàn)了，算法描述：1.先搜所以下所增添的key，在不在此樹里面。2.如果沒(méi)有找到，則申請(qǐng)空間，把key加入里面返回true，否則返回false。
bool InsetBST(BiTree &T,int k) { BitNode* p; if(!SearchBST(T,k,NULL,p)) { BitNode * temp=new BitNode; temp->data=k; temp->lchild=temp->rchild=NULL; if(!p) //只有樹為空時(shí)，此時(shí)的p才為NULL?？吹竭@里應(yīng)該明白SearchBST(T,k,pre,p)這些參數(shù)的意義了吧 { T=temp; } else { if(kdata) //如果不為空樹，加入的key值就和p相比較，小于就是他的左孩子，否子為右孩子 p->lchild=temp; else { p->rchild=temp; } } return 0; } else { return false; } }
1.3BST刪除元素的算法實(shí)現(xiàn)
既然看到這里了，證明你的好奇心很強(qiáng)，這一節(jié)看完，我們就離成功不遠(yuǎn)了，那我們繼續(xù)吧!
刪除總共有3種情況，1只有左子樹;2，只有右子樹;3，左右子樹都有。 先看第一種
如上圖所示 我們要?jiǎng)h除4這個(gè)節(jié)點(diǎn)，我們就把他雙親節(jié)點(diǎn)的左孩子指向4的左子樹。簡(jiǎn)單吧!。那我么看第二種吧
如上圖所示我們所要?jiǎng)h除的7節(jié)點(diǎn)只有右子樹，想必一定想到了，那我們就把他雙親節(jié)點(diǎn)的右孩子指向7節(jié)點(diǎn)的右孩子，那不就ok啦，太棒了!!。現(xiàn)在看第三種情況吧。
大家看出這三幅圖的變化了嗎?我們所要?jiǎng)h除節(jié)點(diǎn)4，為了要保持樹的順序我們就要找比4大的且要離4最近的，那就是他的后繼，當(dāng)然你找前繼也是可以的。此圖是找他的后繼。我們找到后就用4的后繼替換4，最后刪除后繼這個(gè)節(jié)點(diǎn)。ok，大家看完并理解了這3種情況，那代碼實(shí)現(xiàn)就很easy啦。
bool DeleElement(BiTree&T,int key) { if(!T) { return 0; //樹是空樹的話就返回假 } if(T->data==key) { BitNode*s,*p; if(T->rchild==NULL) //只有右子樹，情況2 { s=T; T=T->lchild; free(s); } else if(T->lchild==NULL) { s=T; //只有左子樹，情況1 T=T->rchild; free(s); } else { //情況3，左右子樹都有 p=T; s=T->rchild; while (s->lchild) { p=s; //找到所要?jiǎng)h除節(jié)點(diǎn)的后繼，那就是他的右孩子的 s=s->lchild; } T->data=s->data; //用刪除節(jié)點(diǎn)的后繼替換所刪除的節(jié)點(diǎn) if(p!=T) { p->lchild=NULL; //所刪除的節(jié)點(diǎn)的右孩子不是葉結(jié)點(diǎn) } else p->rchild=NULL; //所刪除的節(jié)點(diǎn)的右孩子是葉節(jié)點(diǎn) free(s); } return 1; } else if(keydata) DeleElement(T->lchild,key); //去和他的左子樹根去比較 else DeleElement(T->rchild,key); //去和他的右子樹根去比較 }
//中序遍歷并輸出元素 void InorderReverse(BiTree T) { if(T) { InorderReverse(T->lchild); cout<data<rchild); p="" }
終于搞完啦，咱也立馬上機(jī)去測(cè)試吧，如果理解了，就自己測(cè)試吧，看能不能自己寫出來(lái)哦!下面是我自己的測(cè)試
int main(){ BiTree tree=NULL; int a[]={60,86,50,40,35,74,51,100,37,90}; for(int i=0;i<10;i++) InsetBST(tree,a[i]); InorderReverse(tree); cout<<" "<<endl<<endl; p="" 0;}
到這為止二叉排序樹已經(jīng)搞定了，如果你自己也實(shí)現(xiàn)了上述功能，那證明你有很強(qiáng)的好奇心并且很有天賦(因?yàn)闃侵鞲懔撕脦滋觳琶靼?，你十幾分就搞定了，那不是最好的證明嗎?ps：樓主是那種很遲鈍但很有毅力)，有了前面的基礎(chǔ)，AVL就是手到擒來(lái)，不要灰心哦，鼓足勁就繼續(xù)征程吧。如果沒(méi)有理解，先暫停會(huì)，避免浪費(fèi)不必要的時(shí)間，就不要往下看了，建議反復(fù)認(rèn)真看幾遍，如果還不理解，可能這篇文章不適合你，建議參考其它文章。
什么是AVL定義：
平衡二叉樹定義(AVL)：它或者是一顆空樹，或者具有以下性質(zhì)的二叉樹：它的左子樹和右子樹的深度之差(平衡因子)的絕對(duì)值不超過(guò)1，且它的左子樹和右子樹都是一顆平衡二叉樹。
平衡因子(bf)：結(jié)點(diǎn)的左子樹的深度減去右子樹的深度，那么顯然-1<=bf<=1,這里我們定義:
#define EH 0,#define LH 1,#define RH -1.依次為等高，左高，右高。
typedef struct _BitNode
{
int data;
int bf;//平衡因子
struct _BitNode *lchild,*rchild;
}BitNode,*BiTree;
我們都知道，平衡二叉樹是在二叉排序樹(BST)上引入的(這一點(diǎn)很重要哦，下圖為例)，就是為了解決二叉排序樹的不平衡性導(dǎo)致時(shí)間復(fù)雜度大大下降，那么AVL就保持住了(BST)的最好時(shí)間復(fù)雜度O(logn)，所以每次的插入和刪除都要確保二叉樹的平衡，那么怎么保持平衡呢?如果還不理解看看下面的圖吧。
看看AVL的魅力吧。有它就有它存在的價(jià)值，看下圖便知。
圖一和圖二都是BST，但圖二不是AVL，圖一是AVL Tree，如果我們要找到10，圖一比較次數(shù)為3，而圖二比較次數(shù)為7次，很顯然，在規(guī)模比較大的話AVL優(yōu)勢(shì)就很突出了。既然AVL這么強(qiáng)大，牛叉。那我們就把它拿下吧。2.1 AVL增添元素 這里搜索和BST搜索一樣，我就不浪費(fèi)時(shí)間介紹了，我們先實(shí)現(xiàn)增加元素的，實(shí)現(xiàn)然后刪除元素的?？墒敲看蔚牟迦牒蛣h除都要確保二叉樹的平衡，那么怎么保持平衡呢?我們就引入平衡因子。注意這里再看下平衡因子的定義我先演示下給一組數(shù)據(jù)，怎么組成一棵AVl Tree。。int a[]={4,3,2,7,9,11,10};1， 插入4，如圖：
，平衡因子為0.2， 插入3，如圖：
，4的平衡因子因?yàn)?的左子樹增長(zhǎng)了，1-0=1，3， 插入2，如圖
，顯然4的平衡因子大于1了，為了保持平衡那我們就這樣做：讓4節(jié)點(diǎn)的左孩子指向3的右子樹(此時(shí)為NULL)，讓3的右孩子指向4，讓樹根指向3，如圖
，這種操作我們規(guī)定為右旋操作，此圖是以4為根進(jìn)行旋轉(zhuǎn)。 代碼如下
void R_Rotate(BiTree&T){ BiTree p; // p=T->lchild; //假如此時(shí)T指向4，則p指向3; T->lchild=p->rchild; //把3的右子樹掛接到4的左子樹上(此例子3右子樹為空) p->rchild=T; //讓3的右孩子指向4. T=p; //根指向節(jié)點(diǎn)3}
4，插入7，如圖：
5，插入9，如圖：
顯然節(jié)點(diǎn)4不平衡了。那我們就把4的右孩子7的左子樹(此時(shí)為NULL)，讓7的左孩子指向4，讓3的右孩子指向7，如圖：
，我們規(guī)定此操作為左旋操作，此圖是以4為根進(jìn)行旋轉(zhuǎn)，代碼如下：
void L_Rotate(BiTree&T){ BiTree p; p=T->rchild; //假如此時(shí)T指向4，則p指向7. T->rchild=p->lchild; //讓7的左子樹掛接到4的右子樹上 p->lchild=T; //讓7的左孩子指向4 T=p; //樹根指向7}
6.我們插入11，如圖：
顯然3節(jié)點(diǎn)，不平衡了，大家都應(yīng)該知道以3為根進(jìn)行左旋。讓3的右孩子指向7的左子樹(此時(shí)為4)。7的左孩子指向3，根指向7，如下圖所示：
7.我們插入10，如圖：
顯然節(jié)點(diǎn)9不平衡，且是右邊高，那我們左旋吧，左旋后的效果是上圖右圖所示。顯然這是不對(duì)的，10比11小，但在11的右孩子上。(根本原因是9和11的平衡因子符號(hào)不同)那我們?cè)谠趺崔k呢,看下圖吧：
成功離我們不遠(yuǎn)了，我們很容易的把這組數(shù)據(jù)拼出了AVl 樹，是不是很有成就感呀。好啦，我們總結(jié)下插入元素的有哪些規(guī)律吧 1，如上所述的第3步，當(dāng)插入元素后導(dǎo)致左邊高，右邊低，并且為4和3的平衡因子符號(hào)相同，則右旋。?
2, 如上所訴的第5步，當(dāng)插入節(jié)點(diǎn)9后，導(dǎo)致以4為根的樹右邊高，左邊低，4和7的平衡因子符號(hào)相同，則左旋 3，如上所述的第7步，當(dāng)插入節(jié)點(diǎn)10后，導(dǎo)致以9為根的樹右邊高，左邊低，由于9和11的平衡因子符號(hào)不同(也就是根和他的右孩子的平衡因子符號(hào)不同)不能進(jìn)行左旋，正確操作：需要先右旋在左旋，要讓根和根的右孩子平衡因子符號(hào)相同。 4，第4種旋轉(zhuǎn)和3相反，當(dāng)左邊高于右邊的話，且根和他的左孩子，平衡因子符號(hào)不同，需要先左旋再右旋恩，就是這么簡(jiǎn)單。在實(shí)現(xiàn)插入函數(shù)之前，我們先封裝2個(gè)函數(shù)。RightBalance():當(dāng)右高時(shí)需要右平衡時(shí)調(diào)用;
LeftBalance()功能:當(dāng)左高時(shí)需要左平衡時(shí)調(diào)用;右平衡函數(shù)代碼:
void RightBalance(BiTree&T){ BiTree R,rl; //調(diào)用此函數(shù)時(shí)，以T為根的樹，右邊高于左邊，則T->bf=RH。 R=T->rchild; //R是T的右孩子 switch (R->bf) { case RH: //如果 T的右孩子和T他們的平衡因子符號(hào)相同時(shí)，則直接左旋，這是總結(jié)中的第2項(xiàng) T->bf=R->bf=EH; L_Rotate(T); break;
case EH: T->bf=RH; R->bf=LH; L_Rotate(T); break; case LH: //如果T的右孩子和T他們的平衡因子符合不同時(shí)，需要先以T的右孩子為根進(jìn)行右旋，再以T為根左旋。 //rl為T的右孩子的左孩子 rl=R->lchild; //2次旋轉(zhuǎn)后，T的右孩子的左孩子為新的根 。注意：rl的右子樹掛接到R的左子樹上，rl的左子樹掛接到T的右子樹上 switch (rl->bf) //這個(gè)switch 是操作T和T的右孩子進(jìn)行旋轉(zhuǎn)后的平衡因子。 { case EH: T->bf=R->bf=EH; //這些平衡因子操作，大家可以自己畫圖操作理解 下面的注解 break; ////2次旋轉(zhuǎn)后，T的右孩子的左孩子為新的根 。 //并且rl的右子樹掛接到R的左子樹上，rl的左子樹掛接到T的右子樹上，rl為新根 case RH: R->bf=EH; T->bf=LH; break; case LH: R->bf=RH; T->bf=EH; break; default: break; } rl->bf=EH; R_Rotate(T->rchild); //先左旋，以T->rchild為根左旋。 L_Rotate(T); //右旋，以T為根, 左旋后 T是和rl想等，rl是新根 break; }}void LeftBalance(BiTree&T){ BiTree L,lr; L=T->lchild; switch (L->bf) {
case EH: L->bf=RH; T->bf=LH; R_Rotate(T); break; case LH: L->bf=T->bf=EH; R_Rotate(T); break; case RH: lr=L->rchild; switch (lr->bf) { case EH: L->bf=L->bf=EH; case RH: T->bf=EH; L->bf=LH; break; case LH: L->bf=EH; T->bf=RH; break; default: break; } lr->bf=EH; L_Rotate(T->lchild); R_Rotate(T); break; default: break; }}
//哈哈，兩元猛將我們已經(jīng)找到了，但是你看到這有點(diǎn)累了，但不要灰心，成功就在我們腳下，現(xiàn)在放棄，豈不是很可惜啦。那我們就實(shí)現(xiàn)插入元素的功能
bool InsertAVLtree(BiTree&T,int key,bool&taller){ if(!T) //此樹為空 { T=new BitNode; //直接作為整棵樹的根。 T->bf=EH; T->lchild=T->rchild=NULL; T->data=key; taller=true; return true; } else { if(key==T->data) //已有元素，不用插入了，返回false; { taller=false; return false; } if(keydata) //所插元素小于此根的值，就找他的左孩子去比 { if(!InsertAVLtree(T->lchild,key,taller)) //所插元素小于此根的值，就找他的左孩子去比 return false; if(taller) //taller為根，則樹長(zhǎng)高了，并且插入到了此根的左子樹上。 { switch (T->bf) //此根的平衡因子 { case EH: //原先是左右平衡，等高 T->bf=LH; //由于插入到左子樹上，導(dǎo)致左高=》》LH taller=true; //繼續(xù)往上遞歸 break; case LH: LeftBalance(T); //原先LH，由于插入到了左邊，這T這個(gè)樹，不平衡需要左平衡 taller=false; //以平衡，設(shè)taller為false，往上遞歸就不用進(jìn)入此語(yǔ)句了， break; case RH: T->bf=EH; //原先RH，由于插入到左邊，導(dǎo)致此T平衡 taller=false; break; default: break; } } } else { if(!InsertAVLtree(T->rchild,key,taller)) return false; if(taller) { switch (T->bf) { case EH: T->bf=RH; taller=true; break; case LH: T->bf=EH; taller=false; break; case RH: RightBalance(T); taller=false; break; default: break; } } } }
//中序遍歷輸出void InOrderReverse(BiTree&T){ if(T) { InOrderReverse(T->lchild); cout<data<rchild); p="" }}
看到這了，自己出一組數(shù)據(jù)或按照我剛才用一組數(shù)據(jù)拼成avl的過(guò)程，看代碼走一遍，你會(huì)有不一樣的收貨的哦(這其實(shí)非常重要)，并插入了成功了，你已經(jīng)成功99%了，沒(méi)有想到自己這么厲害吧，我們接下來(lái)完成它的刪除操作，我們就完美了。如果你有追求完美的目標(biāo)，那就跟我走吧
2.2AVL的刪除操作
下面我會(huì)貼出代碼，根據(jù)代碼把上圖的元素刪除掉吧，你會(huì)成功的
為了更好的理解，建議先把插入代碼先實(shí)現(xiàn)。
刪除代碼和BST的刪除相似，AVL刪除元素后還要照顧好平衡。
bool DeletElement(BiTree&T,int key,bool&lower)//參數(shù)(0)樹根，(1)刪除的元素，(3)此樹是否降低標(biāo)志位
{
bool L,R;//刪除的是左子樹還是右子樹，作為標(biāo)志。
L=R=false;
if(T==NULL) // 判斷樹根是否為空
return false;
if(key==T->data)//找到了所要?jiǎng)h除的節(jié)點(diǎn)
{
BitNode* p,*s;
p=T->rchild;
s=p;
lower=true; //找到了必定刪除，lower為真
if(T->rchild==NULL) // 如果所要?jiǎng)h除的節(jié)點(diǎn)的右孩子為空
{
p=T;
T=T->lchild; //直接刪除比如刪除上圖的 4,9,10，
free(p);
lower=true;
return true;
}
else
{
while (s)//如果所要?jiǎng)h除的T節(jié)點(diǎn)右子樹不為空，就找T的后繼，也就是T的右孩子左子樹的最左葉節(jié)點(diǎn)
{
p=s;
s=s->lchild;
}
T->data=p->data;//替換T
DeletElement(T->rchild,p->data,lower);//刪除掉T的后繼
R=true;
}
}
else if(key
好吧，請(qǐng)?jiān)徫因_了你，你看到這時(shí)，已不止半小時(shí)了。但為你使你相信你是有能力看完的，我不得不做這個(gè)下賤的謊言。 我不期望你能全部都能按照我的思路寫下去，因?yàn)槲覍懙倪€不夠好，哪怕你有一點(diǎn)收獲，樓主也是值得的。
下載文檔
