隐藏
非旋转平衡树与重量平衡树学习笔记 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

非旋转平衡树与重量平衡树学习笔记

发表于 更新于 分类于 Valine：

某些不基于旋转或虽旋转但具有一定特殊性质的平衡树可以优美地解决一些旋转类平衡树所难以解决的问题，这一类平衡树往往具有特殊的定义或性质。

替罪羊树

替罪羊树是一棵不基于旋转机制的树，通过重构保证其平衡性。

定义（们）

一些记号

平衡常数$\alpha$

一个位于$[\frac12,1]$间的常数，可以在范围内任意指定，一般设置为$0.75$左右。

树$T$

将一棵二叉搜索树记为$T$，$T$也可以指这棵树的根节点。

深度$depth(x)$

将$x$到树根的距离记作$depth(x)$。

高度$h(x)$

将$x$到其最深的叶子结点的距离记为$h(x)$。

子树大小$size(x)$

将结点$x$的子树大小记作$size(x)$，认为$size(T)=n$。

$\alpha$大小平衡

若一棵二叉搜索树的结点$x$满足$\alpha\times size(x)\ge \max(size(ls(x)),size(rs(x)))$，我们称$x$是$\alpha$大小平衡的，显然当$\alpha\lt\frac12$时无意义。

$\alpha$高度平衡

若树$T$满足$h(T)\le\lfloor\log_\frac1\alpha n\rfloor$，则称$T$是$\alpha$高度平衡的，显然当$\alpha\gt1$时无意义。

替罪羊树的平衡

替罪羊树既满足$\alpha$大小平衡也满足$\alpha$高度平衡，因为不难发现这两种平衡是等价的：
因为有$\alpha\times size(x)\ge \max(size(ls(x)),size(rs(x)))$，因此对每一个结点有$size(x)\le\alpha^{depth(x)}n$，若在叶子结点，则有$depth(x)\le\log_\frac1\alpha n$，因此两种平衡可以看做等价。

若替罪羊树$T$不满足$\alpha$高度平衡，故我们一定能够找到一个结点$x$，$x$不满足$\alpha$大小平衡。
找到最靠近根的$x$，并对$x$的子树进行暴力重建，即提取出中序遍历重建为完全二叉树。

不难发现，替罪羊树在每次操作后都是平衡的。

时间复杂度证明

替罪羊树的每个操作时间复杂度均摊$\log n$，下面我们进行证明：

我们定义结点的势能函数为：
$\varphi(x)=\left|size(ls(x))-size(rs(x))\right|$。
定义树的势能函数为$\phi(T)=\sum_{x}\varphi(x)$。
当结点$x$不满足$\alpha$大小平衡时（设右儿子更大），有：
$size(rs(x))\gt\alpha size(x)$。
因为每次插入都会检查平衡性，所以不妨令上式处于临界点：
$size(rs(x))=\alpha size(x)$。
$\therefore size(rs(x))=\alpha (size(ls(x))+size(rs(x))+1)$
$\therefore (1-\alpha)size(rs(x))=\alpha(size(ls)+1)$
$\therefore size(rs(x))=\frac\alpha{1-\alpha}size(ls(x))+\frac\alpha{1-\alpha}$
因此$\varphi(x)=O(\frac{2\alpha-1}{1-\alpha}size(ls(x)))$

重构以$x$为根的子树代价$C(x)$为：$size(ls(x))+size(rs(x))+1=\frac1{1-\alpha}size(ls(x))+\frac\alpha{1-\alpha}$

显然$O(\varphi(x))=O(C(x))$，而每次插入一个结点的时候会使其所有祖先的势能函数$\pm1$，而势能函数足以支付重构代价，因此时间复杂度均摊$O(\log n)$。

操作（们）

结构定义

为了方便后面的代码，此处展示出一些基本框架。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct Tree {
	int child[2],father;
	int size,val;
	Tree() {}
	Tree(int l,int r,int f,int s,int v):father(f),size(s),val(v) {
		child[0]=l;
		child[1]=r;
	}
};
 
