本文共 9358 字，大约阅读时间需要 31 分钟。

我想写在前面，本文财阀世家全是虚构，没有诋毁之意，如有雷同，纯属巧合

红色预警！！！红色预警

$$前言$$ 我觉得每次学新知识的时候，动用生活中的常见现象来加以理解，真的很 有趣有用 最近梨泰院class真的上头，太™爽了，熟悉我博客风格的小伙伴应该了解 此内容是类比加以理解的，并不是专业术语等类，且模板的理解会在相应代码上方， 本篇可能已经在标题上告知了 用南韩小聋虾（无恶意，韩圈g应该懂）电视剧中常见的财阀世家来进行替罪羊树理解，话不多说，赶紧上路

Scapegoat Tree概念

在各种二叉平衡树中，大多数的平衡树都是通过旋转来维护这棵二叉查找树的性质,$splay$旋转$treap$等等，并且每次的查找的复杂度大概为$log$的

在土地宽广的H国有着各种各样的领域，每个领域都有领头羊，家族势力贼™庞大 然而大家都心知肚明，旋转很容易写挂，十分玄学，多转转说不定就A了已然成为我们的信条

但是越庞大的财阀世家越被其它公司所嫉妒，因为势力体系时常发生戏剧般的扭转，各个成员处心积虑争夺势力，一点点把柄也很容易使它翻车

而替罪羊树餐饮界的巨头长家则是众多非旋转的二叉平衡树中比较好些也比较好理解的一种了，通过一个神奇的东西以“亲情”稳固（下文会介绍）来达到与旋转平衡树差不多的效果。

---

数据结构最优美的莫过于最暴力却又仍然满足复杂度的数据结构了，而且代码还™冗长易挂

替罪羊树作为数据结构的一员，自然秉承着最暴力的思想：

如果树的结构不够优美了发现自己两个儿子的势力出现严重不对等时，可惜为时已晚（即查找的复杂度要退化成$O(n)$或者比 $O(log)$ 要大了），那么就把这棵子树拍扁了重构就是重新洗牌的时候，只要是为了长家，亲情可以不要，以前我喊你爸爸，现在我是你祖宗也是有可能的 这样就能重新拥有二叉查找树优美的性质了让更有权的人做更高的位置，维持整个家族的和谐。但是替罪羊树最大的缺陷就是无法对区间进行操作难以跨部门同时操作多个势力，不像旋转的可以把子树转到一起，非旋$treap$可以通过分裂合并完成 所以只要不搞区间，替罪羊还是很有用的，且无论在代码量和运行时间上都优于$splay$许多

---

我还是比较喜欢平衡树这种结构的

现在学习了三种平衡树

感觉替罪羊树像是一个人维护一根铁杆，铁杆弯曲了的话强行掰直；

SBT像是在杠杆上左右摇晃，不断寻找平衡点；

splay像是一个人单手托着装满豆子的盘子，发现不平衡，晃一晃就又平衡了…

不过还有奇葩的2-3-4树，看图解感觉在有丝分裂…

------出处未知

由于是基于拍扁重构的，所以替罪羊树思维难度小，代码量小，易于调试，所以非常适合手残党使用

---

为了实现替罪羊树的平衡性，引出了一个新概念平衡因子洗牌判定

$$平衡因子$$ 平衡因子是为了判断这棵树是否平衡的一个系数 而在替罪羊树中，这个平衡因子就是用来判断这一棵子树是否需要重构的标准，常用$alpha(\alpha )$ 来表示 当以$x$为根这颗子树的满足 $$max(sz[lson],sz[rson])>=sz[x]\ast \alpha$$ 时，即左边或右边有一个子树所占大小超过了平衡因子的限定，出现了严重的偏差时判断自己手下是不是势力足够庞大的时候自觉选择让位，长大喜说过：为了长家，我们就可以对这颗子树进行重构了 一般 $\alpha \alpha$ 取值为$0.5～1$左右，普通题目一般取$0.7$左右就行了两个手下有一定能力，不必要限制地太死，可以观察谁更有能力得到更多人数支持，多教孩子去杀鸡（狗头。如果取的 $\alpha$ 较大，那么触发重构的次数就比较小，所以插入的效率较高，而查询的效率会相对较低，反之则是频繁触发重构导致插入效率变低，查询因为很稳定效率就会变高

---

其实我不太喜欢写死板概念，本人爱好搞模板

模板

变量声明

