#include <stdio.h>
#include <stdlib.h>
# define LH 1
# define EH 0
# define RH -1
# define TRUE 1
# define FALSE 0

int taller=0; /*taller反映T长高与否*/
int shorter=0; /*shorter反映T变矮与否*/

typedef struct BSTNode
{ /*二叉排序树的类型定义*/
int data;
int bf; /*结点的平衡因子*/
struct BSTNode * lchild, * rchild;
}BSTNode, *BSTree;

BSTree R_Rotate(BSTree p)
{ /*对以p为根的二叉排序树作右旋处理，处理之p指向新的树根结点*/
/*即旋转处理之前的左子树根结点*/
BSTNode *lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p;p=lc;
return p;
} /*R_Rotate*/

BSTree L_Rotate(BSTree p)
{ /*对以p为根的二叉排序树作左旋处理，处理之p指向新的树根结点*/
/*即旋转处理之前的右子树根结点*/
BSTNode *rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;p=rc;
return p;
}/*L_Rotate*/

BSTree LeftBalance(BSTree T)
{ /*对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时*/
/*指针T指向新的根结点*/
BSTNode *lc,*rd;
lc=T->lchild;
switch(lc->bf)
{
case LH: T->bf=lc->bf=EH;
T=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;
}
rd->bf=EH;
T->lchild=L_Rotate(T->lchild);
T=R_Rotate(T);
}
return T;
}

BSTree RightBalance(BSTree T)
{ /*对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时*/
/*指针T指向新的根结点*/
BSTree rc,ld;
rc=T->rchild;
switch(rc->bf)
{
case RH:T->bf=rc->bf=EH;
T=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;
}
ld->bf=EH;
T->rchild=R_Rotate(T->rchild);
T=L_Rotate(T);
}
return T;
}
BSTree Insert(BSTree T,int e)
{ BSTree p;
if(!T)
{
T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
}
else
{
if(e==T->data)
{
taller=FALSE;
return NULL;
}
if(e < T->data)
{
p=Insert(T->lchild,e);
}
else
{
p=Insert(T->rchild,e);
}
return T;
}
BSTree InsertAVL(BSTree T, int e)
{ /*若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个
/*数据元素为e的新结点,并返回插入后所建成的平衡二叉排序树,否则返回
/*NULL.若因插入而使二叉数失去平衡,则作平衡旋转处理,布尔变量taller
/*反映T长高与否*/
BSTree p;
if(!T)
{
T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=TRUE;
}
else
{
if(e==T->data)
{
taller=FALSE;
return NULL;
}
if(e < T->data)
{
p=InsertAVL(T->lchild,e);
if(p)
{
T->lchild=p;
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
{
p=InsertAVL(T->rchild,e);
if (p)
{
T->rchild=p;
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;
}

BSTree midorder(BSTree T)
{ /*树的中序遍历的递归算法*/
if(T!=NULL)
{
midorder(T->lchild);
printf("%d ",T->data);
midorder(T->rchild);
}
}

BSTree RightBalance1(BSTree p)
{ /*删除结点时对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时*/
/*指针T指向新的根结点*/
BSTree p1,p2;
if(p->bf==-1)
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)
{
p->bf=1;
shorter=0;
}
else
{
p1=p->lchild;
if(p1->bf==0)
{
p->lchild = p1->rchild;
p1->rchild = p;
p1->bf=-1;
p->bf=1;
p=p1;
shorter=0;
}
else if(p1->bf==1)
{
p->lchild=p1->rchild;
p1->rchild=p;
p1->bf=p->bf=0;
p=p1;
shorter=1;
}
else
{
p2=p1->rchild;
p1->rchild = p2->lchild;
p2->lchild = p1;
p->lchild = p2->rchild;
p2->rchild = p;
if(p2->bf == 0)
{
p->bf = 0;
p1->bf = 0;
}
else if(p2->bf == 1)
{
p->bf = -1;
p1->bf = 0;
}
else
{
p->bf=0;
p1->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
return p;
}

BSTree LeftBalance1(BSTree p)
{ /*删除结点时对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时*/
/*指针T指向新的根结点*/
BSTree p1,p2;
if(p->bf==1)
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)
{
p->bf=-1;
shorter=0;
}
else
{
p1=p->rchild;
if(p1->bf==0)
{
p->rchild = p1->lchild;
p1->lchild = p;
p1->bf = 1;
p->bf = -1;
p = p1;
shorter = 0;
}
else if(p1->bf==-1)
{
p->rchild=p1->lchild;
p1->lchild=p;
p1->bf=p->bf=0;
p=p1;
shorter=1;
}
else
{
p2=p1->lchild;
p1->lchild=p2->rchild;
p2->rchild=p1;
p->rchild=p2->lchild;
p2->lchild=p;
if(p2->bf==0)
{
p->bf=0;
p1->bf=0;
}
else if(p2->bf==-1)
{
p->bf=1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=-1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
return p;
}

BSTree Delete(BSTree q, BSTree r)
{ /*对结点进行删除处理*/
if(r->rchild==NULL)
{
q->data=r->data;
q=r;
r=r->lchild;
free(q);
shorter=1;
}
else
{
r->rchild=Delete(q,r->rchild);
}
return r;
}

BSTree DeleteAVL(BSTree p, int e)
{ /*找到要删除的结点,并调用删除函数对其进行删除*/
BSTree q;
if(p==NULL)
return NULL;
else if(e < p->data)
{
p->lchild = DeleteAVL(p->lchild,e);
if(shorter==1)
p=LeftBalance1(p);
return p;
}
else if(e > p->data)
{
p->rchild=DeleteAVL(p->rchild,e);
if(shorter==1)
p=RightBalance1(p);
return p;
}
else
{
q=p;
if(p->rchild==NULL)
{
p=p->lchild;
free(q);
shorter=1;
}
else if(p->lchild==NULL)
{
p=p->rchild;
free(q);
shorter=1;
}
else
{
q->lchild=Delete(q,q->lchild);
if(shorter==1)
q=LeftBalance1(q);
p=q;
}
}
return p;
}