PAT Advanced 1066
1066. Root of AVL Tree (25)
时间限制100 ms
内存限制32000 kB 代码长度限制16000 B 判题程序 Standard
作者
CHEN, Yue
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print ythe root of the resulting AVL tree in one line.
Sample Input 1:
5
88 70 61 96 120Sample Output 1:
70Sample Input 2:
7
88 70 61 96 120 90 65Sample Output 2:
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;
}