替罪羊树模板

  • 2018-04-09
  • 0

突然发现一个月没写 Blog 了,滚回来补锅。。据说要补 30+ 篇 ?!! 就当复习吧。。

替罪羊树 (Scapegoat Tree) 是一棵基于局部重构 (partially rebuild) 的平衡树。

其主要思想是当一棵子树的不平衡程度到达某一阈值时,将该子树拍扁 (flatten) 成中序遍历,然后从中部上拉 (pullup) 成一棵完全二叉树。

由于没有旋转 (rotate) 或者分裂合并 (split & merge) 操作,替罪羊树在删除节点时并不是将节点移除,而是打上标记,在统计时不计入答案即可。我们用 cov[] 表示子树总节点数sz[] 表示子树真正存在的节点数

关于上述阈值的选取,对于任意节点作为根节点,均遵循以下规则:

  • 当左子树(或右子树)的总节点数大于整棵树总节点数的 α 倍时,认定当前树不平衡,需要重构。其中 α 通常选取 [0.6, 0.8] 区间上的数。
    • max(cov[lc[u]], cov[rc[u]]) > cov[u] * α
  • 当整棵树中被删除的节点数大于总节点数的一半时,认定当前树冗余信息过多,需要重构。
    • sz[u] * 2 < cov[u]

需要注意的是,insert() 的返回值为指向需重构子树的根节点的指针。另外,由于删除标记的影响,erase() 若按值删除则可能无法判断目标在左子树还是右子树内,需要按排名删除

替罪羊树复杂度可以证明为均摊单次 O(logn),且常数较 Treap, Splay 等均更优越。其局限性为不支持区间操作,只能实现名次树。

模板题为 BZOJ 3224 普通平衡树

Code: O(nlogn) [6964K, 324MS]

// 替罪羊树 (2018.3.5)
// BZOJ 3224 普通平衡树 
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<algorithm>
#define MAXN 100005
using namespace std;

inline void getint(int &num){
	char ch; bool neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
	if(neg) num = -num;
}

int n, opt, x;
int root, val[MAXN << 1], sz[MAXN << 1], cov[MAXN << 1], lc[MAXN << 1], rc[MAXN << 1];
bool exi[MAXN << 1];
int fl[MAXN << 1], topfl;
int bin[MAXN << 1], topbin = 0;

inline int newNode(int v, int s, int c, int l, int r){
	static int topp = 0;
	int u = topbin ? bin[topbin--] : ++topp;
	val[u] = v, sz[u] = s, cov[u] = c, lc[u] = l, rc[u] = r, exi[u] = 1;
	return u;
}

inline void delNode(int u) {bin[++topbin] = u;}

inline bool balanced(int u) {return max(cov[lc[u]], cov[rc[u]]) <= cov[u] * 0.75 + 5;}  // 平衡因子取 0.75

inline void update(int u) {sz[u] = sz[lc[u]] + sz[rc[u]] + exi[u], cov[u] = cov[lc[u]] + cov[rc[u]] + 1;}

inline void flatten(int u){
	if(lc[u]) flatten(lc[u]);
	if(exi[u]) fl[++topfl] = u; else delNode(u);
	if(rc[u]) flatten(rc[u]);
}

inline int pullup(int l, int r){
	if(l > r) return 0;
	int mid = l + r >> 1, u = fl[mid];
	lc[u] = pullup(l, mid - 1), rc[u] = pullup(mid + 1, r);
	return update(u), u;
}

inline void rebuild(int &u) {topfl = 0, flatten(u), u = pullup(1, topfl);}

inline int* insert(int &u, int v){
	if(!u) return u = newNode(v, 1, 1, 0, 0), (int*)NULL;
	else{
		sz[u]++, cov[u]++; int *sub;
		if(v < val[u]) sub = insert(lc[u], v);
		else sub = insert(rc[u], v);
		return balanced(u) ? sub : &u;
	}
}

//inline void erase(int u, int v){  // Erase with value
//	if(!u) return;
//	sz[u]--;
//	if(exi[u] && v == val[u]) {exi[u] = 0; return;}
//	else{
//		if(v < val[u]) erase(lc[u], v);
//		else erase(rc[u], v);
//	}
//}
/* Wrong Answer - Cannot assert whether v is in the left or right subtree when (exi[u] == false && v == val[u]). */ 

inline void erase(int u, int k){  // Erase with rank 
	sz[u]--;
	if(exi[u] && k == sz[lc[u]] + 1) {exi[u] = 0; return;}
	else{
		if(k <= sz[lc[u]] + exi[u]) erase(lc[u], k);
		else erase(rc[u], k - sz[lc[u]] - exi[u]);
	}
}

inline int rnk(int u, int v){
	int res = 1;
	while(u){
		if(v <= val[u]) u = lc[u];
		else res += sz[lc[u]] + exi[u], u = rc[u];
	}
	return res;
}

inline int kth(int u, int k){
	while(u){
		if(exi[u] && k == sz[lc[u]] + 1) return val[u];
		if(k <= sz[lc[u]]) u = lc[u];
		else k -= sz[lc[u]] + exi[u], u = rc[u];
	}
}

int main(){
	getint(n);
	for(register int i = 1; i <= n; i++){
		getint(opt), getint(x);
		if(opt == 1){
			int *p = insert(root, x);
			if(p) rebuild(*p);
		}
		else if(opt == 2){
			erase(root, rnk(root, x));
			if(sz[root] * 2 < cov[root]) rebuild(root);
		}
		else if(opt == 3) printf("%d\n", rnk(root, x));
		else if(opt == 4) printf("%d\n", kth(root, x));
		else if(opt == 5) printf("%d\n", kth(root, rnk(root, x) - 1));
		else if(opt == 6) printf("%d\n", kth(root, rnk(root, x + 1)));
	}
	return 0;
}



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai