【模板】Treap

Tree和Heap生了个孩子叫Treap

借鉴 模板 讲解

模板题

看了一上午才看明白，Treap = Tree + Heap，是棵弱平衡树。

一棵树同时具有二叉搜索树的性质和堆的性质，可以完成二叉搜索树和堆的操作。

有人曰：

Treap代码量小，速度较快

不能分裂合并，可以可持久化

挺好的东西。

于是我就学了。

可完成的操作：1.插入x

　　　　　　　2.删除x数(若有多个相同的数，因只删除一个)

　　　　　　　3.查询x数的排名(若有多个相同的数，因输出最小的排名)

　　　　　　　4.查询排名为x的数

　　　　　　　5.求x的前驱(前驱定义为小于x，且最大的数)

　　　　　　　6.求x的后继(后继定义为大于x，且最小的数)

说明：

son[k][0] 表示 k 的左儿子, son[k][1] 表示 k 的右儿子
size[k] 表示以 k 为根的子树的节点数
w[k] 表示节点 k 的权值
rnd[k] 表示节点 k 的优先级
g[k] 表示节点 k 的个数（有可能有重复的）

0.旋转

最关键的操作，运用了二进制优化，使左旋和右旋代码合并。

给张左旋右旋的图，可以通过这张图来推出左旋右旋代码。（来自百度百科）

1 //通过旋转来维护小根堆 2 //因为通过旋转根是会变的，所以得加 & 3 // x 为 0 是 右旋，x 为 1 是 左旋 4 //但是不必知道是左旋还是右旋 5 //只知道旋转一个节点的孩子就相当于把这个孩子旋转到父亲上 6 void turn(int &k, int x) 7
turn

1.插入x

可以看出，每次插入都是插入叶节点，所以直接递归处理就好。

同时注意更新size数组，通过旋转保持堆的性质。

1 void insert(int &k, int x)//小根堆_插入 2 11 size[k]++; 12 if(w[k] == x) g[k]++; 13 else if(w[k] < x) 14 18 else 19 23 }
insert

2.删除x

1.如果是叶子节点就直接删除

2.如果只有一个儿子，就子继父位

3.如果有两个儿子，就通过旋转，把较小儿子翻转到上面，把当前节点翻转到下面，知道当前节点为情况1或2

1 //通过旋转使得被删除点转移得到叶子节点上或只有一个儿子 2 void del(int &k, int x)//删除 3 13 //只有一个儿子, 直接继承 14 if(son[k][0] * son[k][1] == 0) k = son[k][0] + son[k][1]; 15 //旋转后须满足小根堆性质，所以右旋，旋转后 k 值改变，继续删除 16 else if(rnd[son[k][0]] < rnd[son[k][1]]) turn(k, 0), del(k, x); 17 //反之左旋 18 else turn(k, 1), del(k, x); 19 } 20 else 21 26 }
delete

3.查询x的排名

递归处理，具体细节看代码。

1 //查询x数的排名(若有多个相同的数，因输出最小的排名) 2 int get_rank(int k, int x) 3
find_rank

4.查询排名为x的数

递归处理，具体细节看代码。

1 //找第 x 大的数 2 int get_kth(int k, int x) 3
find_Kth

5.求x的前驱

递归处理，具体细节看代码。

1 // x 的前驱是比 x 小的数中最大的那个 2 void get_pre(int k, int x) 3
find_pre

6.求x的后继

递归处理，具体细节看代码。

1 // x 的后继是比 x 大的数中最小的那个 2 void get_suc(int k, int x) 3
find_suc

最后是凑字数的主程序

1 int main() 2 17 } 18 return 0; 19 }
main

完整代码

1 #include <cstdio> 2 #include <cstdlib> 3 4 using namespace std; 5 6 int n, root, ans, tot; 7 int son[100001][2], size[100001], w[100001], rnd[100001], g[100001]; 8 //son[k][0] 表示 k 的左儿子, son[k][1] 表示 k 的右儿子 9 //size[k] 表示以 k 为根的子树的节点数 10 //w[k] 表示节点 k 的权值 11 //rnd[k] 表示节点 k 的优先级 12 //g[k] 表示节点 k 的个数（有可能有重复的） 13 14 //通过旋转来维护小根堆 15 //因为通过旋转根是会变的，所以得加 & 16 // x 为 0 是 右旋，x 为 1 是 左旋 17 //但是不必知道是左旋还是右旋 18 //只知道旋转一个节点的孩子就相当于把这个孩子旋转到父亲上 19 void turn(int &k, int x) 20 29 30 void insert(int &k, int x)//小根堆_插入 31 40 size[k]++; 41 if(w[k] == x) g[k]++; 42 else if(w[k] < x) 43 47 else 48 52 } 53 54 //通过旋转使得被删除点转移得到叶子节点上或只有一个儿子 55 void del(int &k, int x)//删除 56 66 //只有一个儿子, 直接继承 67 if(son[k][0] * son[k][1] == 0) k = son[k][0] + son[k][1]; 68 //旋转后须满足小根堆性质，所以右旋，旋转后 k 值改变，继续删除 69 else if(rnd[son[k][0]] < rnd[son[k][1]]) turn(k, 0), del(k, x); 70 //反之左旋 71 else turn(k, 1), del(k, x); 72 } 73 else 74 79 } 80 81 //查询x数的排名(若有多个相同的数，因输出最小的排名) 82 int get_rank(int k, int x) 83 89 90 //找第 x 大的数 91 int get_kth(int k, int x) 92 98 99 // x 的前驱是比 x 小的数中最大的那个 100 void get_pre(int k, int x) 101 106 107 // x 的后继是比 x 大的数中最小的那个 108 void get_suc(int k, int x) 109 114 115 int main() 116 131 } 132 return 0; 133 }
View Code

上一篇：【模板】划分树

下一篇：[HDU4417]Super Mario（主席树+离散化）

---

模板 堆 平衡树 Treap