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