【数据结构】替罪羊树-Scapegoat Tree

替罪羊树不需要旋转来保持平衡，它保持平衡的方式就是重构。

操作：

• 重构，重构允许重构整个树，也可重构它的任一子树。

这其实是一种非常暴力的方法，俗话就是将整个树拍平，成为一个有序序列，然后从中间拉成一棵二叉树。

具体来说定义一个平衡因子α，当某个结点x的某棵子树x.left.size + x.right.size > x.size * α时，就将这棵树拍扁重构。

拍平之后就是这样：

拉长：

重构完成。这样重构一次的时间复杂度为$O(n)$ （n为子树大小），但是实际上替罪羊树的单次插入时间复杂度并不会达到 $O(nlogn)$ ，因为一个 size=t 的子树需要插入 $\Omega (t)$ 个点才会被重构，所以可以通过势能分析来证明替罪羊树的单次操作的均摊时间复杂度为 O(logn)，具体证明这里不详细展开。

• 插入

插入操作和普通二叉搜索树无大异，唯一不同的是，在递归返回时需要判断该子树是否需要重构。

• 删除（惰性删除）

这里的删除不是真正意义上的删除，而是给要删除的点打一个标记，在该节点需要被重构时删除掉。

平衡因子的取值范围：

显然， α 的取值范围在0.5~1的范围内，一般取0.7较为合适。太大的α会使得树变深，太小则会引起过多的重构。

代码：

#include<cstdio>
#include<vector>

const double alpha = 0.75;

class SGTNode{
public:
	SGTNode *left,*right;
    int key,size,cnt;
    bool deleted;
    bool isNeedToReBuild(){return left->cnt>alpha*cnt+5||right->cnt>alpha*cnt+5;}
    void maintain(){size=!deleted+left->size+right->size;cnt=1+left->cnt+right->cnt;}
};

SGTNode *nil;

void dfs(SGTNode *o,std::vector<SGTNode* > &v){
	if(o==nil)return;
    dfs(o->left,v);
    if(!o->deleted)v.push_back(o);
    dfs(o->right,v);
    if(o->deleted)delete o;
}

SGTNode* build(std::vector<SGTNode* > &v,int l,int r){
	if(l>=r)return nil;
    int mid=(l+r)>>1;
    SGTNode *o=v[mid];
    o->left=build(v,l,mid);
    o->right=build(v,mid+1,r);
    o->maintain();
    return o;
}

void reBuild(SGTNode* &o){
	std::vector<SGTNode*> v;
    dfs(o,v);
    o=build(v,0,v.size());
}

void insert(int x,SGTNode* &o){
    if(o==nil){
        o=new SGTNode;
        o->left=o->right=nil;
        o->deleted=false;
        o->size=o->cnt=1;
        o->key=x;
        return;
    }else{
        ++o->size;
        ++o->cnt;
        if(x>=o->key)
            insert(x,o->right);
        else
            insert(x,o->left);
        if(o->isNeedToReBuild())reBuild(o);
    }
}

int rank(SGTNode *now,int x){
    int ans=1;
    while(now!=nil){
        if(now->key>=x)now=now->left;
    	else{
            ans+=now->left->size+!now->deleted;
            now=now->right;
        }
    }
    return ans;
}

int select(SGTNode *now,int x){
    while(now!=nil){
        if(!now->deleted && now->left->size+1==x)
            return now->key;
        if(now->left->size>=x)now=now->left;
        else{
            x-=now->left->size+!now->deleted;
            now=now->right;
        }
    }
}

void erase(SGTNode *o,int k){
    if(!o->deleted && k==o->left->size+1){
        o->deleted=1;
        --o->size;
        return;
    }
    --o->size;
    if(k<=o->left->size+!o->deleted)
        erase(o->left,k);
    else
        erase(o->right,k-o->left->size-!o->deleted);
}
SGTNode *root;
int main(){
	nil=new SGTNode;
    root=nil;
    int n;
    scanf("%d",&n);
    while(n--){
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)insert(x,root);
        if(op==2)erase(root,rank(root,x));
        if(op==3)printf("%d\n",rank(root,x));
        if(op==4)printf("%d\n",select(root,x));
        if(op==5)printf("%d\n",select(root,rank(root,x)-1));
        if(op==6)printf("%d\n",select(root,rank(root,x+1)));
    }
	return 0;
}

【例题】Luogu p3369

参考信息：https://zhuanlan.zhihu.com/p/21263304

https://ezoixx130.blog.luogu.org/tizuiyangshu