替罪羊树学习笔记哦

替罪羊树

替罪羊树 是啥？ 就是一个平衡树，只不过没有旋转操作
那遇到不平衡的咋办呢？ 重构。
怎么重构？先求出不平衡子树的中序遍历（这个中序遍历肯定是有序的递增的）于是就可以分治建树，取中间那个点当根左边的当左子树、右边的当右子树……递归下去
于是就把不平衡的子树变成平衡的子树。
例题：洛谷模板 P3369

几种操作

结构体存的信息:

struct Node
{
   
    int l,r;//左右节点编号
    int val;//当前节点的值
    int flag;//当前节点是否被删除 删除为0 没删除为1
    int size;//size 是这颗子树的大小（包含被删除的节点）
    int fact;//fact是实际的大小（不包含删除的节点）
}node[maxn];

添加节点：二叉搜索树那样添加就好，最后添加完了之后判断是否需要重构。

void ins(int x,int& no)
{
   
    if(!no)
    {
   
        no = newnode(x);
        check(root,no);
        return;
    }
    node[no].fact ++ ;
    node[no].size ++ ;
    if(x < node[no].val)
        ins(x,node[no].l);
    else
        ins(x,node[no].r);
}

删除节点：打上标记就好、在重构的时候完全删去。

void del(int x,int no)
{
   
    if(node[no].flag && node[no].val == x)
    {
   
        node[no].flag = 0;
        node[no].fact -- ;
        check(root,no);
        return;
    }
    node[no].fact--;
    if(x < node[no].val)
        del(x,node[no].l);
    else
        del(x,node[no].r);
}

重构还有一个作用： 完全删去删除点的节点。怎么做到这一点？
重构是把中序遍历的序列分治建树得到的。所以就可以在中序遍历的时候不把已经打上删除标记的点加到序列里去这样就彻底删了。
所以综上重构的条件是 过于不平衡、子树中删除的节点过多
pd函数是判断是否需要重构；

bool pd(int no)
{
   
    return max(node[node[no].l].size, node[node[no].r].size) > phyz * node[no].size ||
           node[no].size - node[no].fact > node[no].size * 0.3;
}

上面删除、添加里的check函数就是判断是否需要重构的函数了。
判断是否需要重构的时候应从根节点开始往下递归直到遇到不平衡子树或当前加的或删的这个节点为止。

void check(int& no,int end)
{
   
    if(no == end)
        return;
    if(pd(no))
    {
   
        rebuild(no);
        update(root,no);
        return;
    }
    if(node[end].val < node[no].val)
    {
   
        check(node[no].l,end);
    }
    else
        check(node[no].r,end);
}

update函数是用来更新重构子树 以上 的节点信息的（因为彻底删除了要删除的节点，所以size大小变化了，但是fact、实际的大小并没有变化；所以只用更新size的大小）。

void update(int no,int end)
{
   
    if(!no)
        return;
    if(node[end].val < node[no].val)
        update(node[no].l,end);
    else
        update(node[no].r,end);
    node[no].size = node[node[no].l].size + node[node[no].r].size + 1;
}

rebuild函数就是重新构建这个子树了。
用到一个vector来存他的中序遍历的序列。
fenzhi函数用来分支建树
zxbl？？真香便利？hhhhhhhhh

vector<int> vv;
void zxbl(int no)
{
   
    if(!no)
        return;
    zxbl(node[no].l);
    if(node[no].flag)
        vv.push_back(no);
    zxbl(node[no].r);
}
void fenzhi(int l,int r,int& no)
{
   
    if(l == r)
    {
   
        no = vv[l];
        node[no].size = node[no].fact = 1;
        node[no].l = node[no].r = 0;
        return;
    }
    int mid = l + r >> 1;
    while(mid > l && node[vv[mid]].val == node[vv[mid - 1]].val)
        mid--;
    no = vv[mid];
    if(l < mid)
        fenzhi(l,mid - 1,node[no].l);
    else
        node[no].l = 0;
    fenzhi(mid + 1,r,node[no].r);
    node[no].size = node[node[no].l].size + node[node[no].r].size + 1;
    node[no].fact = node[node[no].l].fact + node[node[no].r].fact + 1;
}

void rebuild(int& no)
{
   
    vv.clear();
    zxbl(no);
    if(vv.empty())
    {
   
        no = 0;
        return;
    }
    fenzhi(0,vv.size() - 1,no);
}

插入一点细节

可以看到在fenzhi函数里面找到中间的那个数以后还要往左找，为什么？
我们把相等的值默认放在了右子树上，所以重构的时候也得注意一下，如果有几个连续的相等的数字，就一定要找一个最左端的当根，这就是这个while的意义。
这个时候想到，如果题目样例给出一串相等的数字卡你这个树，岂不是凉了？
还有几个操作：

得到第x大的数字
为什么用while写？ 因为我学的时候的那个大佬就是用while写的hhhh
这个有点权值线段树找第k大的意思？

int getnum(int x)
{
   
    int no = root;
    while(no)
    {
   
        if(node[no].flag && node[node[no].l].fact + 1 == x )
            break;
        else if(node[node[no].l].fact >= x)
            no = node[no].l;
        else
        {
   
            x -= node[node[no].l].fact + node[no].flag;
            no = node[no].r;
        }
    }
    return node[no].val;
}

