一、平衡二叉树的概念
平衡二叉树(Balanced binary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。 定义：平衡二叉树或为空树,或为如下性质的二叉排序树: （1）左右子树深度之差的绝对值不超过1; （2）左右子树仍然为平衡二叉树.
平衡因子BF=左子树深度－右子树深度.
平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。
如图所示为平衡树和非平衡树示意图：
二、平衡二叉树算法思想
若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。
失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。 （1）LL型平衡旋转法
由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。
（2）RR型平衡旋转法
由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。
（3）LR型平衡旋转法
由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。
如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为LL型，再按LL型处理成平衡型。 （4）RL型平衡旋转法
由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置，然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型，再按RR型处理。
如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为RR型，再按RR型处理成平衡型。 平衡化靠的是旋转。参与旋转的是3个节点（其中一个可能是外部节点NULL），旋转就是把这3个节点转个位置。注意的是，左旋的时候p->right一定不为空，右旋的时候p->left一定不为空，这是显而易见的。 如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操作上，而不平衡的标志就是出现bf == 2或者 bf == -2的节点。
三、二叉排序数的操作及C语言描述
插入删除是互为镜像的操作。我们可以采用前面对二叉排序树的删除操作来进行。然后，在删除掉结点后，再对平衡树进行平衡化处理。删除之所以删除操作需要的平衡化可能比插入时次数多，就是因为平衡化不会增加子树的高度，但是可能会减少子树的高度，在有有可能使树增高的插入操作中，一次平衡化能抵消掉增高；在有可能使树减低的删除操作中，平衡化可能会带来祖先节点的不平衡。
四、二叉排序数的C语言实现
#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)) #define BT(a,b) ((a)> (b)) typedef int KeyType; typedef int info;
typedef int Boolean; typedef struct ElemType {
KeyType 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指向新的根结点 }//R_Rotate
void L_Rotate(BSTree &p) {//左旋 BSTree rc; rc=p->rchild;
p->rchild=rc->lchild; rc->lchild=p;
p=rc; //p指向新的根结点
}//L_Rotate
void LeftBalance(BSTree &T) {//作平衡旋转处理 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 }//LeftBalance
void RightBalance(BSTree &T) {//作平衡旋转处理 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 }//RightBalance
int InsertAVL(BSTree &T,ElemType e,int &taller)
{ // 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 // 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 // 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否 if(!T)
{ // 插入新结点，树“长高”，置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有相同关键字的结点则不再插入 taller=FALSE; return FALSE; }
if LT(e.key,T->data.key)
{ // 应继续在*T的左子树中进行搜索
if(!InsertAVL(T->lchild,e,taller)) // 未插入 return FALSE;
if(taller) // 已插入到*T的左子树中且左子树“长高” switch(T->bf) // 检查*T的平衡度 {
case LH: // 原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FALSE; break;
case EH: // 原本左、右子树等高，现因左子树增高而使树增高 T->bf=LH; taller=TRUE; break;
case RH: T->bf=EH; // 原本右子树比左子树高，现左、右子树等高 taller=FALSE; } }
else
{ // 应继续在*T的右子树中进行搜索
if(!InsertAVL(T->rchild,e,taller)) // 未插入 return FALSE;
if(taller) // 已插入到T的右子树且右子树“长高” switch(T->bf) // 检查T的平衡度 {
case LH: T->bf=EH; // 原本左子树比右子树高，现左、右子树等高 taller=FALSE; break;
case EH: // 原本左、右子树等高，现因右子树增高而使树增高 T->bf=RH; taller=TRUE; break;
case RH: // 原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; } } }
return TRUE; }
BSTree SearchBST(BSTree T,KeyType key)
{ // 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素， // 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。 if((!T)||EQ(key,T->data.key)) return T; // 查找结束
else if LT(key,T->data.key) // 在左子树中继续查找 return SearchBST(T->lchild,key); else
return SearchBST(T->rchild,key); // 在右子树中继续查找 }//SearchBST
void DestroyDSTable(BSTree &DT)
{ // 初始条件: 动态查找表DT存在。操作结果: 销毁动态查找表DT if(DT) // 非空树 {
if(DT->lchild) // 有左孩子
DestroyDSTable(DT->lchild); // 销毁左孩子子树 if(DT->rchild) // 有右孩子
DestroyDSTable(DT->rchild); // 销毁右孩子子树 free(DT); // 释放根结点 DT=NULL; // 空指针赋0
}//if
}//DestroyDSTable
int InitDSTable(BSTree &DT)
{ // 操作结果: 构造一个空的动态查找表DT DT=NULL; return 1; }//InitDSTable
void Visit(BSTree DT) {
//printf(\"DT->data.key:->%d\\nT->bf:%d\\n\printf(\"DT->data.key:->%d\\n\}//Visit
void TraverseDSTable(BSTree &DT,void(*Visit)(BSTree))
{ // 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数
// 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次 if(DT) {
TraverseDSTable(DT->lchild,Visit); // 先中序遍历左子树 Visit(DT); // 再访问根结点
TraverseDSTable(DT->rchild,Visit); // 最后中序遍历右子树 } }
int InsertAVLD(BSTree &T) {
ElemType e; Boolean taller;
printf(\"input the data until -1\\n\"); scanf(\"%d\while(e.key!=-1) {
InsertAVL(T,e,taller);
printf(\"input the data until -1\\n\"); scanf(\"%d\ }
return 1;
}//InsertAVLD
void 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 }//LeftBalanceD
void 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
}//RightBalanceD
int SearchBSTD(BSTree &T) {
ElemType e;
printf(\"\\nplease input the number you want to search:\\n\"); scanf(\"%d\
if(SearchBST(T,e.key)!=NULL) printf(\"%d\else printf(\"failed!\"); return 1;
}//SearchBSTD
int Delete(BSTree &T,KeyType key,int &shorter) {
int success=0;//标志成功删除与否 if(T) {
if(EQ(key,T->data.key))
{//相等，即当前结点就是要删除的结点 if(T->lchild!=NULL&&T->rchild!=NULL) {//要删除结点的左右子树都不空 BSTree q,r;
//接下来，找到要删除数据的前驱结点，并且将数据与直接前驱 //交换。这样我们将其前驱删除掉后，再调整平衡树就好了。 q=T->lchild;
r=q;//用r来指向其前驱接点。 while(q) { r=q;
q=q->rchild; }//while(q)
KeyType temp=T->data.key; T->data.key=r->data.key; r->data.key=temp;
//接下来，在左子树上删除其前驱接点 success=Delete(T->lchild,key,shorter);
if(shorter)
{//由于删除操作导致了树变小了 switch(T->bf) {
case LH:T->bf=EH;break; case EH:T->bf=RH;break;
case RH:RightBalanceD(T,shorter);break; }//switch }//if
}//if-要删除结点左右子树都不空 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))
{//在左子树上查询要删除的结点
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 }//if<
else if(BT(key,T->data.key))
{//在右子树上查询要删除的结点
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; }//Delete
int DeleteD(BSTree &T) {
ElemType e; int shorter;
printf(\"\\ninput the data you want to delete:\\n\"); scanf(\"%d\Delete(T,e.key,shorter); return 1; }//Delete int main() {
BSTree T;
InitDSTable(T); InsertAVLD(T);
TraverseDSTable(T,Visit); SearchBSTD(T); DeleteD(T);
TraverseDSTable(T,Visit); DestroyDSTable(T); return 1; }
五、复杂度分析
在平衡二叉树上进行查找的过程与二叉排序树的查找算法相同。因此，在查找过程中和关键字进行比较的次数不超过树的深度。含有n个结点的平衡树的最大深度为：
上述讨论，都是在等概率情形下的。如果不是，则为了提高效率，需对等查记录先进行排序，然后构造次优查找树。但是次优查找树不能在查找过程中生成。二叉排序树是动态的，次优查找树是静态的。 六、语法知识点
1、函数名作为参数传递
关于这一点，前面有过讨论。
http://blog.163.com/zhoumhan_0351/blog/static/3995422720093267341920/ 今天我们再做一个总结。
a)一个函数在编译时，也会给它分配一个入口地址。这个入口地址就称为函数的指针。可用一个指针变量指向函数，然后通过该指针变量来调用此函数。如 int max(int x,int y) {……}
int (*p)(); //定义一个函数指针变量p.
p=max;//将max函数的起始地址赋给指针p. c=(*p)(a,b); //等价于c=max(a,b);
注意：对于函数指针来说，*(p+1)等操作是违法的。 b)指向函数指针变量的定义格式： 数据类型 （*指针变量名）（）;
这里的数据类型是函数返回值的数据类型。这个指针变量就是专门用来存放函数入口地址的。在一个程序中，一个指针变量可以先后指向返回类型不同的函数。在给函数指针赋值时，只需给出函数名而不必给出参数。再如 double (*f)(double)=exp; or
f=log10;
我们在程序中的函数TraverseDSTable(BSTree &DT,void(*Visit)(ElemType))便是这样。其为返回值为空型，只有一个参数的指指变量，定调用时： TraverseDSTable(T,Visit);其中，Visit便是函数名。 2、带参数的宏定义 一般形式为：
#define 宏名（参数表） 字符串
在程序中，在编译前，按宏定义命令行中指定的字符串从左到右进行置换，并不分配内存单元，也没有返回值的说法。如： #define EQ(a,b) ((a)==(b))
则凡是程序中出现有EQ(a,b)的地方，则替换成((a)==(b))表达式。 七、弦外之音
关于二叉平衡树的插入的删除的讨论，网上一位网友曾有如下论述，原网址为http://www.yuanma.org/data/2009/0825/article_3877.htm，在这里贴出来，以作思考。 插入和删除
AVL树体现了一种平衡的美感，两种旋转是互为镜像的，插入删除是互为镜像的操作，没理由会有那么大的差别。实际上，平衡化可以统一的这样来操作： 1、while (current != NULL)修改current的平衡因子。
（1）插入节点时current->bf += (current->data > *p)?1:-1; （2）删除节点时current->bf -= (current->data > *p)?1:-1;
（3）current指向插入节点或者实际删除节点的父节点，这是普通二叉搜索树的插入和删除操作带来的结果。*p初始值是插入节点或者实际删除节点的data。因为删除操作可能实际删除的不是data。 2、判断是否需要平衡化
if (current->bf == -2) L_Balance(c_root); else if (current->bf == 2) R_Balance(c_root); 3、是否要继续向上修改父节点的平衡因子 （1）插入节点时if (!current->bf) break;这时，以current为根的子树的高度和插
入前的高度相同。
（2）删除节点时if (current->bf) break;这时，以current为根的子树的高度和删除前的高度相同
4、当前节点移动到父节点，转1。
p = &(current->data); current = current->parent; 完整的插入删除函数如下： bool insert(const T &data) {
if (!BSTree current->bf += (current->data > *p)?1:-1; if (current->bf == -2) L_Balance(c_root); else if (current->bf == 2) R_Balance(c_root); if (!current->bf) break; p = &(current->data); current = current->parent; } return true; } bool remove(const T &data) { if (!BSTree current->bf -= (current->data > *p)?1:-1; if (current->bf == -2) L_Balance(c_root); else if (current->bf == 2) R_Balance(c_root); if (current->bf) break; p = &(current->data); current = current->parent; } return true; } 你可以看到，他们是多么的对称。 注：关于二叉平衡树的插入、删除操作中平衡因子的更新，还有待进一步的探讨及争鸣更为简化和统一的处理方法。 因篇幅问题不能全部显示，请点此查看更多更全内容