ScapeGoatTree 详解

知识点概要

在各种二叉平衡树中，大多数的平衡树都是通过旋转来维护这棵二叉查找树的性质，并且尽量保证每次的查找的复杂度为log的。然而说实话，各种情况的旋转很容易写挂，考场上一旦写挂掉就会心态爆炸，所以我们或许可以通过一些奇妙的方法来使这棵二叉平衡树能够拥有与有需要旋转的二叉查找树同样的性质。而替罪羊树则是这众多非旋转的二叉平衡树中比较好些也比较好理解的一种了（至少比无旋Treap要简单的多了）。 接下来在讲替罪羊树如何实现非旋转之前，我们先要知道一点，什么是优美的数据结构？

暴力啊~ 逃

数据结构最优美的莫过于最暴力却又仍然满足复杂度的数据结构了（类似的还有分块啊，莫队啊，都是很优美的 逃）。所以替罪羊树秉承着最暴力的思想：如果树的结构不够优美了（即查找的复杂度要退化成O(n)或者比log要大了），那么就把这棵子树拍扁了重构，具体如何重构将在下面讲述。这样就能重新回复二叉查找树优美的性质了。所以只要是没有需要提取子树来进行干什么的一些操作，那么替罪羊树无论在代码量和运行时间上都可以优于splay许多。之前学替罪羊树的时候看到了一句非常有意思的话：

我还是比较喜欢平衡树这种结构的（^_^）ノ现在学习了三种平衡树，感觉替罪羊树像是一个人维护一根铁杆，铁杆弯曲了的话强行掰直；SBT像是在杠杆上左右摇晃，不断寻找平衡点；splay像是一个人单手托着装满豆子的盘子，发现不平衡，晃一晃就又平衡了...不过还有奇葩的2-3-4树，看图解感觉在有丝分裂...

这说的就非常有道理啊（雾）。由于是基于拍扁重构的，所以替罪羊树思维难度小，代码量小，易于调试，所以非常适合想我这种手残党使用啊。

知识点详解

注：接下来的代码都以luogu3369为例

平衡因子

平衡因子，顾名思义，是为了判断这棵树是否平衡的一个系数，而在替罪羊树中，这个平衡因子就是用来判断这一棵子树是否需要重构的标准，我们用\alpha来表示。当以x为根这颗子树的满足max(sz[lson],sz[rson])>=sz[x]*\alpha时，我们就可以对这颗子树进行重构了。一般\alpha取值为0.5～1左右，普通题目一般取0.7左右就行了。如果取的\alpha较大，那么重构的次数就比较小，所以插入的效率较高，而查询的效率会相对较低，反之也是如此。

判断子树是否需要重构的代码（由于比较短，就直接现在node结构体里了），代码也顺便给出了node结构体里的各种变量的定义。

struct node {
    node *l,*r;//左右孩子
    int v,sz,valid;//节点的值，节点的子树大小，节点合法（未被删除）子树大小
    bool del;//节点是否被删除
    bool Bad() {//子树是否需要重构
        return (double)l->sz>alpha*(double)sz||(double)r->sz>alpha*(double)sz;
    }
    void Update() {//节点的各个值的更新
        sz=!del+l->sz+r->sz;
        valid=!del+l->valid+r->valid;
    }
};

子树的重构

重构允许重构整棵替罪羊树，也允许重构替罪羊树其中的一棵子树。当我们的树不够平衡的时候，我们就要对于这个子树进行重构了，然而由于这是一棵二叉查找树，所以我们仍要维护这个性质，即保持重建后整棵树的中序遍历与原树相同。所以我们就可以对需要重构的子树进行中序遍历一下，然后二分递归下去进行重构（有点类似与线段树的构建）。形象点来说，就是我们可以把需要重构的子树拍扁成一个序列，然后从这个序列中的中点拎起来（雾），就成了一棵较为平衡的树了。 下面是构造之前与构造之后的图： 构造前：

构造后：

子树重构的代码：

