替罪羊树 洛谷 P3369 【模板】普通平衡树

缘起

平衡二叉树是为了解决二叉树退化为链表导致O(n) 查询复杂度而诞生的数据结构. 现在有一款平衡二叉树比较暴力，就是所谓的替罪羊树（scapegoat tree， 下面简称SGT）（虽然其实我觉得这个名字叫的觉得不是很贴切，但是市面上都这么叫它）.

SGT最大的特点就是一旦失衡，就暴力重建，检查是否失衡就是在插入和删除节点的时候. 其他的和典型的BST没什么两样. 本文以 洛谷 P3369 【模板】普通平衡树 为板子，讲解一下这种数据结构。

分析

题比较裸

题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入xx数
删除xx数(若有多个相同的数，只删除一个)
查询xx数的排名(排名定义为比当前数小的数的个数+1+1。若有多个相同的数，因输出最小的排名)
查询排名为xx的数
求xx的前驱(前驱定义为小于xx，且最大的数)
求xx的后继(后继定义为大于xx，且最小的数)
输入输出格式
输入格式：
第一行为nn，表示操作的个数,下面nn行每行有两个数optopt和xx，optopt表示操作的序号( 1 \leq opt \leq 6 1≤opt≤6 )

输出格式：
对于操作3,4,5,63,4,5,6每行输出一个数，表示对应答案

输入输出样例

输入样例#1：
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

输出样例#1：
106465
84185
492737

说明
时空限制：1000ms,128M

1.n的数据范围： n \leq 100000 n≤100000
2.每个数的数据范围： [-{10}^7, {10}^7][−10 
7
 ,10 
7
 ]
来源：Tyvj1728 原名：普通平衡树

在此鸣谢

这里就不多说什么话了，直接上代码（是参见【1】中的代码改进的, 多谢 a_forever_dream 大神）

#include "stdafx.h"
#include <iostream>
#include <cstdio>
using namespace std;
#define LOCAL

const int MAX_N = 100000+5;
const int INF = 0x3f3f3f3f;

const double alpha = 0.6; // 平衡因子（一般选取0.5~1，一般选0.75,但是这里选0.6是有理由的，见后）
const double beta = 0.6; // 用途见具体代码

struct
{
	int val; // 该节点的数值
	int lc,rc; // 左右孩子在sgt中的索引
	int size; // 以本节点为根的子树含有的节点总数（包括已经处于删除状态的节点）
	int validsize; // 以本节点为根的子树含有的节点总数（不包括已经处于删除状态的节点）
	int cnt; // 以本节点为根的子树包含数值的总个数(当然，不包含处于删除状态的节点)
	int tot; // 本节点val的个数.
	bool valid; // true 表示处于删除状态（只有所有tot个数值都被删除了，才会变得valid=false）
	int parent; // 父节点在sgt中的索引
} sgt[MAX_N]; // sgt 是替罪羊树， 注意，0索引不用于存储数据（根节点的parent域是0）， 关于节点的数据结构详见图及下面的注释

struct
{
	int val;
	int tot;
}rebuidsgt[MAX_N]; // 用于临时保存被拍扁的sgt子树，注意，为什么我们只需要val和tot两个域? 因为这里面的节点都是valid=true即有效的节点, 我们是要拿rebuidsgt中的节点去重建sgt子树用的，其余的信息在重建的过程中自然会写入的,我们只需要val（值）+tot（val出现的次数）两个信息

int n; // rebuidsgt中节点的个数

int root; // 根节点
int len; // sgt中总共有多少个节点

int ids[MAX_N]; // id池子
int idnum; // 池子中的id个数

int idpool() // id池子
{
	if (idnum) return ids[idnum--]; // 如果池子中有id的话，就直接拿去用
	return ++len; // 否则新分配一个出去
}

