【PAT甲级】1066 Root of AVL Tree (25 分)(AVL树建树模板)
2024-09-01 22:40:25
题意:
输入一个正整数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 ;
}
最新文章
- EF6 CodeFirst+Repository+Ninject+MVC4+EasyUI实践(九)
- Macaca-iOS入门那些事
- [转]ASP.Net篇之Session与Cookie
- JAVA集合小结
- 树莓派 安装 php
- Java基础知识强化之IO流笔记58:内存操作流
- java_method_正则校验
- 深入浅出理解python 装饰器
- Java中线程的同步问题
- Luogu P3254 圆桌问题
- MyBatis - 4.动态SQL
- CSRF理解和实战
- UML和模式应用4:初始阶段(4)--需求制品之用例模型模板示例
- Ubuntu下好的PDF阅读器介绍
- HEOI2018(九省联考) 题解集合
- Little-endian和Big-endian
- jQuery 的attr()方法
- Thymeleaf使用说明
- Marshal.FreeHGlobal 方法 (IntPtr)
- 【转】WinForm窗体显示和窗体间传值