AVLアルゴリズム
11593 ワード
#include<stdio.h>
#include<stdlib.h>
#define EH 0
#define LH 1
#define RH -1
typedef struct Bitree
{
int data;
int bf; //
struct Bitree * lchild,*rchild;
}Bitree,*BiNtree;
void R_Roate(BiNtree *t); // *t
void L_Roate(BiNtree *t); // *t
void LeftBalance(BiNtree *t); //
void ReftBalance(BiNtree *t); //
void inserttree(BiNtree *t,int number,int *taller); //
void createtree(BiNtree *t); //
int SearchBST(BiNtree t,int key,int count); // key Ｔ
void LeftBalance_div(BiNtree *p,int *shorter); //
void RightBalance_div(BiNtree *p,int *shorter); //
void Delete(BiNtree q,BiNtree *r,int *shorter); //
int DeleteAVL(BiNtree *p,int x,int *shorter); //
void main()
{
int input,search,m;
//int taller=false;
int count;
int shorter=0;
int taller=0;
BiNtree T,T1,T2;
//T=(BSTree)malloc(sizeof(BSTNode));
T=T1=T2=NULL;
while(1)
{
count=1;
system("cls");
printf(" ******************************************
");
printf(" ╱◥██◣ *1. \t2. \t3. \t4. \t5. *
");
printf("｜ ｜ │ ******************************************
");
printf("╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬< V1.0>
");
printf(" :\t");
scanf("%d",&input);getchar();
switch(input)
{
case 1:
createtree(&T); break;
case 2:
printf(" ");
scanf("%d",&search); getchar();
if(SearchBST(T,search,count))
{
count=SearchBST(T,search,count);
printf(" %d，%d, !
",search,count);
}
else printf(" !
");
break;
case 3:
printf(" ");
scanf("%d",&search); getchar();
inserttree(&T,search,&taller); m = 0;
//PrintBST(T,m);
break;
case 4:
printf(" ");
scanf("%d",&search); getchar();
DeleteAVL(&T,search,&shorter);
// m=0; PrintBST(T,m);
break;
case 5:
printf("\t\tbyebye!
");break;
default:printf(" ， 。");break;
}
if(input == 5) break;
printf("\t\t ..."); getchar();
}
}
// *t
void R_Roate(BiNtree *t)
{
BiNtree temp;
temp= (*t)->lchild;
(*t)->lchild=temp->rchild;
temp->rchild=*t;
*t=temp;
}
// *t
void L_Roate(BiNtree *t)
{
BiNtree temp;
temp =(*t)->rchild;
(*t)->rchild=temp->lchild;
temp->lchild=*t;
*t=temp;
}
//
void LeftBalance(BiNtree *t)
{
BiNtree lc,rd;
lc=(*t)->lchild;
switch(lc->bf)
{
case LH: // *T ，
(*t)->bf = lc->bf = EH;
R_Roate(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;
}
rd->bf = EH;
L_Roate(&(*t)->lchild); // *T
R_Roate(t); // *T
}
}
//
void RightBalance(BiNtree *t)
{
BiNtree rc,ld;
rc = (*t)->rchild; //rc *T
switch(rc->bf) // *T ，
{
case RH: // *T ，
(*t)->bf = rc->bf =EH;
L_Roate(t); break;
case LH: // *T ，
ld = rc->lchild; //ld *T
switch(ld->bf) // *T
{
case LH: (*t)->bf = EH; rc->bf = RH; break;
case EH: (*t)->bf = rc->bf =EH; break;
case RH: (*t)->bf = LH; rc->bf = EH; break;
}
ld->bf = EH;
R_Roate(&(*t)->rchild);// *T
L_Roate(t); // *T
}
}
//
void inserttree(BiNtree *t,int number,int *taller)
{
if(*t==NULL)
{
*t=(BiNtree)malloc(sizeof(Bitree));
(*t)->data=number;
(*t)->lchild=(*t)->rchild=NULL;
(*t)->bf=EH;
*taller=1;
}
else
{
if(number<(*t)->data)
{
inserttree(&(*t)->lchild,number,taller);
if(*taller)
switch((*t)->bf)
{
case LH: // ，
LeftBalance(t);
*taller = 0;
break;
case EH:
(*t)->bf = LH; // 、 ，
*taller = 1;
break;
case RH: // ， 、
(*t)->bf = EH;
*taller = 0;
break;
}//switch(T->bf)
}
if(number>(*t)->data) // *T
{
inserttree(&(*t)->rchild,number,taller);
if(taller) // *T “ ”
switch((*t)->bf) // *T
{
case LH: // ， 、
(*t)->bf = EH;
*taller = 0;
break;
case EH: // 、 ，
(*t)->bf = RH;
*taller = 1;
break;
case RH: // ，
RightBalance(t);
*taller = 0;
break;
} //switch(T->bf)
}
}
}
// ，（ ： －１ ）
void createtree(BiNtree *t)
{
int e,m;
int taller=0; //0 ，1
*t= NULL;
printf("
( -1 ):");
scanf("%d",&e);getchar();
while(e != -1)
{
inserttree(t,e,&taller);
printf("
( -1 ):");
scanf("%d",&e);getchar();
taller=0;
}
}
// key Ｔ
int SearchBST(BiNtree t,int key,int count)
{
if(!t) return -1;
else if(key==t->data) return count;
else if(key<t->data) return SearchBST(t->lchild,key,count+1);
else return SearchBST(t->rchild,key,count+1);
}
//
void LeftBalance_div(BiNtree *p,int *shorter)
{
BiNtree p1,p2;
if((*p)->bf==1) //p ， p bf 1,
{ (*p)->bf=0; *shorter=1; }
else if((*p)->bf==0) //p 、 ， p bf 1,
{ (*p)->bf=-1; *shorter=0; }
else //p
{
p1=(*p)->rchild; //p1 p
if(p1->bf==0) //p1 、 , p bf -2, ，
{
L_Roate(p);
p1->bf=1; (*p)->bf=-1; *shorter=0;
}
else if(p1->bf==-1) //p1 ， ，
{
L_Roate(p);
p1->bf=(*p)->bf=0; *shorter=1;
}
else //p1 , ( )，
{
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;
}
}
}
//
void RightBalance_div(BiNtree *p,int *shorter)
{
BiNtree p1,p2;
if((*p)->bf==RH)
{ (*p)->bf=EH; *shorter=1; }
else if((*p)->bf==EH)
{ (*p)->bf=LH; *shorter=0; }
else
{
p1=(*p)->lchild;
if(p1->bf==EH)
{
R_Roate(p);
p1->bf=RH;
(*p)->bf=LH;
*shorter=0;
}
else if(p1->bf==LH)
{
R_Roate(p);
p1->bf=(*p)->bf=EH;
*shorter=1;
}
else
{
p2=p1->rchild;
p1->rchild=p2->lchild;
p2->lchild=p1;
(*p)->lchild=p2->rchild;
p2->rchild=*p;
if(p2->bf==EH)
{ (*p)->bf=EH; p1->bf=EH; }
else if(p2->bf==LH)
{ (*p)->bf=RH; p1->bf=EH; }
else
{ (*p)->bf=EH; p1->bf=LH; }
p2->bf=EH;
*p=p2;
*shorter=1;
}
}
}
//
void Delete(BiNtree q,BiNtree *r,int *shorter)
{
if((*r)->rchild==NULL)
{
q->data=(*r)->data;
q=*r;
*r=(*r)->lchild;
free(q);
*shorter=1;
}
else
{
Delete(q,&(*r)->rchild,shorter);
if(*shorter==1)
RightBalance_div(r,shorter);
}
}
//
int DeleteAVL(BiNtree *p,int x,int *shorter)
{
int k;
BiNtree q;
if(p==NULL) { printf(" !!
"); return 0;}
else if(x<(*p)->data)// p
{
k=DeleteAVL(&(*p)->lchild,x,shorter);
if(*shorter==1)
LeftBalance_div(p,shorter);
return k;
}
else if(x>(*p)->data)// p
{
k=DeleteAVL(&(*p)->rchild,x,shorter);
if(*shorter==1)
RightBalance_div(p,shorter);
return k;
}
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//
{
Delete(q,&q->lchild,shorter);
if(*shorter==1)
LeftBalance_div(p,shorter);
*p=q;
}
return 1;
}
}