int build(int x, int parent) // 新建sgt的节点, 返回此节点在sgt中的索引
{
	int index = idpool(); // 从id池子中获取id
	sgt[index].val = x;
	sgt[index].lc = sgt[index].rc = 0;
	sgt[index].parent = parent;
	sgt[index].cnt = sgt[index].tot = sgt[index].size = sgt[index].validsize = 1;
	sgt[index].valid = true;
	return index;
}

int findx(int now, int x) // now是sgt中的当前节点, x是待寻找的数值, 方法返回sgt中的索引，注意，整个过程不考虑节点是否被移除
{
	if (sgt[now].val < x && sgt[now].rc)
	{
		return findx(sgt[now].rc, x); // 跳到右子树上去找
	}
	if (sgt[now].val >x && sgt[now].lc)
	{
		return findx(sgt[now].lc, x); // 跳到左子树上去找
	}
	return now; // 注意，这个now未必满足 sgt[now].val=x, 很可能sgt[now].val>x(上一步是找右子树，结果大过头了，但是sgt[now].lc=0（否则的话，就会走sgt[now]的左子树, 这样findx返回的就不会是now了）, 注意，不可能上一步是找左子树，不然sgt[now]的父节点就更大于x了, 上一步根据bst是不可能做这种决定的), 或者 sgt[now].val<x(上一步是找左子树，结果小过头了，注意, sgt[now]一定没有右子树, 不然下一步就会因为sgt[now]<x而走sgt[now]的右边，这样findx返回的就不会是now了)
}

void update(int now,  int _validsize, int _size, int _cnt) // 更新sgt[now]以及他的父辈节点的size、validsize、cnt 三个域
{
	if (!now) // 已经更新到头了
	{
		return;
	}
	sgt[now].size += _size;
	sgt[now].validsize += _validsize;
	sgt[now].cnt += _cnt;
	update(sgt[now].parent,_validsize, _size, _cnt); // 递归更新父辈节点
}

void flatten(int now)  // 将sgt[now]为根的子树拍扁到rebuidsgt[1,...,n]数组中去，其实就是中序遍历（从而就是按照val域从小到大）
{
	if (!now) // 如果到头了
	{
		return;
	}
	flatten(sgt[now].lc); // 左子树
	if (sgt[now].valid) // 如果是有效节点才加入
	{
		n++;
		rebuidsgt[n].val = sgt[now].val;
		rebuidsgt[n].tot = sgt[now].tot; // 拷贝有效节点压入rebuidsgt
	}
	ids[++idnum] = now; // 因为拍扁了sgt[now]——其实所谓的拍扁的真实含义是将sgt[now]为根的子树中所有的有效节点按照中序顺序压入数组rebuidsgt（树-->数组，形象的说就是拍扁了）,无效节点就丢弃了，但是不管是有效节点还是无效节点，有效节点进入rebuidsgt数组，无效节点丢弃，但是节点曾今占据的sgt中的索引——now不能也丢掉了，而要回收进id池子. 后面如果还要分配id的话，可以复用的（这样, sgt数组的真实长度就不会太长）
	flatten(sgt[now].rc);
}

int readd(int low, int high, int parent) // 分治建树（利用rebuildsgt[low,high]建立一棵平衡二叉树） 返回新的此棵重构之后的子树的根节点,sgt[parent]是这棵重构好的树的根节点的父节点
{
	if (low > high) return 0;
	int mid = (low+high)>>1;
	int id = idpool(); // 从id池子中获取id, 这个id是新的根节点
	sgt[id].val = rebuidsgt[mid].val;
	sgt[id].tot = rebuidsgt[mid].tot;
	sgt[id].parent = parent; // 认爹在这里完成了
	sgt[id].size = sgt[id].validsize = high-low+1; // 因为rebuildsgt[low,...,high]中全部是有效节点, 所以validsize和size相等, 并且个数是high-low+1
	sgt[id].lc = readd(low, mid-1, id);
	sgt[id].rc = readd(mid+1, high, id); // 递归构建子树
	sgt[id].valid = true; // 显然是有效的
	sgt[id].cnt = sgt[sgt[id].lc].cnt+sgt[sgt[id].rc].cnt+sgt[id].tot;
	return id;
}

