时间限制 100 ms 内存限制 65536 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.
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
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 120 Sample Output 1: 70 Sample Input 2: 7 88 70 61 96 120 90 65 Sample Output 2: 88
#include<cstdio> #include<algorithm> using namespace std; struct node{ int v,height; node *lchild,*rchild; }*root; //创建结点 node* newNode(int v){ node* Node=new node; Node->v=v; Node->height=1; Node->lchild=Node->rchild=NULL; return Node; } //获取结点高度 int getHeight(node* root){ if(root==NULL)return 0; return root->height; } //跟新结点高度 void updateHeight(node* root){ root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1; } int getBalenceFactor(node* root){ return getHeight(root->lchild)-getHeight(root->rchild); } //左旋 void L(node* &root){ node* temp=root->rchild; root->rchild=temp->lchild; temp->lchild=root; updateHeight(root); updateHeight(temp); root=temp; } //右旋 void R(node* &root){ node* temp=root->lchild; root->lchild=temp->rchild; temp->rchild=root; updateHeight(root); updateHeight(temp); root=temp; } void insert(node* &root,int v){ if(root==NULL){//到达空结点 root=newNode(v); return; } if(v<root->v){//v比根结点权值小 insert(root->lchild,v); updateHeight(root); if(getBalenceFactor(root)==2){ if(getBalenceFactor(root->lchild)==1){//LL型 R(root); }else if(getBalenceFactor(root->lchild)==-1){//LR型 L(root->lchild); R(root); } } }else{ insert(root->rchild,v); updateHeight(root); if(getBalenceFactor(root)==-2){ if(getBalenceFactor(root->rchild)==-1){//RR型 L(root); }else if(getBalenceFactor(root->rchild)==1){//RL型 R(root->rchild); L(root); } } } } int main(){ int n,v; scanf("%d",&n); root=NULL; for(int i=0;i<n;i++){ scanf("%d",&v); insert(root,v); } printf("%d\n",root->v); return 0; }