const double alpha=0.7;
Tree tree[maxn];
int root,size;
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define fa(x) tree[x].father
#define val(x) tree[x].val
#define size(x) tree[x].size
ScapeGoat_Tree() {
	tree[++size]=Tree(0,2,0,2,-INT_MAX); //哨兵
	tree[++size]=Tree(0,0,1,1,INT_MAX);
	root=1;
}
bool balance(int index) {
	return size(index)*alpha>=max(size(ls(index)),size(rs(index)));
}
bool checkson(int index) {
	return rs(fa(index))==index;
}
void push_up(int index) {
	size(index)=size(ls(index))+1+size(rs(index));
}

重构

替罪羊树有一种省空间的拍扁重构法，但省去$O(n)$的空间没有意义，因此我们提取出中序遍历后重建即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int index) {
	if(ls(index))dfs(ls(index));
	a[++cnt]=index;
	if(rs(index))dfs(rs(index));
}
int build(int Left,int Right) {
	if(Left>Right)return 0;
	int mid=(Left+Right)>>1,pos=a[mid];
	ls(pos)=build(Left,mid-1);
	rs(pos)=build(mid+1,Right);
	fa(ls(pos))=fa(rs(pos))=pos;
	push_up(pos);
	return pos;
}
void rebuild(int index) {
	cnt=0;
	dfs(index);
	int father=fa(index),side=checkson(index);
	int pos=build(1,cnt);
	tree[father].child[side]=pos;
	fa(pos)=father;
	if(index==root)root=pos;
}

插入

插入过程与Splay类似，插入后检查一下平衡性即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert(int v) {
	int now=root,father=0;
	while(now) {
		father=now;
		size(father)++;
		now=tree[now].child[val(now)<=v];
	}
	tree[now=++size]=Tree(0,0,father,1,v);
	if(father)tree[father].child[val(father)<=v]=now;
	int pos=0;
	for(int i=now; i; i=fa(i))
		if(!balance(i))pos=i;
	if(pos)rebuild(pos);
}

删除

如果是删除结点有两个儿子，直接将删除结点改为前驱（前驱一定在子树中），然后删除掉前驱。
如果是非叶子结点，修改指针后维护信息即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
void remove(int index) {
	if(ls(index)&&rs(index)) {
		int pre=ls(index);
		while(rs(pre))pre=rs(pre);
		val(index)=val(pre); //前驱复制
		index=pre; //删除前驱
	}
	int son=ls(index)?ls(index):rs(index),side=checkson(index);
	tree[fa(index)].child[side]=son;
	fa(son)=fa(index);
	for(int i=fa(index); i; i=fa(i))size(i)--;
	if(index==root)root=son;
}

寻找

寻找值为$val$的元素下标。

1
2
3
4
5
6
7
8
int find(int v) {
	int now=root;
	while(now) {
		if(val(now)==v)return now;
		else now=tree[now].child[val(now)<v];
	}
	return -1;
}

计算排名

计算值为$v$的元素排名。
注意因为没有处理相同元素，因此找到值相等不能立即退出。
因为有哨兵所以不+1

1
2
3
4
5
6
7
8
9
10
11
int rank(int v) {
	int now=root,ans=0;
	while(now) {
		if(v<=val(now))now=ls(now);
		else {
			ans+=size(ls(now))+1;
			now=rs(now);
		}
	}
	return ans;
}

查询第$k$小

和Splay一样，因为有哨兵所以$rank$要+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
int kth(int rank) {
	rank++;
	int now=root;
	while(now>0&&rank>=0) {
		if(ls(now)&&size(ls(now))>=rank)now=ls(now);
		else {
			if(rank<=size(ls(now))+1)return now;
			rank-=size(ls(now))+1;
			now=rs(now);
		}
	}
	return -1;
}

查询前驱后继

因为不能旋转，故只能从根开始比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int pre(int num) {
	int now=root,ans=-INT_MAX;
	while(now) {
		if(val(now)<num)ans=max(ans,val(now)),now=rs(now);
		else now=ls(now);
	}
	return ans;
}
int suc(int num) {
	int now=root,ans=INT_MAX;
	while(now) {
		if(val(now)>num)ans=min(ans,val(now)),now=ls(now);
		else now=rs(now);
	}
	return ans;
}

treap