void rebuid(int now) // 重建sgt[now]为根节点的sgt子树，想法就是，sgt[now]为根的子树中可能存在处于删除状态的节点, 我们要首先中序遍历这棵子树，对于处于删除状态的节点我们统统不要，即将处于valid=true状态的子树节点按照中序压入数组中去
{
	n = 0;
	flatten(now); // 中序遍历压入有效节点, 此时sgt[now]为根的子树全部消失了——都进入了rebuildsgt中，即已经被拍扁了
	if (now == root) // 如果现在处理的是根节点的话，则需要改变根节点了
	{
		root = readd(1, n, 0); // 根节点的parent自然是0咯
	}
	else // 如果now不是root的话（注意，此时sgt[now]已经消失，其有效节点已经全部钻进rebuildsgt中去了，无效节点已经被丢弃了）
	{
		update(sgt[now].parent, 0, -(sgt[now].size - sgt[now].validsize) ,0); // 则更新sgt[now].parent的size域即可, 因为整个过程其实就是将sgt[now]为根的子树中的无效节点去除，但是有效节点保留，所以sgt[now]的父节点的有效节点数量(validsize)不会变化，节点数(size)因为删除掉了无效节点, 所以节点数会减少，减少的数量恰好就是sgt[now]无效节点数目，即 sgt[now].size-sgt[now].validsize
		int parent = sgt[now].parent; // 保存父节点，因为如果下面if和else中的代码直接使用sgt[now].parent而不是使用这里保存的parent的话，则在下面readd过程中now是会变的（则sgt[now].parent就不再是原本的parent了）
		if (now == sgt[parent].lc) // 如果sgt[now]是其原本父节点的左孩子的话
		{
			sgt[parent].lc = readd(1, n, parent); // 则继续是左孩子吧~
		}
		else
		{
			sgt[parent].rc = readd(1, n, parent); // 继续做右孩子
		}
	}
}

void rebuildIfNecessary(int now, int x) // 重走一遍当时插入/删除时走的路(因为只可能在这条路上的节点才可能失衡), 一旦发现失衡，则拍直重建（这才是替罪羊树的实现平衡的精髓~ 而不是找什么替罪羊~）
{
	if (!now)
	{
		return;
	}
	if ( // 这里需要重构的标准是以size来衡量的, 而不是以有效节点数或者数值总数，因为替罪羊树是惰性删除，就算是被删除掉的节点也是要走过的
		sgt[now].lc && (double)sgt[now].size*alpha<= sgt[sgt[now].lc].size // 如果sgt[now]有左孩子，并且左孩子的节点个数已经超过了sgt[now]的alpha比例
		||
		sgt[now].rc && (double)sgt[now].size*alpha<= sgt[sgt[now].rc].size // 如果sgt[now]有右孩子，并且右孩子的节点个数已经超过了sgt[now]的alpha比例
		||
		sgt[now].validsize <= beta * (double)sgt[now].size // 如果sgt[now]的有效节点个数的比例已经低于了beta（表明sgt[now]为根的子树中已经有太多的处于删除状态的节点），则会导致搜索的效率下降的, 所以也需要重建
		)
	{
		rebuid(now); // 重建now为根节点的sgt子树,从root到x的路上只要rebuild出现一次，后面都不需要rebuild了. 因为已经将sgt的子树 拍扁重构平衡二叉树了.
	}
	else if (sgt[now].val!=x) // 如果不等（注意，如果相等的话，则从root到x要走的路已经走完了，则不需要继续往下走了）
	{
		if (sgt[now].val > x) // 后续要走左子树
		{
			rebuildIfNecessary(sgt[now].lc, x); // 看看左子树要不要重建
		}
		else // 即sgt[now].val < x
		{
			rebuildIfNecessary(sgt[now].rc, x); // 看看右子树要不要重建
		}
	}
}

