手写了个AVL树，目前没有调出来什么问题，明天改改拿去过平衡树模板吧
模板过了有时间写一个avl树总结吧
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int tot,root;
bool flag;
int n,m;
struct node{
int ch[2],fa;
int h,bal,size;//树高，平衡因子，子树大小
int val;
}bst[N];
int newnode(int val,int fa){
bst[++tot].val=val;bst[tot].fa=fa;
bst[tot].h=1;bst[tot].bal=0; bst[tot].size=1;
return tot;
}
int search_bst(int p,int val){
if(p==0) return 0;
if(bst[p].val==val){
//cout<<"high: "<<bst[p].h<<endl;
//cout<<"size: "<<bst[p].size<<endl;
//cout<<"balance: "<<bst[p].bal<<endl;
return p;
}
else if(val<bst[p].val) return search_bst(bst[p].ch[0],val);
else return search_bst(bst[p].ch[1],val);
}
int getfa(int p){//判断是父亲的哪一个儿子
return bst[bst[p].fa].ch[0]==p?0:1;
}
void update(int p){//更新节点
bst[p].h=max(bst[bst[p].ch[0]].h,bst[bst[p].ch[1]].h)+1;//更新树高
bst[p].bal=bst[bst[p].ch[0]].h-bst[bst[p].ch[1]].h;//更新平衡因子
bst[p].size=bst[bst[p].ch[0]].size+bst[bst[p].ch[1]].size+1;//更新子树大小
}
void rotate(int x){//以x为支点旋转他的父亲节点
int s,y,z;
y=bst[x].fa;s=getfa(x);z=bst[x].ch[s^1];//要旋转的节点和可能发生冲突的节点
//cout<<bst[x].val<<" "<<bst[y].val<<" "<<bst[z].val<<endl;
if(y==root) root=x;
else {bst[bst[y].fa].ch[getfa(y)]=x;bst[x].fa=bst[y].fa;}
bst[y].ch[s]=z;bst[x].ch[s^1]=y;
bst[y].fa=x;bst[z].fa=y;
update(y);update(x);
}
void check(int p){//是否发生失衡
if(abs(bst[p].bal)>1){
//cout<<"No Balance "<<bst[p].val<<endl;
if(bst[p].bal==2&&bst[bst[p].ch[0]].bal==1){//LL
//cout<<"Yes: "<<bst[p].val<<endl;
//cout<<"LL"<<endl;
rotate(bst[p].ch[0]);
}
else if(bst[p].bal==-2&&bst[bst[p].ch[1]].bal==-1){//RR
//cout<<"RR"<<endl;
rotate(bst[p].ch[1]);
}
else if(bst[p].bal==2&&bst[bst[p].ch[0]].bal==-1){//LR
//cout<<"LR"<<endl;
rotate(bst[bst[p].ch[0]].ch[1]);
rotate(bst[p].ch[0]);
}
else{//RL
//cout<<"RL"<<endl;
rotate(bst[bst[p].ch[1]].ch[0]);
rotate(bst[p].ch[1]);
}
}
}
void insert_bst(int &p,int fa,int val){
if(p==0){
p=newnode(val,fa);//p是引用
if(root==0) root=p;
return;
}
if(bst[p].val==val) return;
else if(val<bst[p].val) insert_bst(bst[p].ch[0],p,val);
else insert_bst(bst[p].ch[1],p,val);
update(p);
check(p);
}
void delete_bst(int &p,int val){
if(p==0) return;
if(bst[p].val==val){
//cout<<"Del"<<endl;
if(p==root) flag=1;
if(bst[p].ch[0]==0&&bst[p].ch[1]==0) p=0;
else if(bst[p].ch[0]==0) p=bst[p].ch[1];
else if(bst[p].ch[1]==0) p=bst[p].ch[0];
else{//有左右子树
int x=bst[p].ch[0];
while(bst[x].ch[1]){//找到左子树最大
x=bst[x].ch[1];
}
bst[p].val=bst[x].val;
if(flag) {root=p;flag=0;}
//cout<<"root:"<<bst[root].val<<endl;
delete_bst(bst[p].ch[0],bst[x].val);
}
if(flag) {root=p;flag=0;}
return ;
}
else if(val<bst[p].val) delete_bst(bst[p].ch[0],val);
else delete_bst(bst[p].ch[1],val);
update(p);
check(p);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
insert_bst(root,root,x);
}
while(m--){
int op,y;
cin>>op;
if(op==1){//搜索
cin>>y;
if(search_bst(root,y)) {
cout<<"Yes"<<endl;
}
else cout<<"No"<<endl;
}
else if(op==2){//插入
cin>>y;
insert_bst(root,root,y);
}
else if(op==3){//删除
cin>>y;
delete_bst(root,y);
}
}
system("pause");
}