【PAT甲级】1066 Root of AVL Tree (25 分)（AVL树建树模板）

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int a[27];
 5 typedef struct node{
 6     int val;
 7     node*left,*right;
 8 };
 9 node*left_rotate(node*root){
10     node*tamp=root->right;
11     root->right=tamp->left;
12     tamp->left=root;
13     return tamp;
14 }
15 node*right_rotate(node*root){
16     node*tamp=root->left;
17     root->left=tamp->right;
18     tamp->right=root;
19     return tamp;
20 }
21 node*left_right(node*root){
22     root->left=left_rotate(root->left);
23     return right_rotate(root);
24 }
25 node*right_left(node*root){
26     root->right=right_rotate(root->right);
27     return left_rotate(root);
28 }
29 int get_height(node*root){
30     if(root==NULL)
31         return 0;
32     return max(get_height(root->left),get_height(root->right))+1;
33 }
34 node*inser(node*root,int val){
35     if(root==NULL){
36         root=new node();
37         root->val=val;
38         root->left=root->right=NULL;
39     }
40     else if(val<root->val){
41         root->left=inser(root->left,val);
42         if(get_height(root->left)-get_height(root->right)==2)
43             root=val<root->left->val?right_rotate(root):left_right(root);
44     }
45     else{
46         root->right=inser(root->right,val);
47         if(get_height(root->right)-get_height(root->left)==2)
48             root=val>root->right->val?left_rotate(root):right_left(root);
49     }
50     return root;
51 }
52 int main(){
53     ios::sync_with_stdio(false);
54     cin.tie(NULL);
55     cout.tie(NULL);
56     int n;
57     cin>>n;
58     for(int i=1;i<=n;++i)
59         cin>>a[i];
60     node*ans=NULL;
61     for(int i=1;i<=n;++i)
62         ans=inser(ans,a[i]);
63     cout<<ans->val;
64     return 0;
65 }