void add(int x)
{
	if (!root) // 如果这是第一个节点的话, 则新建根节点了事
	{
		root = build(x, 0);
		return;
	}
	int now = findx(root, x); // 找到now, 即sgt[now].val=x或者 sgt[now].val>x(上一步是找右子树)，或者 sgt[now].val<x(上一步是找左子树)
	if (sgt[now].val == x)
	{
		sgt[now].tot++;
		if (!sgt[now].valid) // 如果之前已经是标记为删除状态的话
		{
			sgt[now].valid = true; // 重新激活它
			update(now, 1, 0, 1); // 更新本节点及以上的父辈节点, 因为原先是删除状态的，现在激活了，所以有效节点自然+1啦. 而因为节点只是打上删除标记，并不真正删除，所以size域不会变化，cnt域+1是显然的
		}
		else
		{
			update(now, 0, 0, 1); // 因为sgt[now]原本就有效，所以validsize域不会变化, 所以_validsize入参是0，但是cnt域依旧要+1
		}
	}
	else // 如果 sgt[now].val 和 x不相等
	{
		if (sgt[now].val < x) // 如果是sgt[now].val<x(上一步是找左子树)，则x应该是sgt[now]的右子节点
		{
			sgt[now].rc =  build(x, now); // 新建节点, 并且是sgt[now]的右子节点
		}
		else // 如果是sgt[now].val>x(上一步是找右子树)，则x应该是sgt[now]的左子节点
		{
			sgt[now].lc = build(x, now); // 新建节点, 并且是sgt[now]的左子节点
		}
		update(now, 1,1,1);
	}
	rebuildIfNecessary(root, x); // 注意，前面根本没有考虑节点的删除状态，即便已经被删除了，也仅仅是惰性删除, 本行代码就要考虑拍直重建sgt了，注意，网上有从x到根这样重建的，但是这里采用的是从根到x, 因为逆流而上到root的重建的话，底部重建好了，根处可能还是要重建的，但是从root到x,一旦发现需要重建，重建一次就好了
}

void del(int x) // 删除x
{
	int now = findx(root, x); // 找到x
	if (sgt[now].val == x) // 找到了才能删除啊
	{
		if (!(--sgt[now].tot)) // 如果删没了
		{
			sgt[now].valid = false; // 失效（替罪羊树的删除时惰性删除,所以比较简单）
			update(now, -1, 0, -1);
		}
		else // 如果还没删没, 则有效节点数没变
		{
			update(now, 0, 0, -1);
		}
		rebuildIfNecessary(root, x); // 必要时重构
	}
}

void getrankofx(int x) // 获取x的排名
{
	int now = root;
	int ans = 0;
	while(now && x!=sgt[now].val)
	{
		int lc = sgt[now].lc;
		int rc = sgt[now].rc;
		if (x<sgt[now].val)
		{
			now = lc; // 跳左子树
		}
		else
		{
			ans += (lc?sgt[lc].cnt:0)+sgt[now].tot;
			now = rc; // 跳右子树
		}
	}
	if (now && sgt[now].lc) // 最好如果还有合法左子树的话
	{
		ans+=sgt[sgt[now].lc].cnt;
	}
	printf("%d\n", ans+1); // 上面一直在求比x小的数值的个数, 最后要+1, 因为排名是从1开始的
}

void getnumberofrankx(int x) // 获取排名为x的数值
{
	int now = root;
	while(1)
	{
		if (sgt[sgt[now].lc].cnt>=x)
		{
			now = sgt[now].lc; // 跳到左子树
		}
		else
		{
			x-=sgt[sgt[now].lc].cnt;
			if (x<=sgt[now].tot)
			{
				printf("%d\n", sgt[now].val);
				return;
			}
			x-=sgt[now].tot;
			now = sgt[now].rc; // 跳到右子树上去
		}
	}
}

