旋转treap

treap = tree + heap，就比 BST 多了几行代码。

前言

无旋 treap。
默认读者会 BST 的基本操作、堆的定义。
如果没有特殊声明，本文的 treap 都指旋转 treap。
本文使用的是小根堆。

思想

treap 既是一棵二叉查找树（tree），也是一个二叉堆（heap）。
但是如果这两个数据结构用同一个权值维护，那么这两种数据结构是矛盾的。
所以 treap 用了一个很巧妙的方式：给每个节点附加一个随机的优先级，让权值满足二叉查找树的结构，让优先级满足二叉堆的结构。
这个就是一棵 treap（黑色是权值，蓝色是随机的优先级）：

由于优先级只能随机赋予，堆不一定是一颗完全二叉树，所以 treap 是弱平衡（近似平衡）的。

旋转

在不改变中序遍历的情况下，旋转可以改变树的结构。
在 treap 中，我们用旋转来满足二叉堆，控制树高。
图中从左到右是右旋，从右到左是左旋。

我们来模拟一下右旋的过程（左旋同理）。

在实现中，我会把左右旋放在一起写。

void rotate(int&now, int dir){  
    int t = d[now].ch[dir];  
    d[now].ch[dir] = d[t].ch[!dir];  
    d[t].ch[!dir] = now;  
    pushup(now), pushup(t), now = t;  //now 是 t 的儿子了，先更新 now 再更新 t
}

这里的 rotate(x, 0) 表示将 $ls_{x}$ 提到 $x$ 的高度，即右旋。
这里的 rotate(x, 1) 表示将 $rs_{x}$ 提到 $x$ 的高度，即左旋。

基础操作

节点变化

我们要在定义的时候添加一个优先级，然后在新建时给他赋随机值。

//需要头文件 <random>，<chrono>
std::mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());
struct node{
    int ch[2], size, val, rank;
}d[N];
int newnode(int x){
    int w = ++tot;
    d[w].val = x, ls(w) = rs(w) = 0, d[w].size = 1, d[w].rank = rd();
    return w;
}

插入

只有在插入的那个子树的优先级可能变化。
如果优先级比当前节点小，那么我们把它旋转上来。
记得更新节点。

void insert(int&now, int val){
    if(!now)return void(now = newnode(val));
    int dir = d[now].val < val;
    insert(d[now].ch[dir], val);
    if(d[d[now].ch[dir]].rank < d[now].rank)rotate(now, dir);
    if(now)pushup(now);
}

删除

这里我们需要改变一下目标节点有两个儿子的时候的方法。
我们比较两个儿子的优先级，把优先级小的旋转上来。
那么目标节点就到当前节点的另一侧，继续删除即可。
返回时要更新节点。

void del(int&now, int val){
    if(!now)return;
    if(d[now].val == val){
        if(ls(now) && rs(now)){
            int z = d[rs(now)].rank < d[ls(now)].rank;//哪边的优先级小
            rotate(now, z), del(d[now].ch[!z], val);//删除另一侧
        }
        else now = ls(now) ? ls(now) : rs(now);
    }
    else if(d[now].val < val)del(rs(now), val);
    else del(ls(now), val);
    if(now)pushup(now);//牢记
}

代码

P3369。

可持久化

不知道什么是可持久化的戳这。
只需要在所有要修改节点的地方新建节点，有注释的是新加句子。
完整代码。
修改片段：

void copynode(int &i){if(i)d[++tot] = d[i], i = tot;}//************
void rotate(int&now, int dir){
		int t = d[now].ch[dir];
		copynode(t);//**************  now节点已经新建过了
        d[now].ch[dir] = d[t].ch[!dir];
        d[t].ch[!dir] = now;
        pushup(now), pushup(t), now = t;
	}
	void insert(int&now, int val){
		copynode(now);//****************
		if(!now)return void(now = newnode(val));
		int dir = d[now].val < val;
		insert(d[now].ch[dir], val);
		if(d[d[now].ch[dir]].rank < d[now].rank)rotate(now, dir);
		if(now)pushup(now);
	}
	void del(int&now, int val){
		copynode(now);//****************
		if(!now)return;
		if(d[now].val == val){
			if(ls(now) && rs(now)){
				int z = d[rs(now)].rank > d[ls(now)].rank;
				rotate(now, z), del(d[now].ch[!z], val);
			}
			else now = ls(now) ? ls(now) : rs(now);
		}
		else if(d[now].val < val)del(rs(now), val);
		else del(ls(now), val);
		if(now)pushup(now);
	}

学习笔记：旋转treap

前言

思想

旋转

基础操作

节点变化

插入

删除

代码

可持久化