学习笔记 - 非旋Treap

其实是之前学习的内容了,自己也曾自学过。但是这一次更为透彻——


Part1. Treap 回顾

Treap 是一类平衡树,它的每个节点有两个键值 key,fix。既然叫 Treap,它即满足 “Tree”——

  1. 二叉排序树的性质:key 满足 “左儿子的key<根的key<右儿子的key”;
  2. 堆的性质(一般来说大根堆小根堆都可以,这里采用大根堆):fix 满足 “根的fix>左右儿子的fix”;

Treap 维持树平衡的秘诀就是 fix 的堆性质 —— 实现代码时,fix 往往是随机数决定的,这样就可以维护平衡树的 期望 深度为 $\log n$。

一般的 Treap,实现各种操作的方式类似于 Splay,是通过 Rotate() 实现的。Rotate() 有一个缺点,它会造成树的形态改变,因此很难实现 可持久化

而 Treap 的另一种 —— “非旋”Treap,既然不旋转,它主要依靠 Merge(u,v)Split(u) 两个函数实现各种操作。


Part2. 合并两棵 Treap - Merge(u,v)

Merge(u,v) 的两参数 u,v 表示要合并的两个 Treap 的根。两棵树能够直接合并当且仅当 u的所有点的key都小于v的所有点的key

如果fix[u]>fix[v],说明 v 应作为 u 的子树。因为 v 子树中的所有点的 key 都大于 key[u],所以 v 应作为 u 的右子树。于是递归合并 u 的右子树和 v,即 Merge(rch[u],v),注意 一定不能调换位置 ,因为合并的任意时刻都要使合并的两棵树中,前者的任何点的 key 小于后者任何点的 key

如果 fix[u]<fix[v],说明 u 是 v 的子树。同理,u 应作为 v 的左子树,于是递归合并 u 和 v 的左儿子,Merge(u,lch[v]),照样不能调换位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//u中所有树小于v中所有数
NODE *Merge(NODE *u,NODE *v){
if(u==NULL) return v;
if(v==NULL) return u;
if(u.val>v.val){
u->ch[1]=Merge(u->ch[1],v); //右子树
u->PushUp();
return u; //u成为两棵树合并后的根节点
}
else{
v->ch[0]=Merge(u,v->ch[0]); //!不能换位置
v->PushUp();
return v;
}
}

Part3. 将 Treap 分离为两个

Part3/1. 按节点数量分离

SplitSize(u,k) 表示把 u 中的前 $k$ 小的节点单独提出来建一棵 Treap,剩下的点也成为一棵 Treap。返回 两棵 Treap 的根,一般返回一个 pair<NODE*,NODE*>first是前 $k$ 小的节点的 Treap 的根。

那么就需要维护每个节点的大小 siz,其实跟平衡树查找第 $k$ 大的值差不多 ——

  1. 如果 u->ch[0]->siz>=k(左子树大小大于 $k$),说明前 $k$ 小全在左子树中,那么就递归到左子树。因为 u 是不属于前 $k$ 小的,应该接在第二棵 Treap 上,就把它作为第二棵 Treap 的根;
  2. 如果 u->ch[0]->siz<k,说明 左子树和根 u 都属于前 $k$ 小,就递归到右子树找前 k - u->ch[0]->siz - 1 小。因为 u 是前 $k$ 小中的,应该接在第一棵 Treap 上,就作为第一棵 Treap 的根;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef pair<NODE*,NODE*> DNODE;
DNODE SplitSize(NODE *u,int k){
DNODE Res(NULL,NULL);
if(u==NULL) return Res;
if(u->ch[0]->siz>=k){
Res=SplitSize(u->ch[0],k);
u->ch[0]=Res.second;Res.second=u; //把 u 作为第二棵树的根
}
else{
Res=SplitSize(u->ch[1],k-u->ch[0]->siz-1);
u->ch[1]=Res.first;Res.first=u; //把 u 作为第一棵树的根
}
u->PushUp();
return Res;
}

