链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805404939173888

AVL树与它的旋转操作

这个$AVL$AVL树呢，它是要求每个点的左右儿子的深度差不超过$1$1
每次插入一个结点，仅可能影响这个结点到根路径上的结点的平衡
情况（一）插入点在左子树的左子树(或右子树的右子树)

那么我可以把红色点转上去

这样就平衡了
情况（二）插入点在左子树的右子树（或右子树的左子树）

如果我直接右旋的话就凉了，效果如下：

会发现转完了之后还是不平衡
这主要是由于绿色结点的深度比较大
正确的操作是这样的：

第一步操作的目的就在于让黄色节点的左儿子的右儿子的深度减少1，这样就可以转化为情形（一），进而再进行一次右旋就可以让高度变低了

代码

#include <bits/stdc++.h>
#define maxn 100010
#define cl(x) memset(x,0,sizeof(x))
#define ll long long
using namespace std;
struct AVL
{
	AVL *ch[2], *f;
	ll w, h;
}*RT, nul, pool[maxn];
ll ndtot;
ll read(ll x=0)
{
	ll c, f=1;
	for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return f*x;
}
void link(AVL *son, AVL* fa, ll flag)
{
	son->f=fa;
	fa->ch[flag]=son;
}
bool wh(AVL *son, AVL* fa)
{
	return fa->ch[1]==son;
}
void update(AVL *p)
{
	while(p!=RT)
		p->h = max(p->ch[0]->h,p->ch[1]->h)+1,
		p = p->f;
}
void rotate(AVL *y, ll flag)
{
	AVL *z=y->f, *x=y->ch[flag];
	link(x,z,wh(y,z));
	link(x->ch[!flag],y,flag);
	link(y,x,!flag);
	update(y);
}
void insert(AVL *p, AVL *nd)
{
	ll x = nd->w>=p->w, t;
	if(p->ch[x]==&nul)
	{
		link(nd,p,x);
	}
	else insert(p->ch[x],nd);
	if(abs(p->ch[0]->h - p->ch[1]->h)>1)
	{
		t = nd->w>=p->ch[x]->w;
		if(x!=t)rotate(p->ch[x],t);
		rotate(p,x);
	}
	update(p);
}
void debug(AVL *p)
{
	if(p->ch[0]!=&nul)debug(p->ch[0]);
	if(p->ch[1]!=&nul)debug(p->ch[1]);
}
int main()
{
	ll N=read(), x;
	AVL *p;
	
	nul.ch[0]=nul.ch[1]=&nul;
	nul.h=0;
	
	RT = pool+ ++ndtot;
	
	while(N--)
	{
		x = read();
		p = pool+ ++ndtot;
		p->w=x, p->h=1;
		p->f = p->ch[0] = p->ch[1] = &nul;
		
		if(RT->ch[0]==0)link(p,RT,0);
		else
		{
			insert(RT->ch[0],p);
		}
	}
	printf("%lld",RT->ch[0]->w);
	return 0;
}