/*
1.插入：
	使用了一个s数组来保存根节点到插入节点的路线
	情况：
	（1）空树，直接插入，return
	（2）关键字相同，覆盖原来的值，return
	（3）插入后，不失衡 那么就要拿出s数组的值来改变这条路线的平衡因子。
	（4）插入后，失衡 调用AVL函数。

	 AVL旋转有分为4种
	 ll rr rl lr旋转（在设置平衡因子的时候，rl和lr旋转又有3种子情况）

2.查找：（未实现）
	不同的key可能获取一样的num_key，那么继续向左走

3.删除：（未实现）
	情况分为3种
	（1）节点的平衡因子为-1，用右边的最小值num_key代替
	（2）节点的平衡因子为 1，用左边的最大值num_key代替
	（3）节点的平衡因子为 0，随意那边都行



测试数据

set 1 11
set 2 22
set 9 999
set 10 101010
set 11 11111
set 12 12121
set 19 1919
set 17 1717
set 16 1616
set 15 15
set 5 55
set 1 11
set 2 22
set 12 11
set 25 22
set 48 44
set 4 44
set 3 33
set 37 33
set 78 77
set 7 77
set 6 66
set 51 55
set 66 66
set sdfs  dsfs
set sghjg sdfsdsf
set 第 大幅度
set 了 地方看
set 难题 多对多

ceshi

*/


#include <stdio.h>
#include <string.h>
#include <stdlib.h> 
#define MaxSize 100 

typedef struct node *node_pointer;
typedef struct node
{
	int num_key;//////////////////关键字
	int bf;///////////////////////平衡因子
	char key[10];
	char data[20];
	node_pointer left,right;
}node;
int s[50];//左边走为0 ，右边走为1 .
int si=-1;//用于记录在这个节点的下一步
int stop=-1;//更新断点

void set(node_pointer *root);
void insert(node_pointer *root,node_pointer now_node);
void avl(node_pointer* pingheng);
void ll_avl(node_pointer* pingheng);//ll调整
void rr_avl(node_pointer* pingheng);//rr调整
void lr_avl(node_pointer* pingheng);//lr调整
void rl_avl(node_pointer* pingheng);//rl调整
node_pointer get_node(char*key,char *zhi);
int get_key(char *key);
void lxu(node_pointer head);//层序遍历
void changebf(node_pointer *root);//改变bf


void main()
{
	node_pointer root=NULL;
    printf("请输入  set如set key value.   get如get key;  ceshi;    quit退出\n");
	char caozuo[10];
	int sel;
     do{
         scanf("%s",&caozuo);
         if (strcmp(caozuo,"set")==0)
            sel=1;
         else if (strcmp(caozuo,"get")==0)
            sel=2;
        else if (strcmp(caozuo,"look")==0)
            sel=3;
        else if (strcmp(caozuo,"quit")==0)
            sel=0;
        else if (strcmp(caozuo,"ceshi")==0)
            sel=4;
        else sel=-1;

         switch(sel)
        {
          case 0:printf("\t\t\t^-^再见！^-^ \t\t\t\n");system("pause");break;
          case 1:     set(&root);break;
//          case 2:getvalue(&root);printf("\n\n");break;
          case 4:lxu(root);printf("\n\n");break;
          //case 3:look();printf("\n");break;
          default: printf("请输入正确的选项号！");printf("\n\n");break;
        }
    }while(sel!=0);
}

void set(node_pointer *root)
{
  char key[10],zhi[20];
  scanf("%s %s",&key,&zhi);
  node_pointer now_node=get_node(key,zhi);

  insert(root,now_node);
}

