也許二杈樹(shù)是很好用的，在插入和查找的時(shí)候時(shí)間復(fù)雜度一般為O（logN），但如果左右子樹(shù)失去平衡，也可能達(dá)到O（N）。為了防止這種現(xiàn)象發(fā)生，一種解決辦法是是左右子樹(shù)盡量保持平衡，即建立一種平衡有序樹(shù)AVL樹(shù)。?????
????一棵AVL樹(shù)是其每個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度最多相差1的二杈有序樹(shù)。空樹(shù)的高度定義為-1。
????AVL樹(shù)的結(jié)點(diǎn)聲明；
typedef?struct?avlnode
{
????int?height;//比普通二杈有序樹(shù)多了一個(gè)高度信息?
????ElemType?data;
????struct?bnode?*lchild,?*rchild;
}?*AvlTree,?*Position;????
//----------AVL樹(shù)基本操作------------?------------------------------
AvlTree?MakeEmpty(AvlTree?T);
Position?Find(ElemType?x,?AvlTree?T);
Position?FindMin(AvlTree?T);
Position?FindMax(AvlTree?T);
static?int?Height(Position?P);
AvlTree?Insert(ElemType?x,?AvlTree?T);
AvlTree?Delete(ElemType?x,?AvlTree?T);
ElemType?Retrieve(Position?P);
//----------AVL樹(shù)基本操作的算法實(shí)現(xiàn)--------------------
遞歸算法：?
Position?FindMin(AvlTree?T)
{
????if(T==NULL)
????????return?NULL;
????else?if(T->lchild?==?NULL)
????????return?T;
????else
????????return?FindMin(T->lchild);
}
Position?FindMax(AvlTree?T)
{
????if(T==NULL)
????????return?NULL;
????else?if(T->rchild?==?NULL)
????????return?T;
????else
????????return?FindMax(T->rchild);
}
非遞歸算法：
Position?FindMin(AvlTree?T)
{
????if(T!=NULL)
????{
????????while(T->lchild?!=?NULL)
????????????T?=?T->lchild;
????}
????
????return?T;
}
Position?FindMax(AvlTree?T)
{
????if(T!=NULL)
????{
????????while(T->rchild?!=?NULL)
????????????T?=?T->rchild;
????}
????
????return?T;
}
//返回P點(diǎn)的高度?
static?int?Height(Position?P)
{
????if(P==NULL)
????????return?-1;
????else
????????return?P->height;
}
//在對(duì)一棵AVL樹(shù)進(jìn)行插入操作后，可能會(huì)破壞它的平衡條件，因此必須對(duì)新的AVL樹(shù)進(jìn)行調(diào)整，
這里用到了“單旋轉(zhuǎn)”或“雙旋轉(zhuǎn)”的算法，分別適用于：
單左旋轉(zhuǎn)（SingleRotateWithLeft）；對(duì)結(jié)點(diǎn)p的左孩子的左子樹(shù)進(jìn)行一次插入?
單右旋轉(zhuǎn)（SingleRotateWithRight）；對(duì)結(jié)點(diǎn)p的右孩子的右子樹(shù)進(jìn)行一次插入??
雙左旋轉(zhuǎn)（DoubleRotateWithLeft）；對(duì)結(jié)點(diǎn)p的左孩子的右子樹(shù)進(jìn)行一次插入?
雙右旋轉(zhuǎn)（DoubleRotateWithRight）；對(duì)結(jié)點(diǎn)p的右孩子的左子樹(shù)進(jìn)行一次插入??
static?Position?SingleRotateWithLeft(Position?K2)
{
????Position?K1;
????
????K1?=?K2->lchild;??//在K2和K1之間進(jìn)行一次單左旋轉(zhuǎn)?
????K2->lchild?=?K1->rchild;
????K1->rchild?=?K2;
????
????K2->height?=?Max(Height(K2->lchild),?Height(K2->rchild))?+?1;
????K1->height?=?Max(Height(K1->lchild),?Height(K1->rchild))?+?1;
????
????return?K1;
}
static?Position?SingleRotateWithRight(Position?K2)
{
????Position?K1;
????
????K1?=?K2->rchild;????//在K2和K1之間進(jìn)行一次單右旋轉(zhuǎn)?
????K2->rchild?=?K1->lchild;
????K1->lchild?=?K2;
????
????K2->height?=?Max(Height(K2->lchild),?Height(K2->rchild))?+?1;
????K1->height?=?Max(Height(K1->lchild),?Height(K1->rchild))?+?1;
????
????return?K1;
}
static?Position?DoubleRotateWithLeft(Position?K3)
{
????K3->lchild?=?SingleRotateWithRight(K3->lchild);?//在K2和K1之間進(jìn)行一次單右旋轉(zhuǎn)?
????
????return?SingleRotateWithLeft(K3);?//在K3和K2之間進(jìn)行一次單左旋轉(zhuǎn)?
}
static?Position?DoubleRotateWithRight(Position?K3)
{
????K3->rchild?=?SingleRotateWithLeft(K3->rchild);?//在K2和K1之間進(jìn)行一次單左旋轉(zhuǎn)?
????
????return?SingleRotateWithRight(K3);//在K3和K2之間進(jìn)行一次單右旋轉(zhuǎn)?
}
//向AVL樹(shù)插入結(jié)點(diǎn)的操作?
AvlTree?Insert(float?x,?AvlTree?T)
{
????if(T?==?NULL)
????{
????????T?=?(Position)malloc(sizeof(struct?avlnode));
????????if(T?==?NULL)
????????{
????????????puts("wrong");?
????????????exit(1);
????????}
????????T->data?=?x;??
????????T->height?=?0;
????????T->lchild?=?T->rchild?=?NULL;
????}
????else?if(T->data?==?x)//不做任何插入操作?
????????;
????else?if(T->data?>?x)//把s所指結(jié)點(diǎn)插入到左子樹(shù)中
????{
??????????T->lchild?=?Insert(x,?T->lchild);
??????????if(Height(T->lchild)?-?Height(T->rchild)?==?2)?//若平衡被破壞
??????????{
????????????if(x?<?T->lchild->data)?????//若x比T的左孩子小，對(duì)T單左旋轉(zhuǎn)??
????????????????T?=?SingleRotateWithLeft(T);
????????????else?????????????????????????//否則，對(duì)T雙左旋轉(zhuǎn)???
????????????????T?=?DoubleRotateWithLeft(T);
????????}
????}
????else??????//把s所指結(jié)點(diǎn)插入到右子樹(shù)中
????{
??????????T->rchild?=?Insert(x,?T->rchild);
??????????if(Height(T->rchild)?-?Height(T->lchild)?==?2)
??????????{
????????????if(x?>?T->rchild->data)????//若x比T的右孩子大，對(duì)T單右旋轉(zhuǎn)??
????????????????T?=?SingleRotateWithRight(T);
????????????else????????????????????????//否則，對(duì)T雙右旋轉(zhuǎn)???
????????????????T?=?DoubleRotateWithRight(T);
????????}
????}
????T->height?=?Max(Height(T->lchild),?Height(T->rchild))?+?1;
????
????return?T;???
}
int?Max(int?a,?int?b)
{
????if(a?>?b)
????????return?a;
????else
????????return?b;
}
還有一種AVL樹(shù)，它的結(jié)構(gòu)中不包含高度特征，但包含一個(gè)平衡因子bf，用來(lái)判斷結(jié)點(diǎn)的平衡性，若左孩子比右孩子高，則bf==1；否則，bf==-1；若左右相等則bf==0。
????AVL樹(shù)的結(jié)點(diǎn)聲明；
enum??BALANCE{LH?=?1,?EH?=?0,?RH?=?-1};
typedef?struct?avlnode
{
????BALANCE?bf;//比普通二杈有序樹(shù)多了一個(gè)平衡因子信息
????ElemType?data;
????struct?avlnode?*lchild,?*rchild;
}?*AvlTree,?*Position;
//----------AVL樹(shù)基本操作------------?------------------------------
AvlTree?MakeEmpty(AvlTree?T);
Position?Find(ElemType?x,?AvlTree?T);
Position?FindMin(AvlTree?T);
Position?FindMax(AvlTree?T);
AvlTree?Insert(ElemType?x,?AvlTree?T);
AvlTree?Delete(ElemType?x,?AvlTree?T);
ElemType?Retrieve(Position?P);
//----------AVL樹(shù)基本操作的算法實(shí)現(xiàn)--------------------
//在對(duì)一棵AVL樹(shù)進(jìn)行插入操作后，可能會(huì)破壞它的平衡條件，因此必須對(duì)新的AVL樹(shù)進(jìn)行調(diào)整，
這里用到了“單旋轉(zhuǎn)”或“雙旋轉(zhuǎn)”的算法，分別適用于：
單左旋轉(zhuǎn)（SingleRotateWithLeft）；對(duì)結(jié)點(diǎn)p的左孩子的左子樹(shù)進(jìn)行一次插入
單右旋轉(zhuǎn)（SingleRotateWithRight）；對(duì)結(jié)點(diǎn)p的右孩子的右子樹(shù)進(jìn)行一次插入
雙左旋轉(zhuǎn)（DoubleRotateWithLeft）；對(duì)結(jié)點(diǎn)p的左孩子的右子樹(shù)進(jìn)行一次插入
雙右旋轉(zhuǎn)（DoubleRotateWithRight）；對(duì)結(jié)點(diǎn)p的右孩子的左子樹(shù)進(jìn)行一次插入
Position?SingleRotateWithLeft(Position?K2)
{
????Position?K1;
????K1?=?K2->lchild;??//在K2和K1之間進(jìn)行一次單左旋轉(zhuǎn)
????K2->lchild?=?K1->rchild;
????K1->rchild?=?K2;
????return?K1;
}
Position?SingleRotateWithRight(Position?K2)
{
????Position?K1;
????K1?=?K2->rchild;????//在K2和K1之間進(jìn)行一次單右旋轉(zhuǎn)
????K2->rchild?=?K1->lchild;
????K1->lchild?=?K2;
????return?K1;
}
Position?DoubleRotateWithLeft(Position?K3)
{
????K3->lchild?=?SingleRotateWithRight(K3->lchild);?//在K2和K1之間進(jìn)行一次單右旋轉(zhuǎn)
????return?SingleRotateWithLeft(K3);?//在K3和K2之間進(jìn)行一次單左旋轉(zhuǎn)
}
Position?DoubleRotateWithRight(Position?K3)
{
????K3->rchild?=?SingleRotateWithLeft(K3->rchild);?//在K2和K1之間進(jìn)行一次單左旋轉(zhuǎn)
????return?SingleRotateWithRight(K3);//在K3和K2之間進(jìn)行一次單右旋轉(zhuǎn)
}
AvlTree?LeftBalance(AvlTree?T)?//左平衡處理
{
??????AvlTree?lT?=?T->lchild;
??????switch?(lT->bf)?//檢查左樹(shù)的平衡度，并做相應(yīng)處理
??????{
????????????case?LH?:???T?=?SingleRotateWithLeft(T);?//若新結(jié)點(diǎn)插入在T的左孩子的左子樹(shù)上，對(duì)T單左旋轉(zhuǎn)
????????????????????????T->bf?=?lT->bf?=?EH;???//重新設(shè)置平衡度
????????????????????????break;
????????????case?RH?:???AvlTree?rT?=?lT->rchild;//若新結(jié)點(diǎn)插入在T的左孩子的右子樹(shù)上，對(duì)T雙左旋轉(zhuǎn)，并重新設(shè)置平衡度
????????????????????????switch?(rT->bf)
????????????????????????{
??????????????????????????????case?LH?:???T->bf?=?RH;
??????????????????????????????????????????lT->bf?=?EH;
??????????????????????????????????????????break;
??????????????????????????????case?EH?:???T->bf?=?lT->bf?=?EH;?//我感覺(jué)這種情況應(yīng)該不會(huì)出現(xiàn)
??????????????????????????????????????????break;
??????????????????????????????case?RH?:???T->bf?=?EH;
??????????????????????????????????????????lT->bf?=?LH;
??????????????????????????????????????????break
????????????????????????}
????????????????????????rT->bf?=?EH;
????????????????????????T?=?DoubleRotateWithLeft(T);
????????????????????????break;
??????}
??????return?T;
}
AvlTree?RightBalance(AvlTree?T)?//右平衡處理
{
??????AvlTree?rT?=?T->rchild;
??????switch?(rT->bf)?//檢查右樹(shù)的平衡度，并做相應(yīng)處理
??????{
????????????case?LH?:???T?=?SingleRotateWithRight(T);?//若新結(jié)點(diǎn)插入在T的右孩子的右子樹(shù)上，對(duì)T單右旋轉(zhuǎn)
????????????????????????T->bf?=?rT->bf?=?EH;???//重新設(shè)置平衡度
????????????????????????break;
????????????case?RH?:???AvlTree?lT?=?rT->lchild;//若新結(jié)點(diǎn)插入在T的右孩子的左子樹(shù)上，對(duì)T雙右旋轉(zhuǎn)，并重新設(shè)置平衡度
????????????????????????switch?(lT->bf)
????????????????????????{
??????????????????????????????case?LH?:???T->bf?=?EH;
??????????????????????????????????????????rT->bf?=?RH;
??????????????????????????????????????????break;
??????????????????????????????case?EH?:???T->bf?=?rT->bf?=?EH;?//我感覺(jué)這種情況應(yīng)該不會(huì)出現(xiàn)
??????????????????????????????????????????break;
??????????????????????????????case?RH?:???T->bf?=?LH;
??????????????????????????????????????????rT->bf?=?EH;
??????????????????????????????????????????break
????????????????????????}
????????????????????????lT->bf?=?EH;
????????????????????????T?=?DoubleRotateWithRight(T);
????????????????????????break;
??????}
??????return?T;
}
//向AVL樹(shù)插入結(jié)點(diǎn)的操作
AvlTree?Insert(ElemType?x,?AvlTree?T,?bool?&?taller)
{
????if(T?==?NULL)
????{
????????T?=?(Position)malloc(sizeof(struct?avlnode));
????????if(T?==?NULL)
????????{
????????????puts("wrong");
????????????exit(1);
????????}
????????T->data?=?x;
????????T->lchild?=?T->rchild?=?NULL;
????????T->bf?=?EH;
????????taller?=?true;?//插入新結(jié)點(diǎn)，樹(shù)“長(zhǎng)高”，置taller為真值
????}
????else?if(T->data?==?x)//不做任何插入操作
????????taller?=?false;?//樹(shù)未長(zhǎng)高，置taller為假值
????else?if(T->data?>?x)//把x插入到左子樹(shù)中
????{
??????????T->lchild?=?Insert(x,?T->lchild,?taller);
??????????if?(taller)//已經(jīng)插入左子樹(shù)，且樹(shù)“長(zhǎng)高”，需要檢查平衡度，并做相應(yīng)處理
??????????{
??????????????????switch(T->bf)
??????????????????{
????????????????????????case?LH?:???T?=?LeftBalance(T);//原本左樹(shù)高于右樹(shù)，需做左平衡處理，樹(shù)高不變
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
????????????????????????case?EH?:???T->bf?=?LH;//原本左右等高，現(xiàn)在左高于右，且樹(shù)“長(zhǎng)高”
????????????????????????????????????taller?=?true;
????????????????????????????????????break;
????????????????????????case?RH?:???T->bf?=?EH;?//原本右樹(shù)高于左樹(shù)，現(xiàn)在左右等高，樹(shù)高不變
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
??????????????????}
????????????}
????}
????else??????//把x插入到右子樹(shù)中，仿照處理左樹(shù)的方法處理
????{
????????????T->rchild?=?Insert(x,?T->rchild,?taller);
??????????if?(taller)
??????????{
??????????????????switch(T->bf)
??????????????????{
????????????????????????case?LH?:???T->bf?=?EH;
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
????????????????????????case?EH?:???T->bf?=?RH;
????????????????????????????????????taller?=?true;
????????????????????????????????????break;
????????????????????????case?RH?:???T?=?RightBalance(T);
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
??????????????????}
????????????}
????}
????return?T;
}
AVL樹(shù)應(yīng)用示例:
?/*輸入一組數(shù),存儲(chǔ)到AVL樹(shù)中,并進(jìn)行輸出*/
#include?<iostream>
using?namespace?std;
#define?MAX?100
enum??BALANCE{LH?=?1,?EH?=?0,?RH?=?-1};
typedef?struct?avlnode
{
????BALANCE?bf;//比普通二杈有序樹(shù)多了一個(gè)平衡因子信息
????int?data;
????struct?avlnode?*lchild,?*rchild;
}?*AvlTree,?*Position;
int?Input(int?a[]);//輸入數(shù)據(jù)到數(shù)組,未排序
void?Print(const?int?a[],?int?len);?//輸入未排序的原始數(shù)據(jù)
AvlTree?Sort(AvlTree?A,?const?int?a[],?int?len);?//對(duì)數(shù)據(jù)進(jìn)行排序
AvlTree?Insert(int?x,?AvlTree?T,?bool?&?taller);?//把數(shù)據(jù)存儲(chǔ)到AVL樹(shù)中
Position?SingleRotateWithLeft(Position?K2);?//單左旋轉(zhuǎn)
Position?SingleRotateWithRight(Position?K2);?//單右旋轉(zhuǎn)
Position?DoubleRotateWithLeft(Position?K3);//雙左旋轉(zhuǎn)
Position?DoubleRotateWithRight(Position?K3);//雙右旋轉(zhuǎn)
AvlTree?LeftBalance(AvlTree?T);//?左平衡處理
AvlTree?RightBalance(AvlTree?T);?//右平衡處理
void?inorder(const?AvlTree?bt);?//中序遍歷AVL樹(shù)
void?PrintBT(AvlTree?bt);?//輸出二杈樹(shù)
int?main(void)
{
????int?a[MAX]={0};
????int?len;
????AvlTree?A=NULL;
????len?=?Input(a);
????Print(a,?len);
????printf("\n");
????A?=?Sort(A,?a,?len);
????PrintBT(A);
????printf("\n");
????inorder(A);
????system("pause");
??????return?0;
}
int?Input(int?a[])
{
????int?i=0;
????do{
????????a[i++]?=?rand()%1000;//輸入隨機(jī)數(shù)
????}?while(i<MAX);
????return?i;
}
void?Print(const?int?a[],?int?len)
{
????int?i;
????for(i=0;?i<len;?i++)
????????printf("%d\t",?a[i]);
}
AvlTree?Sort(AvlTree?A,?const?int?a[],?int?len)
{
????int?i;
????bool?taller?=?false;
????for(i=0;?i<len;?i++)
?????????A?=?Insert(a[i],?A,?taller);
????return?A;
}
void?inorder(const?AvlTree?bt)
{
????AvlTree?p=bt,?stack[MAX];//p表示當(dāng)前結(jié)點(diǎn)，棧stack[]用來(lái)存儲(chǔ)結(jié)點(diǎn)
????int?top=-1;
????do
????{
????????while(p?!=?NULL)//先處理結(jié)點(diǎn)的左孩子結(jié)點(diǎn)，把所有左孩子依次入棧
????????{
????????????stack[++top]?=?p;
????????????p?=?p->lchild;
????????}
????????if(top?>=?0)?//所有左孩子處理完畢后
????????{
????????????p?=?stack[top--];//棧頂元素出棧
????????????printf("%d\t",?p->data);?//輸出該結(jié)點(diǎn)
????????????p?=?p->rchild;?//處理其右孩子結(jié)點(diǎn)
????????}
????}?while((p?!=?NULL)||(top?>=?0));
}
//向AVL樹(shù)插入結(jié)點(diǎn)的操作
AvlTree?Insert(int?x,?AvlTree?T,?bool?&?taller)
{
????if(T?==?NULL)
????{
????????T?=?(Position)malloc(sizeof(struct?avlnode));
????????if(T?==?NULL)
????????{
????????????puts("wrong");
????????????exit(1);
????????}
????????T->data?=?x;
????????T->lchild?=?T->rchild?=?NULL;
????????T->bf?=?EH;
????????taller?=?true;?//插入新結(jié)點(diǎn)，樹(shù)“長(zhǎng)高”，置taller為真值
????}
????else?if(T->data?==?x)//不做任何插入操作
????????taller?=?false;?//樹(shù)未長(zhǎng)高，置taller為假值
????else?if(T->data?>?x)//把x插入到左子樹(shù)中
????{
??????????T->lchild?=?Insert(x,?T->lchild,?taller);
??????????if?(taller)//已經(jīng)插入左子樹(shù)，且樹(shù)“長(zhǎng)高”，需要檢查平衡度，并做相應(yīng)處理
??????????{
??????????????????switch(T->bf)
??????????????????{
????????????????????????case?LH?:???T?=?LeftBalance(T);//原本左樹(shù)高于右樹(shù)，需做左平衡處理，樹(shù)高不變
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
????????????????????????case?EH?:???T->bf?=?LH;//原本左右等高，現(xiàn)在左高于右，且樹(shù)“長(zhǎng)高”
????????????????????????????????????taller?=?true;
????????????????????????????????????break;
????????????????????????case?RH?:???T->bf?=?EH;?//原本右樹(shù)高于左樹(shù)，現(xiàn)在左右等高，樹(shù)高不變
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
??????????????????}
????????????}
????}
????else??????//把x插入到右子樹(shù)中，仿照處理左樹(shù)的方法處理
????{
????????????T->rchild?=?Insert(x,?T->rchild,?taller);
??????????if?(taller)
??????????{
??????????????????switch(T->bf)
??????????????????{
????????????????????????case?LH?:???T->bf?=?EH;
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
????????????????????????case?EH?:???T->bf?=?RH;
????????????????????????????????????taller?=?true;
????????????????????????????????????break;
????????????????????????case?RH?:???T?=?RightBalance(T);
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
??????????????????}
????????????}
????}
????return?T;
}
Position?SingleRotateWithLeft(Position?K2)
{
????Position?K1;
????K1?=?K2->lchild;??//在K2和K1之間進(jìn)行一次單左旋轉(zhuǎn)
????K2->lchild?=?K1->rchild;
????K1->rchild?=?K2;
????return?K1;
}
Position?SingleRotateWithRight(Position?K2)
{
????Position?K1;
????K1?=?K2->rchild;????//在K2和K1之間進(jìn)行一次單右旋轉(zhuǎn)
????K2->rchild?=?K1->lchild;
????K1->lchild?=?K2;
????return?K1;
}
Position?DoubleRotateWithLeft(Position?K3)
{
????K3->lchild?=?SingleRotateWithRight(K3->lchild);?//在K2和K1之間進(jìn)行一次單右旋轉(zhuǎn)
????return?SingleRotateWithLeft(K3);?//在K3和K2之間進(jìn)行一次單左旋轉(zhuǎn)
}
Position?DoubleRotateWithRight(Position?K3)
{
????K3->rchild?=?SingleRotateWithLeft(K3->rchild);?//在K2和K1之間進(jìn)行一次單左旋轉(zhuǎn)
????return?SingleRotateWithRight(K3);//在K3和K2之間進(jìn)行一次單右旋轉(zhuǎn)
}
AvlTree?LeftBalance(AvlTree?T)?//左平衡處理
{
??????AvlTree?lT?=?T->lchild;
??????switch?(lT->bf)?//檢查左樹(shù)的平衡度，并做相應(yīng)處理
??????{
????????????case?LH?:???T?=?SingleRotateWithLeft(T);?//若新結(jié)點(diǎn)插入在T的左孩子的左子樹(shù)上，對(duì)T單左旋轉(zhuǎn)
????????????????????????T->bf?=?lT->bf?=?EH;???//重新設(shè)置平衡度
????????????????????????break;
????????????case?RH?:???AvlTree?rT?=?lT->rchild;//若新結(jié)點(diǎn)插入在T的左孩子的右子樹(shù)上，對(duì)T雙左旋轉(zhuǎn)，并重新設(shè)置平衡度
????????????????????????switch?(rT->bf)
????????????????????????{
??????????????????????????????case?LH?:???T->bf?=?RH;
??????????????????????????????????????????lT->bf?=?EH;
??????????????????????????????????????????break;
??????????????????????????????case?EH?:???T->bf?=?lT->bf?=?EH;?//我感覺(jué)這種情況應(yīng)該不會(huì)出現(xiàn)
??????????????????????????????????????????break;
??????????????????????????????case?RH?:???T->bf?=?EH;
??????????????????????????????????????????lT->bf?=?LH;
??????????????????????????????????????????break;
????????????????????????}
????????????????????????rT->bf?=?EH;
????????????????????????T?=?DoubleRotateWithLeft(T);
????????????????????????break;
??????}
??????return?T;
}
AvlTree?RightBalance(AvlTree?T)?//右平衡處理
{
??????AvlTree?rT?=?T->rchild;
??????switch?(rT->bf)?//檢查右樹(shù)的平衡度，并做相應(yīng)處理
??????{
????????????case?RH?:???T?=?SingleRotateWithRight(T);?//若新結(jié)點(diǎn)插入在T的右孩子的右子樹(shù)上，對(duì)T單右旋轉(zhuǎn)
????????????????????????T->bf?=?rT->bf?=?EH;???//重新設(shè)置平衡度
????????????????????????break;
????????????case?LH?:???AvlTree?lT?=?rT->lchild;//若新結(jié)點(diǎn)插入在T的右孩子的左子樹(shù)上，對(duì)T雙右旋轉(zhuǎn)，并重新設(shè)置平衡度
????????????????????????switch?(lT->bf)
????????????????????????{
??????????????????????????????case?LH?:???T->bf?=?EH;
??????????????????????????????????????????rT->bf?=?RH;
??????????????????????????????????????????break;
??????????????????????????????case?EH?:???T->bf?=?rT->bf?=?EH;?//我感覺(jué)這種情況應(yīng)該不會(huì)出現(xiàn)
??????????????????????????????????????????break;
??????????????????????????????case?RH?:???T->bf?=?LH;
??????????????????????????????????????????rT->bf?=?EH;
??????????????????????????????????????????break;
????????????????????????}
????????????????????????lT->bf?=?EH;
????????????????????????T?=?DoubleRotateWithRight(T);
????????????????????????break;
??????}
??????return?T;
}
void?PrintBT(AvlTree?bt)
{
????if(bt?!=?NULL)
????{
????????printf("%d",?bt->data);
????????if(bt->lchild!=NULL?||?bt->rchild!=NULL)
????????{
????????????printf("(");
????????????PrintBT(bt->lchild);
????????????if(bt->rchild!=NULL)
????????????????printf(",");
????????????PrintBT(bt->rchild);
????????????printf(")");
????????}
????}
}