替罪羊树

替罪羊树？

替罪羊树是一种平衡二叉搜索树，在维护树的平衡时，不需要进行旋转操作，而是通过一种非常暴力的重构来保证树的平衡。

替罪羊树

参数定义

树结点的定义如下，需要记录左右子树的序号、当前结点的值、当前子树的大小、当前子树的真实大小以及当前结点是否存在。

当前子树的真实大小是指去掉被删除结点的大小，因为替罪羊树采用懒删除的思想，删除节点时不是真的马上删除，而是在下一次重构时才真的把结点删除，所以对于每一个结点来说，用exist标记该结点是否被删除。

struct node {
	int l, r, val;
	int size, fact;
	int exist;
}tree[maxn];

int cnt, root;

插入

插入操作非常的简单，与二叉搜索树没什么差别。其中insert()中的check()是检查是否需要重构来保证树的平衡的，之后会讲到，这里可以先忽略。

// 新建结点
void newnode(int &now, int val) {
	now = ++cnt;
	tree[now].val = val;
	tree[now].size = tree[now].fact = 1;
	tree[now].exist = 1;
}

// 插入
void insert(int &now, int val) {
	if (!now) {
		newnode(now, val);
		check(root, now);
		return;
	}
	tree[now].size++;
	tree[now].fact++;
	if (val < tree[now].val) insert(tree[now].l, val);
	else insert(tree[now].r, val);
}

删除

删除操作也非常的简单，找到该结点并且将exist标记改为0即可，同时也需要check()一下是否需要重构。

// 删除
void del(int now, int val) {
	if (tree[now].exist && tree[now].val == val) {
		tree[now].exist = 0;
		tree[now].fact--;
		check(root, now);
		return;
	}
	tree[now].fact--;
	if (val < tree[now].val) del(tree[now].l, val);
	else del(tree[now].r, val);
}

重构

判断是否需要重构

因为只有插入和删除操作会影响树的高度，所以只需要在插入和删除的函数里面调用check()函数来判断是否需要重构。而插入和删除操作只对树的一条链路有影响，所以重构时，我们在该链路上寻找需要重构的子树。

那么我们是从下往上找好呢还是从上往下找好呢？很显然是从上往下找好，因为从下往上找可能需要多次重构，而从上往下找到一颗子树需要重构那么剩下的都会在这一次重构中完成。

所以也可以看到我们在调用check()函数时，传递的参数是从root到now结点，即从上往下找。

check()函数非常的简单，只是一层简单的封装。

// 检查是否需要重构
void check(int &now, int end) {
	if (now == end) return;
	if (imbalence(now)) {
		rebuild(now);
		update(root, now);
		return;
	}
	if (tree[end].val < tree[now].val) check(tree[now].l, end);
	else check(tree[now].r, end);
}

判断是否平衡

我们如何判断替罪羊树是否平衡呢？

我们先定义一个平衡因子alpha，alpha的值必需取0.5~1.0之间，我这里取0.75，当满足下面两个条件的一个就需要重构了。

• 当子树的左子树或者右子树的size大于子树的size * alpha时
• 当子树被删除的结点数大于子树的size * 0.3的时，既tree[now].size - tree[now].fact > tree[now].size * 0.3

那么判断树是否平衡的函数也非常的好写了

const double alpha = 0.75;

// 判断是否不平衡
bool imbalence(int now) {
	if (max(tree[tree[now].l].size, tree[tree[now].r].size) > tree[now].size * alpha
			|| tree[now].size - tree[now].fact > tree[now].size * 0.3)
		return true;
	return false;
}

重构子树

替罪羊树是通过一种非常暴力的方式来进行重构的。

首先对需要重构的子树进行中序遍历，将未删除的结点加到vector里面，然后通过分治的方式，把中序遍历的结果“提”起来变成一颗树，就像下面这张图一样。

vector<int> v;	// 记录中序遍历的结果

// 对now为根的子树做中序遍历
void inoder(int now) {
	if (!now) return;
	inoder(tree[now].l);
	if (tree[now].exist) v.push_back(now);
	inoder(tree[now].r);
}

// 对中序遍历的结果重构
void lift(int l, int r, int &now) {
	if (l == r) {
		now = v[l];
		tree[now].l = tree[now].r = 0;
		tree[now].size = tree[now].fact = 1;
		return;
	}
	int mid = (l + r) >> 1;
    // 出现重复值时，要将重复值挂在右子树，所以需要while找最左边的重复值
	while (l < mid && tree[v[mid]].val == tree[v[mid-1]].val) mid--;
	now = v[mid];
    // 左子树可能为空，所以需要判断一下
	if (l < mid) lift(l, mid-1, tree[now].l);
	else tree[now].l = 0;
	lift(mid+1, r, tree[now].r);
	tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
	tree[now].fact = tree[tree[now].l].fact + tree[tree[now].r].fact + 1; 
}

// 对以now为根的子树重构
void rebuild(int &now) {
	v.clear();
	inoder(now);
    // 子树全被删除了，直接将该结点置空就好
	if (v.empty()) {
		now = 0;
		return;
	}
	lift(0, v.size()-1, now);
}

更新信息

重构子树后，需要对链路上未重构的结点的信息进行更新，操作也很简单，通过递归回溯的方式更新。