int pre(int now, int x, bool isfromrc) // 从sgt[now]中寻找x的前驱, isfromrc=true表示 now 是从它的右子树过来的，isfromrc=false表示now是从它的左子树过来的. 见图5，关于此方法的说明（这个方法花了我很多时间来理解,原因是一开始就把入参isfromrc的意义搞错了）
{
	if (!now) // 如果x比整棵替罪羊树中所有元素都小的话，则其实是不存在前驱的，则返回-INF
	{
		return -INF;
	}
	if (!isfromrc) // 如果是从左孩子来找now的, 则二话不说，继续找爹
	{
		return pre(sgt[now].parent, x, sgt[sgt[now].parent].rc == now);
	}
	if (sgt[now].valid && sgt[now].val < x) // 唯一可以直接返回的情形——没被删除并且符合前驱特性
	{
		return sgt[now].val;
	}
	if (sgt[now].lc) // 如果有左孩子，一路向右找极右子节点返回
	{
		now = sgt[now].lc;
		while(sgt[now].rc)
		{
			now = sgt[now].rc; // sgt[now]是极右子节点
		}
		return sgt[now].val;
	}
	return pre(sgt[now].parent, x, sgt[sgt[now].parent].rc == now); // 如果上面两种情况都不符合，则继续找爹
}

int nxt(int now, int x, bool isfromlc)  // sgt[now]中找x的后继
{
	if (!now) // 如果比整棵替罪羊树的所有节点都来的大, 则后继是INF
	{
		return INF;
	}
	if (!isfromlc) // 如果以右孩子的身份来找now的,直接继续找爹
	{
		return nxt(sgt[now].parent, x, sgt[sgt[now].parent].lc == now);
	}
	if (sgt[now].valid && sgt[now].val > x) 
	{
		return sgt[now].val;
	}
	if (sgt[now].rc) 
	{
		now = sgt[now].rc;
		while(sgt[now].lc)
		{
			now = sgt[now].lc; // 极左子节点
		}
		return sgt[now].val;
	}
	return nxt(sgt[now].parent, x, sgt[sgt[now].parent].lc == now); 
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int n, opt, x;
	scanf("%d", &n);
	while(n--)
	{
		scanf("%d%d", &opt, &x);
		if (opt == 1)
		{
			add(x);
		}
		if (opt == 2)
		{
			del(x);
		}
		if (opt == 3)
		{
			getrankofx(x);
		}
		if (opt == 4)
		{
			getnumberofrankx(x);
		}
		if (opt == 5)
		{
			printf("%d\n", pre(findx(root, x), x, true));  // 直接给true，是为了刚开始的时候pre方法是要检查一下是否当前节点（即findx(root,x)）满足x的前驱，如果是，则直接返回
		}
		if (opt == 6)
		{
			printf("%d\n", nxt(findx(root, x), x, true));
		}
	}
	return 0;
}

ac情况

评测状态

Accepted

100

用时: 439ms / 内存: 2688KB

​ 图1

图1中，根节点的size=5，validsize=4（因为它的左孩子已经处于删除状态），根节点的cnt=2+1+2+1=6（左孩子的tot=3不算，因为左孩子已经被删除）, tot表示数值出现了几次，例如根节点tot=2，表示根节点的val域出现了2次.

替罪羊树的思想可以使用下图表明

​ 图2

图2是一棵极度失衡的BST，那么之前讲过的平衡二叉树的处理手段都无外乎是两个字——旋转~ 但是SGT就比较粗放——暴力重建

即先将图2中的节点拍扁

​ 图3

然后分治重建

​ 图4

​ 图5

这里说一下pre方法的原理. 首先，我们要使用findx(root, x)找到x对应的now节点. 这个now节点存在以下三种可能