void insert(node_pointer *root,node_pointer now_node)//bf的变化失败了，待于改正
{
	si=-1;
	stop=-1;

	if (*root == NULL)//空树时
	      *root=now_node;
	else
	{
		node_pointer dang=*root;//当前
        node_pointer* pre=root;//上一个,指向指针的指针
        node_pointer* pingheng=NULL;//用于判断是否非平衡了
        while(1)
        {
			if( 0 == strcmp(dang->key,now_node->key) )//相同的key
				{
					strcpy(dang->data,now_node->data);
					free(now_node);
					return;//直接返回了，没有失去平衡
				}
			else
			{
				if(now_node->num_key <= dang->num_key  )//小于等于,左走
					{ 

						s[++si]=0;
						if( (dang->bf+1)  == 2)
						{
							stop=si;
							pingheng=pre;//始终为失衡的最低点
						}


						pre=&((*dang).left);//变量的地址
						dang=dang->left;//变量的值
						if(dang==NULL)
							{
								*pre=now_node;
								break;
							}
					}
				else if(now_node->num_key > dang->num_key )//大于，右走
					{
						
						s[++si]=1;
						if((dang->bf-1)  == -2 )
						{
							stop=si;
							pingheng=pre;//始终为失衡的最低点
						}

						pre=&((*dang).right);
						dang=dang->right;
						if(dang==NULL)
							{
								*pre=now_node;
								break;
							}
					}
			}

		}
			//处理平衡
		if (pingheng ==NULL)
		{
			changebf(root);
		}
		else 
		{
			avl(pingheng);
		}
	}
}
void changebf(node_pointer *root)
{
	int i=0;
	node_pointer temp=*root;
	for ( i = 0; i <= si; ++i)
	{
		if (s[i]==0)
		{
			++(temp->bf);
			temp=(temp)->left;
		}
		else if(s[i]==1)
		{
			--(temp->bf);
			temp=(temp)->right;			
		}
	}

}
void avl(node_pointer* pingheng)
{
	node_pointer here=*pingheng;
	if( s[stop]==0 &&  s[stop+1]==0)
	{	ll_avl(pingheng); }
	else if( s[stop]==0 && s[stop+1]==1)
	{	lr_avl(pingheng); }
	else if( s[stop]==1 &&  s[stop+1]==0)
	{	rl_avl(pingheng); }
	else if( s[stop]==1 &&  s[stop+1]==1)
	{	rr_avl(pingheng); }
}

void ll_avl(node_pointer* pingheng)
{
	node_pointer temp = (*pingheng)->left;
	(*pingheng)->left = temp->right;
	temp->right=*pingheng;
	*pingheng=temp;

	temp->bf=0;
	temp->right->bf=0;
}
void lr_avl(node_pointer* pingheng)
{
	node_pointer temp_a=(*pingheng);
	node_pointer temp_b=(*pingheng)->left;
	*pingheng= temp_b->right;

	 temp_a->left=(*pingheng)->right;
	 temp_b->right=(*pingheng)->left;

	(*pingheng)->right=temp_a;
	(*pingheng)->left=temp_b;

	if (stop+1 == si)
	{
		temp_a->bf= 0;
		temp_b->bf= 0;
	}
	else if( s[stop+2]== 0 )
	{
		temp_a->bf= -1;
		temp_b->bf= 0;
	}
	else
	{
		temp_a->bf= 0;
		temp_b->bf= 1;		
	}

	(*pingheng)->bf =0;
}

void rl_avl(node_pointer* pingheng)
{
	node_pointer temp_a=(*pingheng);
	node_pointer temp_b=(*pingheng)->right;
	*pingheng= temp_b->left;

	 temp_a->right=(*pingheng)->left;
	 temp_b->left=(*pingheng)->right;

	(*pingheng)->left=temp_a;
	(*pingheng)->right=temp_b;

	if (stop+1 == si)
	{
		temp_a->bf= 0;
		temp_b->bf= 0;
	}
	else if( s[stop+2]== 0 )
	{
		temp_a->bf= 0;
		temp_b->bf= -1;
	}
	else
	{
		temp_a->bf= 1;
		temp_b->bf= 0;		
	}

	(*pingheng)->bf =0;
}

void rr_avl(node_pointer* pingheng)
{
	node_pointer temp = (*pingheng)->right;
	(*pingheng)->right = temp->left;
	temp->left=*pingheng;
	*pingheng=temp;	

	temp->bf=0;
	temp->left->bf=0;

}

node_pointer get_node(char*key,char *zhi)
{
  node_pointer now_node=(node_pointer)malloc(sizeof(node));
  now_node->num_key=get_key(key);
  strcpy(now_node->key,key);
  strcpy(now_node->data,zhi);
  now_node->bf=0;
  now_node->left=NULL;
  now_node->right=NULL;
  return now_node;
}
int get_key(char *key)
{ 
    int number = 0;    
    while(*key)    
       number+=*key++ ;   
  return number;  
}

void lxu(node_pointer head)  
{  
node_pointer st[MaxSize],p=head;  
  int dui_front=0,dui_rear=0;  
   st[dui_rear++ % MaxSize]=head; 
   printf("平衡因子->num_key->key->value\n"); 
   while(true){  
         p=st[dui_front++ % MaxSize];//调用队头，并且输出  
         printf("%d->%d->%s->%s\n",p->bf,p->num_key,p->key,p->data);  
        if(p->left)st[dui_rear++ % MaxSize]=p->left;//进  
        if(p->right)st[dui_rear++ % MaxSize]=p->right;  
  
        if(dui_front >= dui_rear)break;//返回到了树顶了  
    }  
}  

AVL平衡树