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

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

0%

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

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??)
姥爷们赏瓶冰阔落吧~