隐藏
非旋转treap与可持久化平衡树学习笔记 | Bill Yang's Blog

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

0%

非旋转treap与可持久化平衡树学习笔记

发表于 更新于 分类于 Valine：

treap有许多种实现方式，具有动静结合的特点，这使它成为可持久化平衡树的优秀实现方式。

几个概念

treap

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

笛卡尔树

笛卡尔树就是treap，可以静态线性构造，常用于切换RMQ与LCA问题。

接口

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

非旋转treap

没有旋转的treap，因为treap的唯一接口是他的根，每个结点的子树仍然是一棵treap，和可并堆与主席树类似，这使得它可以静态的非旋转构造。
不采用旋转机制，而采用分裂合并机制是非旋转treap的核心。

可持久化treap

因为旋转类treap指针进行复杂的变化，故难以可持久化，而替罪羊树的重构更是可持久化代价巨大，故考虑对非旋转treap进行可持久化。

非旋转treap的操作

$newnode(v)$：创建一个新点，权值为$v$。

1
2
3
4
5
6
7
8
9
10
mt19937 g(rand());
struct Tree {
	int l,r,size;
	int val,d;
	Tree(int _l=0,int _r=0,int s=0,int v=0,int _d=0):l(_l),r(_r),size(s),val(v),d(_d) {}
};
int newnode(int v) {
	tree[++size]=Tree(0,0,1,v,g()%maxn);
	return size;
}

$split(x,n)$：将$x$为根的treap根据中序遍历拆分为前$n$个点和其余点构成的两棵treap，返回一个pair分别表示两棵treap的接口。

  • 若树为空（接口为$0$），返回$pair<0,0>$。
  • 若左子树的$size(ls(x))\ge n$，说明分界点在左子树中，当前点属于第二部分，令$lt=split(ls(x),n)$，维护指针与信息后返回$pair < lt.first,x >$。
  • 否则，说明分界点在右子树中，当前点属于第一部分，令$rt=split(rs(x),n-size(ls(x))-1)$，维护指针与信息后返回$pair < x,rt.second >$。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    pii split(int index,int num) {
    	if(!index)return mp(0,0);
    	int l=tree[index].l,r=tree[index].r;
    	if(num<=size(l)) {
    		pii lt=split(l,num);
    		tree[index].l=lt.second;
    		push_up(index);
    		return mp(lt.first,index);
    	} else {
    		pii rt=split(r,num-size(l)-1);
    		tree[index].r=rt.first;
    		push_up(index);
    		return mp(index,rt.second);
    	}
    }

$merge(x,y)$：将以$x$和$y$为接口的treap合并为一棵treap，返回合并后treap的接口。保证$x$子树的$key$小于$y$子树。

  • 若$x==0$或$y==0$，说明已经有一棵treap为空，返回另一棵。
  • 否则说明两棵treap都存在，此时我们有两种合并方式，第一种将$x$作为根在子树合并$y$，第二种将$y$作为根在子树合并$x$，这两种方案均可满足$key$有序，因此我们应该使用$d$来作为判断依据。
    • 若$d(x)<d(y)$，为了保持小根堆的性质，我们应该将根选为$x$。因此将$x$的右子树与$y$合并，维护信息后返回$x$。
    • 否则，我们应该将根选为$y$。因此将$y$的左子树与$x$合并，维护信息后返回$y$。
1
2
3
4
5
6
7
8
9
10
11
12
int merge(int a,int b) {
	if(!a||!b)return a+b;
	if(d(a)<d(b)) {
		tree[a].r=merge(tree[a].r,b);
		push_up(a);
		return a;
	} else {
		tree[b].l=merge(a,tree[b].l);
		push_up(b);
		return b;
	}
}

$find$_$rank(x,k)$：找到以$x$为接口的treap中排名为$k$的点。

平衡树基本操作

1
2
3
4
5
6
int find_rank(int index,int k) {
	if(!index)return 0;
	if(k<=size(tree[index].l))return find_rank(tree[index].l,k);
	else if(k==size(tree[index].l)+1)return index;
	else return find_rank(tree[index].r,k-size(tree[index].l)-1);
}

$get$_$rank(x,v)$：查询以$x$为接口的treap中值为$v$的排名。