1. sgt[now]=x
2. sgt[now]>x, 而且sgt[now]已经没有左子树了（这是必然的，不然findx返回的就不会是now，这句话后面不再说了）
3. sgt[now]<x, 而且sgt[now]已经没有右子树了（这是必然的，不然findx返回的就不会是now，这句话后面不再说了）

正如findx一样，上述三种方法中都没有关于删是否删除的考虑. 上面三种可能中，只有一种情况是可以直接返回sgt[now].val的. 就是 sgt[now]<x && sgt[now].valid

如果不满足的话， 只存在以下几种可能

1. sgt[now]=x
2. sgt[now]>x，而且
3. sgt[now]<x 但是sgt[now]已经被删除了

对于情形2，因为没有左子树，所以只能找now的爸爸. 对于情形1和情形3，都可以先找它的左孩子的右孩子的右孩子的右孩子…的右孩子（此处省略一万个右孩子, 其实可以是0个右孩子），因为情形1和情形3都可能存在左孩子. 对于情形1和情形3，如果有左孩子的话，可以按照左孩子的一路右孩子的方式一路走到叶子，然后直接返回叶子. 因为叶子是不可能是删除状态的（因为会因为处于删除状态的节点过多而被rebuild，你去看代码中用beta的地方）. 如果没有左孩子呢? 那么和情形2一样，都要找now的爸爸.

所以，至此，我们清楚了——除了情形3中sgt[now]没被删除和情形1、情形3有左孩子这些情况可以直接返回之外，都需要跑去找sgt[now]的爸爸.

但是找爸爸归找爸爸，左孩子来找爸爸和右孩子来找爸爸得到的待遇是不一样的. 如果是左孩子来找爸爸的话，则只能继续找爸爸的爸爸（也就是找爷爷）. 因为x一定<爸爸的val（因为是从左孩子去找它的爸爸的），所以x要想大于点什么的话，只能继续往上找

即像下图这个样子

​ 图6

如果是以右孩子的身份来找爸爸P的话，则待遇就不一样了. 因为findx的过程曾经经过P的，而且当时在P的时候是选择了右边. 所以x一定是>sgt[P].val的. 所以我们要做的事情就是首先检测一下sgt[P]是否被删除，如果没被删除的话，直接返回即可. 如果被删除了, 则看看其左孩子是否有，如果有的话，一路向右找最右的右孩子，根据替罪羊树的重构算法，该极右的节点是不会是删除状态的. 即下图

​ 图7

图7如果Q处于被删除状态. 而且Q没有右孩子（Q是极右的），我们说这是不可能的. 首先，因为重构机制的存在，如果Q是删除的，那么Q就不可能存在左孩子，不然beta机制就会致使其重构. 而如果Q没有左孩子，而只是孤零零的一个挂在Q的父节点上，但是我们知道，根据重构的beta机制，至多扫描到Q这个节点就会将Q移除掉. 也不可能出现图8那种情况. 即A是失效节点，它有两个有效孩子B和C，因为 alpha我调整为了0.6（而不是网上大部分的0.75）, 如果是0.75的话，是可能出现图8情形的. 即A（失效节点）后面跟着两个有效节点（既不违反alpha规则，又不违反beta规则），但是按照nxt算法的话，找到的就是A这个失效节点了，而不是正确的B节点. 解决方法就是下调alpha为0.6, 这样的话，就不可能出现图8情形. 甚至极左子节点A是失效节点都不可能（不是违反alpha规则就是违反beta规则）.

回到之前的话题，如果有左孩子的话，就直接返回左孩子的极右子节点. 如果没有左孩子的话，则只能再继续找爹. 然后再根据到底是以左孩子的身份还是右孩子的身份找爹而区别对待. 如此往复. 如果一直找不到的，则这个x就比整个替罪羊树中所有的元素还小. 则返回-INF即可.

替罪羊树的前驱后继算法较为复杂的原因在于惰性删除

​ 图8

参考

【1】https://blog.csdn.net/a_forever_dream/article/details/81984236