1066 Root of AVL Tree（51行代码+超详细注释）

分数 25

全屏浏览题目

切换布局

作者 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 the root of the resulting AVL tree in one line.

Sample Input 1:

5
88 70 61 96 120

Sample Output 1:

Sample Input 2:

7
88 70 61 96 120 90 65

Sample Output 2:

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n;
int l[N],r[N],h[N],v[N],idx,root;//分别为左子树，右子树，高度，结点权值，当前结点，根结点
void updata(int u){//更新结点u的高度
   h[u]=max(h[l[u]],h[r[u]])+1;
}
int R(int &root){//右旋
   int t=l[root];
   l[root]=r[t],r[t]=root;;
   updata(root),updata(t);
   root=t;
}
int L(int &root){//左旋
   int t=r[root];
   r[root]=l[t],l[t]=root;
   updata(root),updata(t);
   root=t;
}
int balance_alpha(int u){//左右子树的高度差
   return h[l[u]]-h[r[u]];
}
void insert(int &u,int x){//插入
   if(!u)u=++idx,v[u]=x;//如果结点为空，则将x的插入该节点
   else if(x<v[u]){//如果插入结点的值小于当前结点
       insert(l[u],x);//往左子树插入
       if(balance_alpha(u)==2){//插完后若u结点的平衡因子为2
           if(balance_alpha(l[u])==1)R(u);//若此时左子树的平衡因子为1则右旋u结点
           else L(l[u]),R(u);//否则则先左旋左孩子后右旋u结点
       }
   }
   else if(x>=v[u]){//参照上面
       insert(r[u],x);
       if(balance_alpha(u)==-2){
           if(balance_alpha(r[u])==-1)L(u);
           else R(r[u]),L(u);
       }
   }
   updata(u);//插完之后更新u结点高度
}
int main(){
   cin>>n;
   while(n--){//输入
       int x;
       cin>>x;
       insert(root,x);//插入x
   }
   cout<<v[root]<<endl;//输出根结点的值
   return 0;
}