平衡树基本操作

1
2
3
4
5
int get_rank(int index,int v) {
	if(!index)return 0;
	if(v<val(index))return get_rank(tree[index].l,v);
	else return size(tree[index].l)+1+get_rank(tree[index].r,v);
}

$insert(x,k,v)$：在以$x$为接口的treap中排名为$k$的点前插入一个新点，权值为$v$。

利用分裂与合并插入新点（注意保证中序有序）。

1
2
3
4
int insert(int index,int k,int v) {
	pii tmp=split(index,k-1);
	return merge(merge(tmp.first,newnode(v)),tmp.second);
}

$remove(x,k)$：在以$x$为接口的treap中删除排名为$k$的点。

利用分裂与合并删除点（注意保证中序有序）。

1
2
3
4
5
int remove(int x,int k) {
	pii a=split(x,k-1);
	pii b=split(a.second,1);
	return merge(a.first,b.second);
}

查询前驱后继

可以通过限制路径比较最小/大值来实现查询前驱后继，但要求提供treap的接口。

可持久化

将$split$和$merge$中间改为添加新点即可。

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
pii split(int index,int num) {
	if(!index)return mp(0,0);
	int l=tree[index].l,r=tree[index].r;
	int now=++size;
	tree[now]=tree[index];
	if(num<=size(l)) {
		pii lt=split(l,num);
		tree[now].l=lt.second;
		push_up(now);
		return mp(lt.first,now);
	} else {
		pii rt=split(r,num-size(l)-1);
		tree[now].r=rt.first;
		push_up(now);
		return mp(now,rt.second);
	}
}
int merge(int a,int b) {
	if(!a||!b)return a+b;
	int now=++size;
	if(d(a)<d(b)) {
		tree[now]=tree[a];
		tree[now].r=merge(tree[a].r,b);
	} else {
		tree[now]=tree[b];
		tree[now].l=merge(a,tree[b].l);
	}
	push_up(now);
	return now;
}

技巧

丽洁姐姐在论文中提供了一种尚未证明的通过概率进行合并的方法。

当$d$相同的点在treap中大量存在时，会导致treap严重失衡，此时我们可以使用概率进行合并，就是说认为有$\frac{size(a)}{size(a)+size(b)}$的概率使得$d(a)<d(b)$，故可以使用该概率进行交换。

将merge中的代码：

1
if(d(a)<d(b))

改为：

1
if(g()%(size(a)+size(b))<size(a))

是不是很神奇？
实际测试时发现采用了这样的算法后时间效率有所提升。

总结

非旋转treap具有好写、易调试的特点，可以完成大部分平衡树的操作，同时还可以进行可持久化，故对于简单的平衡树应用采用非旋转treap性价比很高。

对可持久化数据结构的思考

任何一个数据结构若看做线性结构，则可持久化相当于将线性结构拓展为二维平面。

但由于拓展为平面，状态量大幅度增加，因此能省的空间尽量省去，将没有修改的重复部分用指针指过去即可。

同时我们发现，这样用指针指向重复元素的方法可以使我们在$O(1)$时间内复制元素，这是可持久化数据结构的一个思路点。

因为可持久化数据结构呈二维形态，故在使用可持久化数据结构时需要对数据结构维护的信息与可持久化（二维拓展）的信息作出思考。如在使用主席树解决区间$k$大问题时，我们就是对值域建立线段树对位置可持久化。

目前我们学习到的可持久化数据结构有这些：

  • 可持久化线段树（主席树）：以根作为接口动态开点的线段树。
    • 可持久化数组：$O(\log n)$寻址，$O(\log n)$修改，$O(\log n)$批量修改，$O(1)$复制，$O(1)$清空。
      • 可持久化并查集：路径压缩无优化。
      • 可持久化栈：利用可持久化数组时间空间开销略大。
  • 可持久化平衡树（treap）：以根作为接口动态开点的treap。
    • 可持久化序列：$O(\log n)$插入删除，$O(\log n)$查询。
  • 可持久化链表：$O(1)$添加、删除、查询，$O(n)$清空。
    • 可持久化栈
  • 可持久化动态树（部分可持久化）
  • 可持久化图（smg？？）
相关文章
姥爷们赏瓶冰阔落吧~