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