对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是O(n),原因在于对树的形状没有限制。
平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点的平衡因子为只可能是：-1、0和1
一棵好的平衡二叉树的特征：
（1）保证有n个结点的树的高度为O(logn)
（2）容易维护，也就是说，在做数据项的插入或删除操作时，为平衡树所做的一些辅助操作时间开销为O(1)
一、平衡二叉树的构造
在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树
1.调整方法
（1）插入点位置必须满足二叉查找树的性质，即任意一棵子树的左结点都小于根结点，右结点大于根结点
（2）找出插入结点后不平衡的最小二叉树进行调整，如果是整个树不平衡，才进行整个树的调整。
2.调整方式
（1）LL型
LL型：插入位置为左子树的左结点，进行向右旋转
由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1变为2，成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转，旋转过程中遵循“旋转优先”的规则，A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。
（2）RR型
RR型：插入位置为右子树的右孩子，进行向左旋转
由于在A的右子树C的右子树插入了结点F，A的平衡因子由-1变为-2，成为不平衡的最小二叉树根结点。此时，A结点逆时针左旋转，遵循“旋转优先”的规则，A结点替换D结点成为C的左子树，D结点成为A的右子树。
（3）LR型
LR型：插入位置为左子树的右孩子，要进行两次旋转，先左旋转，再右旋转；第一次最小不平衡子树的根结点先不动，调整插入结点所在的子树，第二次再调整最小不平衡子树。
（4）RL型
RL型：插入位置为右子树的左孩子，进行两次调整，先右旋转再左旋转；处理情况与LR类似。
code：
#define LH +1
#define EH 0
#define RH -1
#define ElemType int
#define Status int
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)>(b))
typedef struct BSTNode
{
ElemType data;
int bf; // 节点的平衡因子
struct BSTNode * lchild, * rchild; //左右孩子指针
}BSTNode, * BSTree;
#include
#include
#include
using namespace std;
void R_Rotate(BSTree & p)
{
//对以*p 为根的二叉排序树做右旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点
BSTree lc;
lc = p->lchild;//lc指向p的左子树
p->lchild = lc->rchild;//p左子树lc的有右子树
lc->rchild = p; //lc右子树指向p
p = lc;//p指向新的根结点
}//R_Rotate
void L_Rotate(BSTree & p)
{
//对以*p 为根的二叉排序树做左旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点
BSTree rc;
rc = p->rchild;//rc指向p的左子树
p->rchild = rc->lchild;//p左子树rc的左子树
rc->lchild = p; //rc左子树指向p
p = rc;//p指向新的根结点
}//R_Rotate
void LeftBalance( BSTree & T)
{
BSTree lc,rd;
lc = T->lchild;
switch(lc->bf)
{
case LH:
lc->bf = T->bf = EH;
R_Rotate(T); break;
case RH:
rd = lc->rchild;
T->lchild = rd->rchild;
lc->rchild = rd->lchild;
rd->lchild = lc;
rd->rchild = T;
T = rd;
}//switch(lc->bf)
}//LeftBalance
void RightBalance( BSTree & T)
{
BSTree rc,rd;
rc = T->rchild;
switch(rc->bf)
{
case RH:
rc->bf = T->bf = EH;
L_Rotate(T); break;
case LH:
rd = rc->lchild;
T->rchild = rd->lchild;
rc->lchild = rd->rchild;
rd->rchild = rc;
rd->lchild = T;
T = rd;
}//switch(rc->bf)
}//RightBalance
Status InsertAVL ( BSTree &T , ElemType e, bool
&taller )
{//若平衡二叉树中不存在e，则插入新节点e返回1，否则返回0.
若因插入结点使树不平衡，进行旋转，taller代表树是否长高
if(!T){ //空树，直接插入
T = (BSTNode *)malloc(sizeof(BSTNode)); T->data =
e;
T->lchild = T->rchild = NULL; T->bf = EH; taller =
true;
}
else {
if(EQ(e,T->data) ){ taller= false;
return 0;} //已存在e
if(LT(e,T->data) ) { // e<根结点，向左查找左子树
if(!InsertAVL(T->lchild,e,taller) )
return 0;///未插入
if( taller ) //已插入左子树并使树长高
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; break;
}
}//if
else
{
if(!InsertAVL(T->rchild,e,taller) )
return 0;
if( taller )
switch (T->bf)
{
case LH:
T->bf = EH;taller = false; break;
case EH:
T->bf = RH; taller = true; break;
case RH:
RightBalance(T); taller = false; break;
}
}//else
}//else
return 1;
}//InsertAVL
void InOrderTraverse(BSTree T)
{//中序遍历二叉树，递归
if(T){
InOrderTraverse(T->lchild);
cout<< T->data<<" ";
InOrderTraverse(T->rchild);
}
}
int main()
{
ElemType e;
int n;
BSTree T;
T = NULL;
bool taller;
cout<<"请输入二叉平衡树结点个数:";
cin>>n;
cout<<"请输入"<<n<<"个要插入的元素（空格隔开）：";
while(n--){
cin>>e;
InsertAVL(T,e,taller);
}
cout<<"二叉排序树中序遍历为："; InOrderTraverse(T);
cout<<endl;
return 0;
}