P3369 【模板】普通平衡树
方法一:
//avl数组版
#include
using namespace std;
const int maxn=100010;
struct avlnode{
int val;
int size;
int cnt;
int height;
int ls;
int rs;
}avl[maxn];
int root,tot;
int height(int rt)
{
return avl[rt].height;
}
void pushup(int rt)
{
avl[rt].size=avl[avl[rt].ls].size+avl[avl[rt].rs].size+avl[rt].cnt;
}
void LeftRotation(int &rt)
{
int k;
k=avl[rt].rs;
avl[rt].rs=avl[k].ls;
avl[k].ls=rt;
avl[rt].height=max(height(avl[rt].ls),height(avl[rt].rs))+1;
pushup(rt);
avl[k].height=max(height(avl[k].ls),height(avl[k].rs))+1;
pushup(k);
rt=k;
}
void RightRotation(int &rt)
{
int k;
k=avl[rt].ls;
avl[rt].ls=avl[k].rs;
avl[k].rs=rt;
avl[rt].height=max(height(avl[rt].ls),height(avl[rt].rs))+1;
pushup(rt);
avl[k].height=max(height(avl[k].ls),height(avl[k].rs))+1;
pushup(k);
rt=k;
}
int Newavl(int v)
{
tot++;
avl[tot].val=v;
avl[tot].ls=avl[tot].rs=0;
avl[tot].cnt=avl[tot].size=1;
avl[tot].height=0;
return tot;
}
void preorder(int rt)
{
if (rt!=0)
{
cout<