题意:

输入一个正整数N(<=20),接着输入N个结点的值,依次插入一颗AVL树,输出最终根结点的值。

AAAAAccepted code:

 #define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[];
typedef struct node{
int val;
node*left,*right;
};
node*left_rotate(node*root){
node*tamp=root->right;
root->right=tamp->left;
tamp->left=root;
return tamp;
}
node*right_rotate(node*root){
node*tamp=root->left;
root->left=tamp->right;
tamp->right=root;
return tamp;
}
node*left_right(node*root){
root->left=left_rotate(root->left);
return right_rotate(root);
}
node*right_left(node*root){
root->right=right_rotate(root->right);
return left_rotate(root);
}
int get_height(node*root){
if(root==NULL)
return ;
return max(get_height(root->left),get_height(root->right))+;
}
node*inser(node*root,int val){
if(root==NULL){
root=new node();
root->val=val;
root->left=root->right=NULL;
}
else if(val<root->val){
root->left=inser(root->left,val);
if(get_height(root->left)-get_height(root->right)==)
root=val<root->left->val?right_rotate(root):left_right(root);
}
else{
root->right=inser(root->right,val);
if(get_height(root->right)-get_height(root->left)==)
root=val>root->right->val?left_rotate(root):right_left(root);
}
return root;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=;i<=n;++i)
cin>>a[i];
node*ans=NULL;
for(int i=;i<=n;++i)
ans=inser(ans,a[i]);
cout<<ans->val;
return ;
}
05-06 01:00