平衡二叉树-替罪羊树 c/c++代码实现

参考：https://www.bilibili.com/video/BV1Wt411L7te?t=1822大佬视频
需要重构的条件是:当前结点的左子树或右子树的大小大于当前结点的大小乘一个平衡因子alpha或者以当前节点为根的子树内被删除的结点数量大于树大小的30%了
代码中有比较详细的注释

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
struct Node{
    int l,r,val;
    int size,fact;
    bool exist;
}node[maxn];
int root,cnt;
vector<int> v;
void creat(int &now,int val){   //创建一个新结点
    now=++cnt;
    node[now].val=val;  //值等于val
    node[now].size=node[now].fact=1;    //实际结点大小=节点大小
    node[now].exist=true; //结点是否存在
}
/*需要重构的条件是:当前结点的左子树或右子树的大小大于当前结点的大小乘一个平衡因子alpha或者以当前节点为根的子树内被删除的结点数量大于树大小的30%了*/
bool imbalence(int now){   //判断是否需要重构
    if((max(node[node[now].l].size,node[node[now].r].size)>node[now].size*0.75)
       ||(node[now].size-node[now].fact>node[now].size*0.3))
        return true;
    return false;
}
void ldr(int now){   //中序遍历暴力重构
    if(!now) return;
    ldr(node[now].l);
    if(node[now].exist) v.push_back(now);
    ldr(node[now].r);
}
void lift(int l,int r,int &now){   //将中序遍历的vector进行重构（分治的方法完成）
    if(l==r){    //分治到只有一个结点
        now=v[l];
        node[now].l=node[now].r=0;
        node[now].size=node[now].fact=1;
        return;
    }
    int mid=(l+r)/2; //取最中间的结点（为了让生成的树尽量平衡）
    while (l<mid&&node[v[mid]].val==node[v[mid-1]].val) mid--;   //这里比较重要
    now=v[mid];   /* 我们平衡二叉树的定义是，如果一个数大于或等于当前节点，我们要把它往右边放置，所以如果中间左边的结点跟我们中间取得结点相同，那我们就应该取左边的那个结点作为根节点*/
    if(l<mid) lift(l,mid-1,node[now].l);
    else node[now].l=0;
    lift(mid+1,r,node[now].r);
    node[now].size=node[node[now].l].size+node[node[now].r].size+1;  //回溯方法更新结点的实际大小和大小
    node[now].fact=node[node[now].l].fact+node[node[now].r].fact+1;
}

void rebuild(int &now){   //重构函数
    v.clear();
    ldr(now);
    if(v.empty()){
        now=0;
        return;
    }
    lift(0,v.size()-1,now);
}

void update(int now,int end){   //更新结点
    if(!now) return;
    if(node[end].val<node[now].val) update(node[now].l,end);
    else update(node[now].r,end);
    node[now].size=node[node[now].l].size+node[node[now].r].size+1;
}

void check(int &now,int end){  //检查树是否符合条件
    if(now==end) return;
    if(imbalence(now)){
        rebuild(now);
        update(root,now);
        return;
    }
    if(node[end].val<node[now].val) check(node[now].l,end);
    else check(node[now].r,end);
}

void insert(int &now,int val){  //插入一个数
    if(!now){
        creat(now,val);  //插入后判断是否符合标准
        check(root,now);
        return;
    }
    node[now].size++;  //回溯更新结点大小和实际大小
    node[now].fact++;
    if(val<node[now].val)  insert(node[now].l,val);
    else  insert(node[now].r,val);
}
void del(int now,int val){   //删除结点，首先要判断结点是否存在，不存在就没有删除的必要了
    if(node[now].exist&&val==node[now].val){
        node[now].exist=false;
        node[now].fact--;
        check(root,now);
        return;
    }
    node[now].fact--;
    if(val<node[now].val) del(node[now].l,val);
    else del(node[now].r,val);
}
int get_rank(int val){   //得到名次
    int now=root,rank=1;  //名次等于所有比他小的数+1，也就是说如果有多个相同的数，排名是第一个数的名次
    while (now){
        if(val<=node[now].val) now=node[now].l;  //如果当前值比节点值小，往左递归
        else{
            rank+=node[now].exist+node[node[now].l].fact;  //如果大于当前结点，就需要加上比他小的结点在加上这个根节点（如果根节点存在的话）
            now=node[now].r;  //往右子树寻找
        }
    }
    return rank;
}
int get_num(int rank){    //给定排名求字母
    int now=root;
    while (now){
        if(node[now].exist&&node[node[now].l].fact+node[now].exist==rank) break;  //如果找到排名，直接返回排名
        else if(node[node[now].l].fact>=rank) now=node[now].l; //没找到就继续向下寻找
        else{
            rank-=node[node[now].l].fact+node[now].exist;  //如果往右子树找，相当于这个数比左边的数都打，所以排名要减去左边的大小
            now=node[now].r;
        }
    }
    return node[now].val;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int ch,x;
        scanf("%d%d",&ch,&x);
        if(ch==1) insert(root,x);
        if(ch==2) del(root,x);
        if(ch==3) printf("%d\n",get_rank(x));
        if(ch==4) printf("%d\n",get_num(x));
        if(ch==5) printf("%d\n",get_num(get_rank(x)-1));
        if(ch==6) printf("%d\n",get_num(get_rank(x+1)));
//        v.clear();
//        ldr(root);
//        for(auto it : v) printf("%d ",node[it].val);
//        cout<<endl;
    }
    return 0;
}