node *Build(std::vector<node*> &v,int l,int r) {
    if(l>=r) return null;
    int mid=(l+r)>>1;
    node *o=v[mid];
    o->l=Build(v,l,mid);
    o->r=Build(v,mid+1,r);
    o->Update();
    return o;
}
void Dfs(node *o,std::vector<node*> &v) {
    if(o==null) return ;
    Dfs(o->l,v);
    if(!o->del) v.push_back(o);//如果这个节点被删除了，那么就不用进行重构了
    Dfs(o->r,v);
    if(o->del) delete o; //节点删除
}
void ReBuild(node* &o) {
    std::vector<node*>v;//v数组记录中序遍历之后各个需要重构的节点
    Dfs(o,v);
    o=Build(v,0,v.size());//o表示重构之后子树的根节点
}

基础操作:

插入：

插入操作一开始和普通BST无异，但在插入操作结束以后，从插入位置往上回溯的时候，对于每一层都进行一次是否需要重构的判断，如果需要重构，就从该层开始重构以该层为根的子树（一个节点导致树的不平衡，就要导致整棵子树被拍扁，听说这就是“替罪羊”这个名字的由来）。

void Insert(int x,node* &o) {
    if(o==null) {//新建节点
        o=new node;
        o->l=o->r=null;
        o->del=false;
        o->sz=o->valid=1;
        o->v=x;
        return ;
    }
    ++o->sz;++o->valid;//在递归下去的时候就把该维护的信息维护好
    if(x>=o->v) Insert(x,o->r);
    else Insert(x,o->l);
    if(o->Bad()) ReBuild(o);//判断是否需要重构
}

删除：

似乎是叫惰性删除来着。。这里的删除并不是直接的删除，而是给这个节点打上一个删除标记，直到重构子树的时候再把无用的节点删除掉。删除也是和插入一样，在回溯的同时仍然要判断是否需要重构。

void Delete(node *o,int rnk) {//当前节点、需要删除的节点的排名（所以在删除之前需要查询一下rank）
    if(!o->del&&rnk==o->l->valid+1) {
        o->del=1;//打上删除标记
        --o->valid;
        return ;
    }
    --o->valid;//维护子树未被删除节点的信息
    if(rnk<=o->l->valid+!o->del) Delete(o->l,rnk);
    else Delete(o->r,rnk-o->l->valid-!o->del);
}

查询rank与kth

这些学过Splay想必已经熟知了吧，但是唯一不同的就是记得我们考虑的时候只考虑存在的节点，而不是直接调用这个子树的sz。

int GetRank(node* o,int x) {
    int ans=1;
    while(o!=null) {
        if(o->v>=x) o=o->l;
        else {
            ans+=o->l->valid+!o->del;//考虑的只是存在的节点
            o=o->r;
        }
    }
    return ans;
}
int FindKth(node* o,int x) {
    while(o!=null) {
        if(!o->del&&o->l->valid+1==x) return o->v;
        if(o->l->valid>=x) o=o->l;
        else {
            x-=o->l->valid+!o->del;
            o=o->r;
        }
    }
}

求前驱和后继

这个实际上并不需要自己手写一个函数了，因为我们可以利用之前已有的函数来进行查询。查询x的前驱的时候，就可以用GetRank先查询x的排名为rnk，然后用FindKth查询排名为rnk-1的数即可。查询x的后继的时候，实际上就是查x+1的排名，因为两者是等价的。这些东西都可以在主函数中实现，就不放上代码了。

复杂度分析

平衡树最重要的一点是它的每次操作的期望复杂度或者均摊复杂度都是logn的，这也是它比较优秀的一个点。那么暴力重构的替罪羊树又为什么能够达到平衡树要求的复杂度呢？ 虽然说是要重构子树，但是复杂度并不会太高，重构一次为O(n)的，并且只有插入的节点达到\alpha*size[t]的时候才有可能会进行重建，所以总共期望的重建次数为logn次，而其他操作的复杂度也是不高的，所以均摊下来总体的复杂度是O(nlogn)的，也是十分优美的。

