PAT甲级1066.

目录

A1066

题目

样例

样例1

输入:

5
88 70 61 96 120

输出:

70

样例2

输入:

7
88 70 61 96 120 90 65

输出:

88

思路和坑点

　　AVL树的建树，直接使用AVL树的模板即可，一定要会写AVL树的调整函数。
　　AVL树的总结可以参加之前的博文树与二叉树的总结中关于AVL树部分的总结。
　　注意：根据题目要求调整插入的方法。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{                        //结点的定义和初始化 
    int data;
    int high=1;                             //高度初始化 
    struct node *left=NULL,*right=NULL;     //左右孩子初始化为空 
}Node;
int gethigh(Node *root){                    //获取树的高度 
    if(root==NULL) return 0;
    else return root->high;
} 
int getbf(Node *root){                      //获取结点的平衡因子 
    return gethigh(root->left)-gethigh(root->right);
}
void updatahigh(Node *root){                //更新结点的平衡因子 
    root->high=max(gethigh(root->left),gethigh(root->right))+1;
}
void L(Node *&root){                        //左旋 
    Node *temp=root->right;
    root->right=temp->left;
    temp->left=root;
    updatahigh(root);
    updatahigh(temp);
    root=temp;
}
void R(Node *&root){                        //右旋 
    Node *temp=root->left;
    root->left=temp->right;
    temp->right=root;
    updatahigh(root);
    updatahigh(temp);
    root=temp;
}
void Insert(Node *&root,int x){             //插入 
    if(root==NULL){
        root=new Node;
        root->data=x;
        return;
    }
    if(x<root->data){
        Insert(root->left,x);
        updatahigh(root);
        if(getbf(root)==2){
            if(getbf(root->left)==1)
                R(root);
            else if(getbf(root->left)==-1){
                L(root->left);
                R(root);
            }
        }
    }
    else{
        Insert(root->right,x);
        updatahigh(root);
        if(getbf(root)==-2){
            if(getbf(root->right)==-1)
                L(root);
            else if(getbf(root->right)==1){
                R(root->right);
                L(root);
            }
        }
    }
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    Node *root=NULL;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        Insert(root,temp);
    }
    cout<<root->data;
    return 0;
}