学习笔记 - 非旋Treap | Lucky_Glass's Blog

以心为名，名为爱惜

0%

学习笔记 - 非旋Treap

发表于 更新于 分类于 Valine：

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

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)，因为 now 和 root 中每个值的大小不确定。

所以需要先把原树分成小于等于 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，欢迎提问~