关于可持久化

至于替罪羊树是否能够可持久化，答案是不可以的，至少在现在看来。由于替罪羊树维护平衡的时候需要重建这棵子树，所以重构之后的信息就会有所改变了，可持久化也就无法进行了。

关于替罪羊树

替罪羊树虽然在时间复杂度和代码量上都比splay优越的很多，然而为什呢替罪羊树运用的却并不广泛呢。原因或许就在于他的非旋转性吧，splay虽然需要用到旋转的操作，但是他灵活性确实无可质疑的，因为splay在维护一个序列的操作中近乎完美。所以替罪羊树的应用也并没有splay那么广泛，不过如果碰到题目可以用替罪羊树代替splay的话，那么就可以毫无异议的使用替罪羊树了。

代码（luogu3369 && BZOJ3224）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const double alpha=0.7;
int n;
/*==================Define Area================*/
namespace ScapegoatTree {
    struct node {
        node *l,*r;
        int v,sz,valid;
        bool del;
        bool Bad() {
            return (double)l->sz>alpha*(double)sz||(double)r->sz>alpha*(double)sz;
        }
        void Update() {
            sz=!del+l->sz+r->sz;
            valid=!del+l->valid+r->valid;
        }
    };
    node *null;
    void Dfs(node *o,std::vector<node*> &v) {
        if(o==null) return ;
        Dfs(o->l,v);
        if(!o->del) v.push_back(o);
        Dfs(o->r,v);
        if(o->del) delete o; 
    }
    node *Build(std::vector<node*> &v,int l,int r) {
        if(l>=r) return null;
        int mid=(l+r)>>1;
        node *o=v[mid];
        o->l=Build(v,l,mid);
        o->r=Build(v,mid+1,r);
        o->Update();
        return o;
    }
    void ReBuild(node* &o) {
        std::vector<node*>v;
        Dfs(o,v);
        o=Build(v,0,v.size());
    }
    void Insert(int x,node* &o) {
        if(o==null) {
            o=new node;
            o->l=o->r=null;
            o->del=false;
            o->sz=o->valid=1;
            o->v=x;
            return ;
        }
        ++o->sz;++o->valid;
        if(x>=o->v) Insert(x,o->r);
        else Insert(x,o->l);
        if(o->Bad()) ReBuild(o);
    }
    int GetRank(node* o,int x) {
        int ans=1;
        while(o!=null) {
            if(o->v>=x) o=o->l;
            else {
                ans+=o->l->valid+!o->del;
                o=o->r;
            }
        }
        return ans;
    }
    int FindKth(node* o,int x) {
        while(o!=null) {
            if(!o->del&&o->l->valid+1==x) return o->v;
            if(o->l->valid>=x) o=o->l;
            else {
                x-=o->l->valid+!o->del;
                o=o->r;
            }
        }
    }
    void Delete(node *o,int rnk) {
        if(!o->del&&rnk==o->l->valid+1) {
            o->del=1;
            --o->valid;
            return ;
        }
        --o->valid;
        if(rnk<=o->l->valid+!o->del) Delete(o->l,rnk);
        else Delete(o->r,rnk-o->l->valid-!o->del);
    }
    node *rt;
}
using namespace ScapegoatTree;

int main() {
    null=new node;
    rt=null;
    read(n);
    while(n--) {
        int opt,x;
        read(opt);read(x);
        if(opt==1) Insert(x,rt);
        if(opt==2) Delete(rt,GetRank(rt,x));
        if(opt==3) writeln(GetRank(rt,x));
        if(opt==4) writeln(FindKth(rt,x));
        if(opt==5) writeln(FindKth(rt,GetRank(rt,x)-1));
        if(opt==6) writeln(FindKth(rt,GetRank(rt,x+1)));
    }
    return 0;
}