Part3/2. 按节点 key 分离

Split(u,k) 表示把 u 分离成小于等于 $k$ 和大于 $k$ 的两部分。返回值同 SplitSize(u,k)

其实就是利用二叉排序树:

  1. 如果 u 的 key 大于 $k$,就说明小于 $k$ 的数全在左子树,就递归到左子树;而 u 本身应该属于第二棵树,就把它作为第二棵树的根;
  2. 如果 u 的 key 小于等于 $k$,就说明 左子树和根 u 都属于第一棵树,于是递归到右子树求解;u 应作为第一棵树的根;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
DNODE Split(NODE *u,int k){
DNODE Res(NULL,NULL);
if(u==NULL) return Res;
if(u->key>k){
Res=Split(u->ch[0],k);
u->ch[0]=Res.second;Res.second=u;
}
else{
Res=Split(u->ch[1],k);
u->ch[1]=Res.first;Res.first=u;
}
u->PushUp();
return Res;
}

Part4. 其他操作

Part4/1. 插入节点

把该新节点 now 看成一棵只有一个点的树,但是我们不能直接 Merge(root,now),因为 nowroot 中每个值的大小不确定。

所以需要先把原树分成小于等于 now 的部分和大于 now 的部分,Split(root,now->key) 即可。然后再把这三棵树 按顺序 合并即可。

1
2
3
4
5
void Insert(int now){ //插入一个值为 now 的节点
NODE *p=NewNode(now); //从内存池中新建一个单独的节点,并赋予fix=rand()和key=now
DNODE Res=Split(root,now);
root=Merge(Merge(Res.first,p),Res.second);
}

Part4/2. 删除节点

要删除一个值为 val 的节点(保证存在)。可以这样操作:

  1. 将原树分离为小于 val(即小于等于 val-1)的和大于等于 val 的节点;
  2. 此时 val 是第二棵树中最小的元素;
  3. 因为只需要删除一个值为 val 的点,就再把第二棵树中的第一小(也就是 val)的点分出来就可以了;
  4. 最后将除了分离出来的 val 这个点,剩下的两棵树合并即可;
1
2
3
4
5
void Delete(int val){
DNODE Res1=Split(root,val-1); //val在Res1.second中
DNODE Res2=SplitSize(Res1.second,1); //Res2.first就是val
root=Merge(Res1.first,Res2.second); //将除了 Res2.first 的所有点都合并起来
}

Part4/3. 其他平衡树操作

和一般的平衡树一样,就不解释了……

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
NODE *FindKth(NODE *u,int k){ //找到第 k 小的点
if(u->ch[0]->siz>=k) return FindKth(u->ch[0],k);
if(u->ch[0]+1==k) return u;
return FindKth(u->ch[1],k-u->ch[0]->siz-1);
}
/*
常数更大的写法
NODE *FindKth(int k){
DNODE Res1=SplitSize(root,k-1);
DNODE Res2=SplitSize(Res1.second,1);
root=Merge(Res1.first,Merge(Res2.first,Res2.second));
return Res2.first;
}
*/
//下面 FindPre 和 FindNxt 都可以用一般的平衡树写,但是这样比较简单
NODE *FindPre(int val){ //前驱,严格小于 val 的最大数
DNODE Res1=Split(root,val-1);
DNODE Res2=SplitSize(Res1.first,Res1.first->siz-1);
root=Merge(Merge(Res2.first,Res2.second),Res1.second)
return Res2.second;
}
NODE *FindNxt(int val){ //后继,严格大于 val 的最大数
DNODE Res1=Split(root,val);
DNODE Res2=SplitSize(Res1.second,1);
root=Merge(Res1.first,Merge(Res2.first,Res2.second));
return Res2.second;
}

The End

Thank for reading!

Email: lucky_glass@foxmail.com,欢迎提问~

0%