AVL树的旋转！
对于AVL树的旋转不是很明白，单旋转还好，双旋转就搞不懂什么规律了！高手们给说下规律吧，或贴个连接什么的！
[解决办法]
学习没有捷径, 靠自己努力. 要说规律的话, 观察左子树高度跟右子树高度差, 让树平衡, 仅此而已.
[解决办法]
增加和删除可能需要通过一次或多次树旋转来重新平衡这个树.
http://bbs.pfan.cn/post-206194-1.html
typedef struct BSTNode {
ElemType data ;
int bf ; //结点的平衡因子
struct BSTNode *lchild , *rchild ; //左、右孩子指针
}BSTNode , *BSTree ;
void R_Rotate (BSTree &p) {
//对以*p为根的二叉排序树作右旋转处理，处理之后p指向新的树根结点，即旋转
//处理之前的左子树的根结点
lc=p->lchild ; //lc指向的*p的左子树根结点
p->lchild=lc->rchild ; //lc的右子树挂接为*p的左子树
lc->rchild=p ; p=lc ; //p指向新的根结点
}// R_Rotate
void L_Rotate (BSTree &p) {
//对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转
//处理之前的右子树的根结点
rc=p->rchild ; //rc指向的*p的右子树根结点
p->rchild=rc->lchild ; //rc左子树挂接为*p的右子树
rc->lchild=p ; p=rc ; //p指向新的根结点
}//L_Rotate
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高
Status InsertAVL (BSTree &T , ElemType e , Boolean &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 0 ; } //则不插入
if (LT(e.key , T->data.key)) { //继续在*T的左子树中进行搜索
if (!InsertAVL(T->lchild , e , taller)) return 0; //未插入
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 ; break ;
}//switch(T->bf)
}//if
else { //继续在*T的左子树中进行搜索
if(!InsertAVL(T->rchild , e , taller)) return 0 ; //未插入
if (taller) //已插入到*T的右子树中且右子树“长高”
switch ( T->bf ) { //检查*T的平衡度
case LH: //原本左子树比右子树高，现左、右子树等高
T->bf=EH ; taller=FALSE ; break ;
case EH: //原本左、右子树等高，现因右子树增高而使树增高
T->bf=RH ; taller=FALSE ; break ;
case RH: //原本右子树比左子树高，需要作右平衡处理
RightBalance(T) ; taller=FALSE ; break ;
}//switch(T->bf)
}//else
}//else
return 1;
}//InsertAVL
void LeftBalance (BSTree &T) {
//对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针T指向
//新的根结点
lc=T->lchild ; //lc指向*T的左子树根结点
switch (lc->bf) { //检查*T的左子树的平衡高度，并作相应平衡处理
case LH: //新结点插入在*T的左孩子的左子树上，要作单右旋处理
T->bf=lc->bf=EH ;
R_Rotate(T); break ;
case RH: //新结点插入在*T的左孩子的右子树上，要作双旋处理
rd=lc->rchild ; //rd指向*T的左孩子的右子树根
switch (rd->bf) { //修改*T及其左孩子的平衡因子
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)
rd->bf=EH;
L_Rotate(T->lchild) ; //对*T的左子树作左旋转处理
R_Rotate(T) ; //对*T作右旋转处理
}// switch (lc->bf)
}//LeftBalance