背景简述：在H国有个富可敌国（好老套的霸道男主人设）的财阀世家长家（借用梨泰院class），有着庞大的家庭成员链，每个人都有不同的股份势力。而我们则是站在上帝视角来看这场权力纠纷的

exist：该点是否真实存在（Q：干嘛呀？A：因为后面的删除，不要慌） 这个人是不是名存实亡，势力是否还在自己手上 son[2]：0左儿子，1右儿子政策要求计划生育，就生两个，当自己的手下，hhhh val：该点的权值（看题目给的是什么） 上帝分配给这个娃儿的股份势力 alive：子树（不含自己）中真正存在的点数和（Q：又在搞甚么？A：不要慌，往下走）看看站在自己阵营的势力人数有多少个现在还有股份势力的，帮助自己与兄弟对抗 total：子树中（不含自己）管它总的点数和（管它是不是真的还存在） 看看愿意站在自己阵营人数，包括已经名存实亡失去势力的人员，至少曾经帮过我，尽管后面发现会直接扔掉它 memory[]，idx2：是自己手动的内存池，自然idx2就是指针 cur[]，idx1：拍扁的数组和自己配置的指针用来重新洗牌，打乱财阀集团的职位的工具 长家的亲情是建立在势力基础上的，之前你是我爸爸，是因为我势力不够，一旦我翻身上位，你就得叫我爸爸

struct Scapegoat {
   	bool exist;	int son[2], val, alive, total;}t[MAXN];int idx1, idx2, flag, root, Size;int cur[MAXN], memory[MAXN];

Bad函数判断是否需要重构

理解

其实上面介绍平衡因子的时候已经告诉了人数占比超过我们划分的界限，说明孩子已经足够优秀了，获得了大部分下人的支持，尽管可能势力并不多呢，老父亲你就自己乖乖下位吧！！！

（老父亲内心OS）

模板

bool Bad ( int rt ) {
   	return ( double ) t[rt].alive * alpha <= ( double ) max ( t[t[rt].son[0]].alive, t[t[rt].son[1]].alive );}

rebuild重构

理解

首先对于这棵子树要先进行拍扁，从小到大的顺序，左儿子->根->右儿子

然后把这个序列重新提起来，如果要左右尽量平衡的话，我们肯定是从中间开始提 很像线段树的递归方法 开始洗牌了，这个部部长的两个手下也可以叫做两个儿子的能力体现已经很明显了，下边人的站队已经有所明显对比，部长就退位让儿子上，自己卧薪尝胆一段时间说不定能再上

模板

void flat ( int rt ) {
   	if ( ! rt )		return;	flat ( t[rt].son[0] );	if ( t[rt].exist )		cur[++ idx1] = rt;	else		memory[++ idx2] = rt;	flat ( t[rt].son[1] );} void build ( int l, int r, int &rt ) {
   	int mid = ( l + r ) >> 1;	rt = cur[mid];	if ( l == r ) {
   		t[rt].son[0] = t[rt].son[1] = 0;		t[rt].alive = t[rt].total = 1;		return;	}	if ( l < mid )		build ( l, mid - 1, t[rt].son[0] );	else		t[rt].son[0] = 0;	build ( mid + 1, r, t[rt].son[1] );	t[rt].total = t[t[rt].son[0]].total + t[t[rt].son[1]].total + 1;	t[rt].alive = t[t[rt].son[0]].alive + t[t[rt].son[1]].alive  + 1;}void rebuild ( int &rt ) {
   	idx1 = 0;	flat ( rt );	if ( idx1 )		build ( 1, idx1, rt );	else		rt = 0;}

insert插入

理解

判断该点的权值与我们$wanttoinsert$的点的权值的大小关系，小的往左儿子，右的往右儿子

其实我们发现如果$x$发生重构，有可能一路上的祖宗（有颜色的点）都会有所影响，本应该找最上面第一个被影响的（绿色）然后重构，下面就跟着完成了，但是窝码的是一路上遇到就直接重构（有颜色的都重构一遍） 显而易见很浪费时间，但是我不会另一种，所以如果有dalao会的话，麻烦教教蒟蒻 这样洗牌时从左到右的势力逐渐上升，可以理解为势力过大的想去支持左边，但是左儿子不稀罕，势力过小的它反倒稀罕，两兄弟可能口味不太一样吧hhhhh 其实它们很聪明的，因为长家洗牌规则是取左右支持者差不多的人上，既然自己选择了要小/大的，就要把大/小丢给对方，尽量保证自己站在中间位置，当然了这一切都是假象，毕竟上帝安排这娃儿成为谁的手下