treap是一个经典的基于旋转机制的平衡树，与Splay不同点在于，其每个结点包含的随机值具有堆的性质，这使得treap更加平衡，同时也有了许多神奇的性质。
同时treap还可以有非旋转与可持久化的拓展。

定义（们）

treap

treap是一棵二叉平衡树，其每个结点包含两个属性：$key$（键值）与$d$（随机值）。其中$key$满足二叉平衡树的性质，也就是说treap的中序遍历$key$是有序的，$d$满足堆的性质，也就是说treap是一个大/小根堆。

接口

如果我们可以从一个结点开始遍历得到整棵treap，我们就称这个结点是treap的接口。
因为treap没有维护父亲指针，因此treap的唯一接口是它的根。

treap的重量平衡

treap是重量平衡的，不妨证明treap插入与删除的时间复杂度。
不难发现，若$d$随机指定，treap的高度期望是$O(\log n)$的。
设插入点是$x$，设$x$旋转到了其祖先$k$的位置，因此我们需要使用$size(k)$的时间对信息进行重构，但这种情况发生在$x$的随机权值是$k$子树中最大/小的一个，这样的概率是$\frac1{size(k)}$的，故treap的期望旋转代价为$1$。
定位插入点的时间复杂度期望是$O(\log n)$的，故插入一个点的时间复杂度期望是$O(\log n)$的。
设我们要删除$x$点，直接重构接口为$x$的treap，因为一个点期望有$O(\log n)$个祖先，故祖先后代关系总共有$O(n\log n)$对，也就是说每个点的子树大小之和期望是$O(n\log n)$，因此每个点的子树大小期望是$O(\log n)$，故删除一个数的期望复杂度是$O(\log n)$。

操作（们）

结构定义

为了方便后面的代码，此处展示出一些基本框架。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
mt19937 g(rand());
 
struct Tree {
	int child[2];
	int d,val;
	int size;
};

Tree tree[maxn];
int size,root;
queue<int>Q; //garbage collection
#define d(x) tree[x].d
#define val(x) tree[x].val
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define root(x) tree[x].root
#define size(x) tree[x].size
void push_up(int index) {
	int ls=ls(index),rs=rs(index);
	size(index)=size(ls)+size(rs)+1;
}
int newnode(int val) {
	int now;
	if(!Q.empty()) {
		now=Q.front();
		Q.pop();
		ls(now)=rs(now)=0;
	} else now=++size;
	val(now)=val;
	d(now)=g()%maxn;
	size(now)=1;
	return now;
}

插入与旋转

因为不需要记录父亲指针，因此旋转与插入非常简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void rotate(int& index,bool side) {
	int son=tree[index].child[side^1];
	tree[index].child[side^1]=tree[son].child[side];
	tree[son].child[side]=index;
	push_up(index);
	push_up(son);
	index=son;
}
void insert(int& index,int val) {
	if(!index) {
		index=newnode(val);
		return;
	}
	bool side=val>val(index);
	int &son=tree[index].child[side];
	insert(son,val);
	size(index)++;
	if(d(index)<d(son))rotate(index,side^1);
}

重构与删除

删除一个元素，直接提取出中序遍历重构其子树。
因为重构需要重新分配编号，内存不确定要开多大，故使用垃圾回收保证$O(n)$内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int cnt,a[maxn];
void dfs(int index) {
	if(!index)return;
	if(ls(index))dfs(ls(index));
	a[++cnt]=val(index);
	Q.push(index);
	if(rs(index))dfs(rs(index));
}
int build(int Left,int Right) {
	if(Left>Right)return 0;
	int mid=(Left+Right)>>1,now=newnode(a[mid]);
	ls(now)=build(Left,mid-1);
	rs(now)=build(mid+1,Right);
	push_up(now);
	return now;
}
int rebuild(int index) {
	cnt=0;
	dfs(ls(index));
	dfs(rs(index));
	int pos=build(1,cnt);
	return pos;
}
void remove(int val) {
	int now=root,father;
	bool side;
	while(val(now)!=val) {
		father=now;
		size(now)--;
		if(val<val(now))now=ls(now),side=0;
		else now=rs(now),side=1;
	}
	int pos=rebuild(now);
	if(now!=root)tree[father].child[side]=pos;
	else root=pos;
}