// 重构完后更新根到now链路上结点的信息
void update(int now, int end) {
	if (!now) return;
	if (tree[end].val < tree[now].val) update(tree[now].l, end);
	else update(tree[now].r, end);
	tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

获取值x的排名

排名的定义是值小于x的数的个数+1，在统计rank的值时，往左子树走时，是无贡献的，只有往右子树走时，才有左子树和根节点的贡献。

// 根据值获得排名，即比当前数小的个数+1
int getrank(int val) {
	int now = root, rank = 1;
	while(now) {
		if (val <= tree[now].val)
			now = tree[now].l;
		else {
            // 往右子树走，统计小于x的值的个数
			rank += tree[now].exist + tree[tree[now].l].fact;
			now = tree[now].r;
		}
	}
	return rank;
}

根据排名rank获取值val

与主席树求第k大时也很像。

// 根据排名获得值
int getnum(int rank) {
	int now = root;
	while (now) {
		if (tree[now].exist && tree[tree[now].l].fact + tree[now].exist == rank)
			break;
		else if(tree[tree[now].l].fact >= rank)
			now = tree[now].l;
		else {
			rank -= tree[tree[now].l].fact + tree[now].exist;
			now = tree[now].r;
		}
	}
	return tree[now].val;
}

x的前驱

// 找x的前驱，即小于x且最大的数
int getpre(int x) {
	return getnum(getrank(x) - 1);
}

x的后继

// 找x的后继，即大于x且最小的数
int getnext(int x) {
	return getnum(getrank(x + 1));
    // 注意这里为什么不是下面的写法
    // return getnum(getrank(x) + 1);
    // 这样写在出现重复数字时会出现错误，而getrank(x+1)是把所有x都包含进去了，不会出现错误。
}

洛谷P3369

洛谷P3369是平衡树的模板题

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

// 样例输出
106465
84185
492737

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 2e5+5;


struct node {
	int l, r, val;
	int size, fact;
	int exist;
}tree[maxn];

int cnt, root;
const double alpha = 0.75;	// 平衡因子
vector<int> v;	// 记录中序遍历的结果

// 新建结点
void newnode(int &now, int val) {
	now = ++cnt;
	tree[now].val = val;
	tree[now].size = tree[now].fact = 1;
	tree[now].exist = 1;
}

// 判断是否不平衡
bool imbalence(int now) {
	if (max(tree[tree[now].l].size, tree[tree[now].r].size) > tree[now].size * alpha
			|| tree[now].size - tree[now].fact > tree[now].size * 0.3)
		return true;
	return false;
}

// 对now为根的子树做中序遍历
void inorder(int now) {
	if (!now) return;
	inorder(tree[now].l);
	if (tree[now].exist) v.push_back(now);
	inorder(tree[now].r);
}

// 对中序遍历的结果重构
void lift(int l, int r, int &now) {
	if (l == r) {
		now = v[l];
		tree[now].l = tree[now].r = 0;
		tree[now].size = tree[now].fact = 1;
		return;
	}
	int mid = (l + r) >> 1;
	while (l < mid && tree[v[mid]].val == tree[v[mid-1]].val) mid--;
	now = v[mid];
	if (l < mid) lift(l, mid-1, tree[now].l);
	else tree[now].l = 0;
	lift(mid+1, r, tree[now].r);
	tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
	tree[now].fact = tree[tree[now].l].fact + tree[tree[now].r].fact + 1; 
}

// 对以now为根的子树重构
void rebuild(int &now) {
	v.clear();
	inorder(now);
	if (v.empty()) {
		now = 0;
		return;
	}
	lift(0, v.size()-1, now);
}

// 重构完后更新根到now链路上结点的信息
void update(int now, int end) {
	if (!now) return;
	if (tree[end].val < tree[now].val) update(tree[now].l, end);
	else update(tree[now].r, end);
	tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

// 检查是否需要重构
void check(int &now, int end) {
	if (now == end) return;
	if (imbalence(now)) {
		rebuild(now);
		update(root, now);
		return;
	}
	if (tree[end].val < tree[now].val) check(tree[now].l, end);
	else check(tree[now].r, end);
}

// 插入
void insert(int &now, int val) {
	if (!now) {
		newnode(now, val);
		check(root, now);
		return;
	}
	tree[now].size++;
	tree[now].fact++;
	if (val < tree[now].val) insert(tree[now].l, val);
	else insert(tree[now].r, val);
}

// 删除
void del(int now, int val) {
	if (tree[now].exist && tree[now].val == val) {
		tree[now].exist = 0;
		tree[now].fact--;
		check(root, now);
		return;
	}
	tree[now].fact--;
	if (val < tree[now].val) del(tree[now].l, val);
	else del(tree[now].r, val);
}

// 根据值获得排名，即比当前数小的个数+1
int getrank(int val) {
	int now = root, rank = 1;
	while(now) {
		if (val <= tree[now].val)
			now = tree[now].l;
		else {
			rank += tree[now].exist + tree[tree[now].l].fact;
			now = tree[now].r;
		}
	}
	return rank;
}

// 根据排名获得值
int getnum(int rank) {
	int now = root;
	while (now) {
		if (tree[now].exist && tree[tree[now].l].fact + tree[now].exist == rank)
			break;
		else if(tree[tree[now].l].fact >= rank)
			now = tree[now].l;
		else {
			rank -= tree[tree[now].l].fact + tree[now].exist;
			now = tree[now].r;
		}
	}
	return tree[now].val;
}

// 找x的前驱，即小于x且最大的数
int getpre(int x) {
	return getnum(getrank(x) - 1);
}

// 找x的后继，即大于x且最小的数
int getnext(int x) {
	return getnum(getrank(x + 1));
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int opt, x;
		scanf("%d%d", &opt, &x);
		if (opt == 1) insert(root, x);
		else if(opt == 2) del(root, x);
		else if(opt == 3) printf("%d\n", getrank(x));
		else if(opt == 4) printf("%d\n", getnum(x));
		else if(opt == 5) printf("%d\n", getpre(x));
		else printf("%d\n", getnext(x));
	}
	return 0;
}