PAT Advanced 1066

5
88 70 61 96 120

70

7
88 70 61 96 120 90 65

88

//有关二叉平衡树相关知识就不在这里多说了
//网上有很多
#include<stdio.h>
#include<stdlib.h>
#define FALSE 0
#define TRUE 1
#define EH 0
#define LH 1
#define RH -1
#define N 20
typedef int BOOL ;


typedef struct AVL_Node
{
	struct AVL_Node * left;
	struct AVL_Node * right;
	int bf;
	int data;


}AVL_Node,*AVL_Tree;
/* 右旋转 */
void R_Rotate(AVL_Tree * root)
{
	AVL_Tree temp=(*root)->left;
	(*root)->left=temp->right;
	temp->right=*root;
	*root=temp;
}
/* 左旋转 */
void L_Rotate(AVL_Tree * root)
{
	AVL_Tree temp=(*root)->right;
	(*root)->right=temp->left;
	temp->left=*root;
	*root=temp;
}


void LeftBalance(AVL_Tree * root)
{
	AVL_Tree left,right;
	left=(*root)->left;
	/* 平衡因子 */
	switch(left->bf)
	{
	case LH://新节点插入在左子树的左子树
		left->bf=(*root)->bf=EH;
		R_Rotate(root);
		break;
	case RH://新节点插入字左子树的右子树
		right=left->right;
		switch(right->bf)
		{
		case LH:
			(*root)->bf=RH;
			left->bf=EH;
			break;
		case EH:
			(*root)->bf=EH;
			left->bf=EH;
			break;
		case RH:
			(*root)->bf=EH;
			left->bf=LH;
			break;
		}
		//这里要注意的是在左子树的右子树进行调整后右子树会变成平衡
		right->bf = EH;
		//LR调整
		L_Rotate(&(*root)->left);
		R_Rotate(root);
		break;
	}
}


void RightBalance(AVL_Tree * root)
{
	AVL_Tree left,right;
	right=(*root)->right;


	switch(right->bf)
	{
	case RH://新节点插入在右子树的右子树上
		(*root)->bf=right->bf=EH;
		L_Rotate(root);
		break;
	case LH://新节点插入在右子树的左子树上
		left=right->left;
		switch(left->bf)
		{
		case EH:
			(*root)->bf=right->bf=EH;
			break;
		case LH:
			(*root)->bf=EH;
			right->bf=RH;
			break;
		case RH:
			(*root)->bf=LH;
			right->bf=EH;
			break;
		}
		//这里要注意的是在右子树的左子树进行调整后左子树会变成平衡
		left->bf=EH;
		//RL调整
		R_Rotate(&(*root)->right);
		L_Rotate(root);
		break;
	}
}


//插入节点
int InsertAVL(AVL_Tree * root,int data,BOOL * flag)
{
	if((*root)==NULL)
	{
		(*root)=(AVL_Tree)malloc(sizeof(AVL_Node));
		(*root)->data=data;
		(*root)->left=(*root)->right=NULL;
		(*root)->bf=EH;
		*flag=TRUE;
	}
	else if((*root)->data==data)//相同的节点就忽略
	{
		*flag=FALSE;
		return 0;
	}
	else if(data<(*root)->data)//插入到左子树上
	{
		if(!InsertAVL(&(*root)->left,data,flag))
			return 0;
		if((*flag)==1)//调整需要继续进行
		{
			switch((*root)->bf)
			{
			case LH:
				LeftBalance(&(*root));//在左子树高的情况下插入后需要进行左平衡
				*flag=FALSE;
				break;
			case EH://原来是平衡的话，就表明插入后左子树高
				*flag=TRUE;
				(*root)->bf=LH;
				break;
			case RH://原来是右子树高的情况下，插入后左右子树高度相等
				*flag=FALSE;
				(*root)->bf=EH;
				break;
			}
		}
	}
	else
	{//同理如上
		if(!InsertAVL(&(*root)->right,data,flag))
			return 0;
		if((*flag)==1)
		{
			switch((*root)->bf)
			{
			case LH:
				(*root)->bf=EH;
				*flag=FALSE;
				break;
			case EH:
				*flag=TRUE;
				(*root)->bf=RH;
				break;
			case RH:
				RightBalance(&(*root));
				*flag=FALSE;
				break;
			}
		}
	}
	return 1;
}
int a[N];
int main()
{
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	AVL_Tree t=NULL;
	//用来标注调整过程的结束
	BOOL flag;
	for(i=0;i<n;i++)
		InsertAVL(&t,a[i],&flag);
	printf("%d\n",t->data);


	return 0;
}