得到x的排名

int getrank(int x)
{
   
    int ans = 1;
    int no = root;
// printf("%d\n",no);
    while(no)
    {
   
        if(node[no].val >= x)
            no = node[no].l;
        else
        {
   
            ans += node[node[no].l].fact + node[no].flag;
            no = node[no].r;
        }
    }
// printf("%d\n",ans);
    return ans;
}

就是这了。。。代码很长；但是要有耐心。

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5+5;
//3369
const double phyz = 0.75;
struct Node
{
   
    int l,r;//左右节点编号
    int val;//当前节点的值
    int flag;//当前节点是否被删除 删除为0 没删除为1
    int size;//size 是这颗子树的大小（包含被删除的节点）
    int fact;//fact是实际的大小（不包含删除的节点）
}node[maxn];
int cnt;
int root;
int newnode(int val)
{
   
    ++cnt;
    node[cnt].val = val;
    node[cnt].l = 0;
    node[cnt].r = 0;
    node[cnt].flag = 1;
    node[cnt].size = node[cnt].fact = 1;
    return cnt;
}
vector<int> vv;
void zxbl(int no)
{
   
    if(!no)
        return;
    zxbl(node[no].l);
    if(node[no].flag)
        vv.push_back(no);
    zxbl(node[no].r);
}
void fenzhi(int l,int r,int& no)
{
   
    if(l == r)
    {
   
        no = vv[l];
        node[no].size = node[no].fact = 1;
        node[no].l = node[no].r = 0;
        return;
    }
    int mid = l + r >> 1;
    while(mid > l && node[vv[mid]].val == node[vv[mid - 1]].val)
        mid--;
    no = vv[mid];
    if(l < mid)
        fenzhi(l,mid - 1,node[no].l);
    else
        node[no].l = 0;
    fenzhi(mid + 1,r,node[no].r);
    node[no].size = node[node[no].l].size + node[node[no].r].size + 1;
    node[no].fact = node[node[no].l].fact + node[node[no].r].fact + 1;
}

void rebuild(int& no)
{
   
    vv.clear();
    zxbl(no);
    if(vv.empty())
    {
   
        no = 0;
        return;
    }
    fenzhi(0,vv.size() - 1,no);
}
void update(int no,int end)
{
   
    if(!no)
        return;
    if(node[end].val < node[no].val)
        update(node[no].l,end);
    else
        update(node[no].r,end);
    node[no].size = node[node[no].l].size + node[node[no].r].size + 1;
}

bool pd(int no)
{
   
    return max(node[node[no].l].size, node[node[no].r].size) > phyz * node[no].size ||
           node[no].size - node[no].fact > node[no].size * 0.3;
}
void check(int& no,int end)
{
   
    if(no == end)
        return;
    if(pd(no))
    {
   
        rebuild(no);
        update(root,no);
        return;
    }
    if(node[end].val < node[no].val)
    {
   
        check(node[no].l,end);
    }
    else
        check(node[no].r,end);
}


void ins(int x,int& no)
{
   
    if(!no)
    {
   
        no = newnode(x);
        check(root,no);
        return;
    }
    node[no].fact ++ ;
    node[no].size ++ ;
    if(x < node[no].val)
        ins(x,node[no].l);
    else
        ins(x,node[no].r);
}

void del(int x,int no)
{
   
    if(node[no].flag && node[no].val == x)
    {
   
        node[no].flag = 0;
        node[no].fact -- ;
        check(root,no);
        return;
    }
    node[no].fact--;
    if(x < node[no].val)
        del(x,node[no].l);
    else
        del(x,node[no].r);
}

int getnum(int x)
{
   
    int no = root;
    while(no)
    {
   
        if(node[no].flag && node[node[no].l].fact + 1 == x )
            break;
        else if(node[node[no].l].fact >= x)
            no = node[no].l;
        else
        {
   
            x -= node[node[no].l].fact + node[no].flag;
            no = node[no].r;
        }
    }
    return node[no].val;
}

int getrank(int x)
{
   
    int ans = 1;
    int no = root;
// printf("%d\n",no);
    while(no)
    {
   
        if(node[no].val >= x)
            no = node[no].l;
        else
        {
   
            ans += node[node[no].l].fact + node[no].flag;
            no = node[no].r;
        }
    }
// printf("%d\n",ans);
    return ans;
}

int main()
{
   
    root = 0;
    cnt = 0;
    int n;
    scanf("%d",&n);
    while( n -- )
    {
   
        int f,x;
        scanf("%d%d",&f,&x);
        if(f == 1)
            ins(x,root);
        else if(f == 2)
            del(x,root);
        else if(f == 3)
            printf("%d\n",getrank(x));
        else if(f == 4)
            printf("%d\n",getnum(x));
        else if(f == 5)
            printf("%d\n",getnum(getrank(x) - 1));
        else if(f == 6)
            printf("%d\n",getnum(getrank(x + 1)));
    }
// vv.clear();
// zxbl(root);
// for (int i = 0; i < vv.size(); i++ )
// {
   
// printf("%d ",node[vv[i]].val);
// }
}

希望学完了，不要忘吧 hhhhhhhhh wtcl