模板

void insert ( int &rt, int val ) {
   	if ( ! rt ) {
   		rt = memory[idx2 --];		t[rt].val = val;		t[rt].exist = t[rt].alive = t[rt].total = 1;		t[rt].son[0] = t[rt].son[1] = 0;		return;	}	t[rt].alive ++, t[rt].total ++;	if ( val <= t[rt].val )		insert ( t[rt].son[0], val );	else		insert ( t[rt].son[1], val );	if ( Bad ( rt ) )		rebuild ( rt );}

delete删除

理解

替罪羊的删除很有趣，是一种惰性删除，就是我不是真的把你删了，只是给你打个删除标记，等到重构的时候我不把你加进去，自然而然你就消失了，锁定一个点有两个方法，权值或者排名，我们可以把权值转化成排名用查找排名系统就可以了

你的势力已经被剥夺了，但是你还是站在这里可以当个人形标志，等重新洗牌的时候，你就相当于被冷藏了，调到了帕津，不再在本部有任何痕迹，一切为零

模板1（删除排名为x的数）

void Delete_rnk ( int &rt, int rnk ) {
   	if ( t[rt].exist && t[t[rt].son[0]].alive + 1 == rnk ) {
   		t[rt].exist = 0;		t[rt].alive --;		return;	}	t[rt].alive --;	if ( rnk <= t[t[rt].son[0]].alive + t[rt].exist )		Delete_rnk ( t[rt].son[0], rnk );	else		Delete_rnk ( t[rt].son[1], rnk - t[t[rt].son[0]].alive - t[rt].exist );}

模板2（删除权值为x的数）

有时候删多了，自己手底下一共的点还没有达到我们的期望，也要进行一次重构

被革职的人太多了，自己的支持人数其实已经不多了，我们就进行一次洗牌统计，巩固一下部门政权

void Delete_val ( int val ) {
   	Delete_rnk ( root, FindRank ( val ) );	if ( ( double ) t[root].total * alpha > t[root].alive )		rebuild ( root );}

查找x排名

理解

找排名其实跟$treap,splay$都是一路子，先看左儿子，发现排名没有左儿子真的存在的点多就在左儿子里面找，不然就在右儿子里面找，注意是真的存在的点因为我们是惰性删除看看势力从小到大的顺序，自己排在第几位

模板

int FindRank ( int k ) {
   	int rt = root, ans = 1;	while ( rt ) {
   		if ( k <= t[rt].val )			rt = t[rt].son[0];		else {
   			ans += t[t[rt].son[0]].alive + t[rt].exist;			rt = t[rt].son[1];		}	}	return ans;}

找第K大

理解

跟其他平衡树一样的的思路，同样这里是要以真实存在的点来进行计算，因为我们是惰性删除看看势力第K大的娃儿是哪个，我们上帝没事还是要找点事做滴

模板

int FindKth ( int k ) {
   	int rt = root;	while ( rt ) {
   		if ( t[rt].exist && t[t[rt].son[0]].alive + 1 == k )			return t[rt].val;		else if ( k <= t[t[rt].son[0]].alive )				rt = t[rt].son[0];			else {
   				k -= ( t[t[rt].son[0]].alive + t[rt].exist );				rt = t[rt].son[1];			}	}}

前驱后继

思路

根本不用单独写前驱后继那么复杂，直接找到$x$的排名，然后$\pm 1$就是前驱后继了康康势力最接近与自己的比自己小的和比自己大的，说实话要不是上帝要问问，谁管你是谁，影响老子上位

不同的题目不同的要求不同的写 什么意思呢？我们以例题的要求为例 可能有多个值相同的数，然后前驱要求严格小于，后继要求严格大于 那么我们的写法就应该是

printf ( "%d\n", FindKth ( FindRank ( x ) - 1 ) );printf ( "%d\n", FindKth ( FindRank ( x + 1 ) ) );

要理解我们的查找排名函数是排名找的是同值中最小的一个，排名减一值一定变小了 而因为有同值所以我们就要手动把值加一再查找，不管是否存在

例题：Tyvj 1728 普通平衡树

题目

code

