1552.平衡二叉树

本文主要是介绍1552.平衡二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

输入格式
第一行包含整数 N，表示总插入值数量。第二行包含 N 个不同的整数，表示每个插入值。

输出格式
输出得到的 AVL 树的根是多少。

数据范围
1≤N≤20

输入样例1：
5
88 70 61 96 120

输出样例1：
70

输入样例2：
7
88 70 61 96 120 90 65

输出样例2：
88

#include<iostream>
using namespace std;
const int N=30;
int l[N],r[N],v[N],h[N],idx;
int n,root;
int height(int u)
{return h[l[u]]-h[r[u]];
}
void update(int u)
{h[u]=max(h[l[u]],h[r[u]])+1;
}
void R(int &u)
{int p=l[u];l[u]=r[p];r[p]=u;update(u),update(p);u=p;
}
void L(int &u)
{int p=r[u];r[u]=l[p];l[p]=u;update(u),update(p);u=p;
}
void insert(int &u,int w)
{if(!u) u=++idx,v[u]=w;else if(w<v[u]){insert(l[u],w);if(height(u)==2){if(height(l[u])==1) R(u);else L(l[u]),R(u);}}else{insert(r[u],w);if(height(u)==-2){if(height(r[u])==-1) L(u);else R(r[u]),L(u);}}update(u);
}         
int main()
{cin>>n;while(n--){int w;cin>>w;insert(root,w);}cout<<v[root];return 0;
}

这篇关于1552.平衡二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---