2018.9.2 UPD：应机房dalao的要求，上传了一个非指针版本的替罪羊树，不知道为什么似乎跑的比指针版的快那么一丢丢。。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const double alpha=0.7;
const int N=1e5+500;
int n;
/*==================Define Area================*/
namespace ScapegoatTree {
    struct node {
        int l,r,v,sz,valid;
        bool del;
        void New(int x) {l=r=0;v=x;sz=valid=1;del=0;}
    }t[N<<2];
    #define ls(o) t[o].l
    #define rs(o) t[o].r
    #define pb push_back
    int tot=0,rt=0;
    bool Bad(int o) {
        return (double)t[ls(o)].sz>alpha*t[o].sz||(double)t[rs(o)].sz>alpha*t[o].sz;
    }
    void Updata(int o) {
        t[o].sz=t[ls(o)].sz+t[rs(o)].sz+!t[o].del;
        t[o].valid=t[ls(o)].valid+t[rs(o)].valid+!t[o].del;
    }
    void Dfs(int o,std::vector<int> &v) {
        if(!o) return ;
        Dfs(ls(o),v);
        if(!t[o].del) v.pb(o);
        Dfs(rs(o),v);
        return ;
    }
    int Build(std::vector<int> &v,int l,int r) {
        if(l>=r) return 0;
        int mid=(l+r)>>1;
        int o=v[mid];
        ls(o)=Build(v,l,mid);
        rs(o)=Build(v,mid+1,r);
        Updata(o);
        return o;
    }
    void ReBuild(int &o) {
        std::vector<int>v;
        Dfs(o,v);
        o=Build(v,0,(int)v.size());
    }
    void Insert(int x,int &o) {
        if(!o) {
            o=++tot;
            t[o].New(x);
            return ;
        }
        t[o].sz++;t[o].valid++;
        if(x>=t[o].v) Insert(x,rs(o));
        else Insert(x,ls(o));
        if(Bad(o)) ReBuild(o);
        return ;
    }
    int GetRank(int o,int x) {
        int ans=1;
        while(o) {
            if(t[o].v>=x) o=ls(o);
            else {
                ans+=t[ls(o)].valid+!t[o].del;
                o=rs(o);
            }
        }
        return ans;
    }
    int FindKth(int o,int x) {
        while(o) {
            if(!t[o].del&&t[ls(o)].valid+1==x) {return t[o].v;}
            if(t[ls(o)].valid>=x) o=ls(o); 
            else {
                x-=t[ls(o)].valid+!t[o].del;
                o=rs(o);
            }
        }
    }
    void Delete(int o,int Rnk) {
        if(!t[o].del&&Rnk==t[ls(o)].valid+1) {
            t[o].del=1;
            --t[o].valid;
            return ;
        }
        --t[o].valid;
        if(Rnk<=t[ls(o)].valid+!t[o].del) Delete(ls(o),Rnk);
        else Delete(rs(o),Rnk-t[ls(o)].valid-!t[o].del);
    }
}
using namespace ScapegoatTree;

int main() {
    read(n);
    rt=0;
    while(n--) {
        int opt,x;
        read(opt);read(x);
        if(opt==1) Insert(x,rt);
        if(opt==2) Delete(rt,GetRank(rt,x));
        if(opt==3) writeln(GetRank(rt,x));
        if(opt==4) writeln(FindKth(rt,x));
        if(opt==5) writeln(FindKth(rt,GetRank(rt,x)-1));
        if(opt==6) writeln(FindKth(rt,GetRank(rt,x+1)));
    }
    return 0;
}

例题

emm。。至于例题么。。实际上大部分的平衡树题目，替罪羊树都是可以做的嘛。但是这道题目就有点不同了。典型的树套树的题目，但是如果用Splay或者Treap这种基于旋转的平衡树，每次旋转都需要一棵新的线段树，常数就大的飞起了。而如果是替罪羊树套线段树的话，那么只需要在重构替罪羊树的时候一起重构一下线段树就行了。如果想看这道题目的详细题解的话，可以走这里：妙妙的传送门