#include 
   
    #include 
    
     using namespace std;#define MAXN 2000005#define alpha 0.7struct Scapegoat {
   	bool exist;	int son[2], val, alive, total;}t[MAXN];int idx1, idx2, flag, root, Size;int cur[MAXN], memory[MAXN];bool Bad ( int rt ) {
   	return ( double ) t[rt].alive * alpha <= ( double ) max ( t[t[rt].son[0]].alive, t[t[rt].son[1]].alive );}void flat ( int rt ) {
   	if ( ! rt )		return;	flat ( t[rt].son[0] );	if ( t[rt].exist )		cur[++ idx1] = rt;	else		memory[++ idx2] = rt;	flat ( t[rt].son[1] );} void build ( int l, int r, int &rt ) {
   	int mid = ( l + r ) >> 1;	rt = cur[mid];	if ( l == r ) {
   		t[rt].son[0] = t[rt].son[1] = 0;		t[rt].alive = t[rt].total = 1;		return;	}	if ( l < mid )		build ( l, mid - 1, t[rt].son[0] );	else		t[rt].son[0] = 0;	build ( mid + 1, r, t[rt].son[1] );	t[rt].total = t[t[rt].son[0]].total + t[t[rt].son[1]].total + 1;	t[rt].alive = t[t[rt].son[0]].alive + t[t[rt].son[1]].alive  + 1;}void rebuild ( int &rt ) {
   	idx1 = 0;	flat ( rt );	if ( idx1 )		build ( 1, idx1, rt );	else		rt = 0;}void insert ( int &rt, int val ) {
   	if ( ! rt ) {
   		rt = memory[idx2 --];		t[rt].val = val;		t[rt].exist = t[rt].alive = t[rt].total = 1;		t[rt].son[0] = t[rt].son[1] = 0;		return;	}	t[rt].alive ++, t[rt].total ++;	if ( val <= t[rt].val )		insert ( t[rt].son[0], val );	else		insert ( t[rt].son[1], val );	if ( Bad ( rt ) )		rebuild ( rt );}int FindKth ( int k ) {
   	int rt = root;	while ( rt ) {
   		if ( t[rt].exist && t[t[rt].son[0]].alive + 1 == k )			return t[rt].val;		else if ( k <= t[t[rt].son[0]].alive )				rt = t[rt].son[0];			else {
   				k -= ( t[t[rt].son[0]].alive + t[rt].exist );				rt = t[rt].son[1];			}	}}int FindRank ( int k ) {
   	int rt = root, ans = 1;	while ( rt ) {
   		if ( k <= t[rt].val )			rt = t[rt].son[0];		else {
   			ans += t[t[rt].son[0]].alive + t[rt].exist;			rt = t[rt].son[1];		}	}	return ans;} void Delete_rnk ( int &rt, int rnk ) {
   	if ( t[rt].exist && t[t[rt].son[0]].alive + 1 == rnk ) {
   		t[rt].exist = 0;		t[rt].alive --;		return;	}	t[rt].alive --;	if ( rnk <= t[t[rt].son[0]].alive + t[rt].exist )		Delete_rnk ( t[rt].son[0], rnk );	else		Delete_rnk ( t[rt].son[1], rnk - t[t[rt].son[0]].alive - t[rt].exist );}void Delete_val ( int val ) {
   	Delete_rnk ( root, FindRank ( val ) );	if ( ( double ) t[root].total * alpha > t[root].alive )		rebuild ( root );}int main() {
   	int n;	for ( int i = 2000000;i >= 1;i -- )		memory[++ idx2] = i;	scanf ( "%d", &n );	for ( int i = 1;i <= n;i ++ ) {
   		int opt, x;		scanf ( "%d %d", &opt, &x );		switch ( opt ) {
   			case 1 : insert ( root, x ); break;			case 2 : Delete_val ( x ); break;			case 3 : printf ( "%d\n", FindRank ( x ) ); break;			case 4 : printf ( "%d\n", FindKth ( x ) ); break;			case 5 : printf ( "%d\n", FindKth ( FindRank ( x ) - 1 ) ); break;			case 6 : printf ( "%d\n", FindKth ( FindRank ( x + 1 ) ) ); break;		}	}	return 0;}
    
   

刚开始就觉得这种数据结构都可以用皇宫生存法则来理解，但是我觉得写过了再写就没有社么意思了，所以直接pass了，但是如果你们喜欢，我不介意下一次再用一次

---

其实本来是想用227的举报同人圈事件的，但是我怕被无脑举报，想想还是算了，但是我还是很不甘的，毕竟我的太太都封笔了…

要知道学了splay是为了LCT，那么学了替罪羊就是为了k-d tree，你们想用什么来类比呢？？欢迎评论，不怕没有脑洞就怕脑洞不够大

转载地址：http://pxil.baihongyu.com/