替罪羊树

前言

暴力即优雅

替罪羊树是一种依赖于暴力重构操作维持平衡的平衡树

它利用了一个平衡因子$α$来维持平衡

$α$通常设0.7

当一棵子树不满足平衡因子的条件的时候

我们就把这棵子树拍扁重建

听起来就很暴力

在别人嗷嗷乱转的时候直接一巴掌上去

一打一个不吱声

感谢xixi的代码

平衡树（FHQ/Splay/替罪羊）

操作

重构

替罪羊树之所以能够平衡，是在于其重构时不是瞎重构，而是将被重构的子树重构为一棵完全二叉树

需要一个辅助的数组记录中序遍历的序列

int rebuild(int l,int r)
{
	if(l==r)
	{
		tr[t[l]]={tr[t[l]].v,1,1,1,0,0};
		return t[l];
	}
	int mid=l+r>>1;
	while(mid<r && tr[t[mid]].v==tr[t[mid+1]].v) mid++;
	int x=t[mid];
	ls(x)=l<mid?rebuild(l,mid-1):0;
	rs(x)=r>mid?rebuild(mid+1,r):0;
	tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;
	tr[x].fac=tr[ls(x)].fac+tr[rs(x)].fac+1;
	return x;
}

检查平衡

检查左右子树之一的大小占其本身子树大小的比例是否超过 $α$

如果不平衡就拍扁重建

就像这种 是不是看起来就欠拍不平衡

void check(int &x,int ed)
{
	if(x==ed) return;
	if(max(tr[ls(x)].siz,tr[rs(x)].siz)>tr[x].siz*0.7 || tr[x].siz-tr[x].fac>tr[x].siz*0.3)
	{
		t.clear();
		dfs(x);
		x=t.empty()?0:rebuild(0,t.size()-1);
        return;
	}
	check(tr[x].s[tr[ed].v>tr[x].v],ed);
	tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;
}

插入

替罪羊树的插入操作与其他的二叉搜索树差不多。

只不过因为其导致了树形态的改变

我们在插入完回溯的过程中还需要判断一下是否需要重构

void Insert(int &x,int v)
{
	if(!x)
	{
		tr[x=++cnt]={v,1,1,1};
		check(rt,x);
		return;
	}
	tr[x].siz++,tr[x].fac++;
	Insert(tr[x].s[v>tr[x].v],v);
}

删除

替罪羊树使用惰性删除(就是打标记删)，只需要将对应节点上代表节点内数据数量的标记自减一即可。

void delet(int x,int v)
{
	tr[x].fac--;
	if(tr[x].fg && tr[x].v==v)
	{
		tr[x].fg=0;
		check(rt,x);
	}
	else delet(tr[x].s[v>tr[x].v],v);
}

查询

跟BST相同

判断该找左子树还是右子树

递归找即可

int getrank(int v)
{
	int x=rt,k=1;
	while(x)
	{
		if(v<=tr[x].v) x=ls(x);
		else k+=tr[x].fg+tr[ls(x)].fac,x=rs(x);
	}
	return k;
}
int getval(int k)
{
	int x=rt;
	while(x)
	{
		if(tr[x].fg && tr[ls(x)].fac+tr[x].fg==k) break;
		if(tr[ls(x)].fac>=k) x=ls(x);
		else k-=tr[ls(x)].fac+tr[x].fg,x=rs(x);
	}
	return tr[x].v;
}

---

有了之前的基础

感觉平衡树越来越好学

再次感谢xixi的代码

（号称全网最佳）

完结撒花

---

引用来源

替罪羊树~讲解

替罪羊树（Scapegoat Tree）-CSDN博客

替罪羊树 - OI Wiki (oi-wiki.org)