计算排名

和替罪羊树一样，但无哨兵。

1
2
3
4
5
6
7
8
9
10
11
int rank(int val) {
	int now=root,ans=0;
	while(now) {
		if(val<=val(now))now=ls(now);
		else {
			ans+=size(ls(now))+1;
			now=rs(now);
		}
	}
	return ans+1;
}

查询第$k$小

和替罪羊树一样，但无哨兵。

1
2
3
4
5
6
7
8
9
10
11
12
int kth(int rank) {
	int now=root;
	while(now>0&&rank>=0) {
		if(ls(now)&&size(ls(now))>=rank)now=ls(now);
		else {
			if(rank<=size(ls(now))+1)return now;
			rank-=size(ls(now))+1;
			now=rs(now);
		}
	}
	return -1;
}

查询前驱后继

和替罪羊树一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int pre(int num) {
	int now=root,ans=-INT_MAX;
	while(now) {
		if(val(now)<num)ans=max(ans,val(now)),now=rs(now);
		else now=ls(now);
	}
	return ans;
}
int suc(int num) {
	int now=root,ans=INT_MAX;
	while(now) {
		if(val(now)>num)ans=min(ans,val(now)),now=ls(now);
		else now=rs(now);
	}
	return ans;
}

重量平衡树的应用

套数据结构

平衡树套线段树被认为是不可写的数据结构，因为带旋转的平衡树在旋转时无法快速维护内部线段树，但伴随着非旋转平衡树与重量平衡树的引入，这类数据结构便能方便的写出来了。
替罪羊树：暴力重构线段树
treap：暴力重构treap并合并线段树

例.带插入区间$k$小值

传送门

动态大小比较

利用重量平衡树，我们可以给树上每个结点一个值的映射（点$\rightarrow$值），使得值在任何时候满足中序遍历有序，这样我们就可以在$O(1)$的时间内比较两个已插入进平衡树的点的大小关系。
这类大小比较在实数中完全没有应用的必要，因此常常应用到字符串的比较中。

方法：
给每个结点定义一个实数区间，根的实数区间为$(0,1)$，对于区间为$(l,r)$的点$i$，$ls(i)$的区间为$(l,\frac{l+r}2)$，$rs(i)$的区间为$(\frac{l+r}2,r)$，每个点的映射就是它的实数区间的中点。

不难发现，这样的映射满足条件。
在插入的时候可能需要对一整个子树重新计算映射，故需要使用重量平衡树，时间复杂度：$O(\log n)$插入，$O(1)$查询。

例.没有人的算术

传送门

动态K-D树

因为K-D树的插入并不会影响K-D树的形态，只会影响其效率，因此我们可以采用和替罪羊树一样的思想。
给K-D树定义平衡常数，根据平衡常数判断是否需要重构K-D树。

后缀平衡树

后缀平衡树是一种比后缀自动机、后缀数组更为强大的处理字符串的工具。

后缀平衡树的建立采用增量算法：
考虑已有字符串$S$的后缀平衡树，现在我们在其开头插入字符$c$。（为什么不在末尾插入？这样会多出$O(n)$个后缀，而在前面插入只会多出$O(1)$个后缀）后缀平衡树中应该多出$cS$这个后缀，如果能够快速比较$cS$与平衡树中其他后缀的大小，我们就可以在平衡树中快速插入这个后缀。
利用二分+Hash可以做到$O(\log n)$比较，总时间复杂度$O(n\log^2n)$。

有没有更快的方法？

先比较两个后缀的首字母，若首字母不同可以直接得出大小关系，否则比较除去首字母的两个后缀大小，此时比较的两个后缀均在平衡树中存在，故可以使用上述“动态大小比较”的方法，做到$O(1)$比较大小关系，总时间复杂度$O(n\log n)$。

插入时间复杂度$O(n\log n)$，同样我们可以删除一个开头元素（后缀自动机不支持），还可以将后缀平衡树可持久化（后缀自动机只能暴力撤销），后缀平衡树的时间复杂度不依赖于字符集的大小。

例.Phorni

传送门

相关文章
姥爷们赏瓶冰阔落吧~