文章目录
Treap = Tree + Heap (树堆 = 树 + 堆)1. 例题1 洛谷P3369 【模板】普通平衡树1. 结构体定义如下2. 向上更新`以u为根的树的节点个数`3. 旋转操作 route4. 插入操作 insert5. 删除操作 del6. 查询排名rand_x7. 查询 K 小值 kth8. 求key的前驱 get_pre9. 求key的后继 get_suf完整代码扩展应用1. 线段树套平衡树，求区间前驱后继排名(就是线段树的每个节点都是一个平衡树)2. 伸展树, 区间反转分割3. 双端优先队列的实现 (可以 取最大最小值的堆)4. 游戏排名系统 (动态数据容器) [原文链接/yang_yulei/article/details/46005845](/yang_yulei/article/details/46005845)Treap = Tree + Heap (树堆 = 树 + 堆)
大佬的博客/blog/HOJQVFNA/qian-xi-treap-ping-heng-shu
简介 : 本质上是一种使用 随机权值维护堆的性质的二叉查找树, 通过基础的树旋转维持堆的性质,
由随机权值保证树高度为 logN
具体做法 : 插入或删除后, 若不满足 堆的性质 则旋转
优点 : 防止 退化成链表 简单好写, 是最好写的平衡树之一, 好理解
缺点 : 常数大
1. 例题1 洛谷P3369 【模板】普通平衡树
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入 x 数 (插入值)
2. 删除 x 数(若有多个相同的数，因只删除一个)
3. 查询 x 数的排名(排名定义为比当前数小的数的个数 +1 )
4. 查询排名为 k 的数 (求K小值)
5. 求 x 的前驱 (前驱定义为小于 x，且最大的数)
6. 求 x 的后继 (后继定义为大于 x，且最小的数)
1. 结构体定义如下
#define lson(u) (tree[u].chl[0])#define rson(u) (tree[u].chl[1])struct Node {int chl[2],//chl[0]是左儿子 , chl[1]是右儿子val, //节点值sz, //以该节点的为根节点个数recy, //该节点重复了几次rnd; //随机优先级 } tree[MAXN<<4];
2. 向上更新以u为根的树的节点个数
当前节点u的sz = 左子树sz + 右子树sz +u的重复次数recy(U)inline void push_up(int u) {//更新节点以u为根的树的节点个数tree[u].sz = tree[lson(u)].sz + tree[rson(u)].sz + tree[u].recy;}
3. 旋转操作 route
我们可以把左旋和右旋合并成为一个统一的函数通过传入的操作数cmd实现相应的旋转#define LROUTE 0#define RROUTE 1void route(int& u, int cmd) {//cmd=0左旋, cmd=1右旋int tmp = tree[u].chl[cmd^1];tree[u].chl[cmd^1] = tree[tmp].chl[cmd];tree[tmp].chl[cmd] = u;push_up(u), push_up(tmp); //不要忘了更新对应的szu = tmp;}
4. 插入操作 insert
和普通BST一样的插入, 并建立随机权值即可插入后, 需要向上更新节点的 以该节点的为根节点个数szvoid insert(int& u, int key) {if(!u) {//走到叶子就新建节点u = ++tot;tree[u].sz = tree[u].recy = 1;tree[u].val = key;tree[u].rnd = rand(); //随机权值return ;}tree[u].sz ++;if(key == tree[u].val) {tree[u].recy ++; return ; }int cmd = (key > tree[u].val); //大于则向右插入insert(tree[u].chl[cmd], key);//插入后维护大根堆的性质//失衡的时候, 往与插入相反的方向旋转if(tree[u].rnd < tree[tree[u].chl[cmd]].rnd)route(u, cmd^1);push_up(u);}
5. 删除操作 del
和普通的BST一样的删除, 分为 4种情况 没有这值为 key 的节点, 直接返回当前根和key不相等, 就去相应的子节点解决叶子节点, 直接删除有左儿子, 没有右儿子, 右旋并去右儿子解决 (因为右旋后root转到了rig)没有左儿子, 有右儿子, 左旋并去左儿子解决(因为左旋后root转到了lef)左右都有, 就把 大的转上来 并去 另一个儿子 解决 使用 堆删除的方式, 把key旋转到叶子 节点后删除void del(int& u, int key) {if(!u) return ;if(key < tree[u].val) del(lson(u), key);else if(key > tree[u].val) del(rson(u), key);else {//4种删除情况if(!lson(u) && !rson(u)) {//叶子节点直接删除tree[u].sz --,tree[u].recy --;if(tree[u].recy == 0) u = 0;} else if(lson(u) && !rson(u)) {//只有左节点route(u, 1);del(rson(u), key);} else if(!lson(u) && rson(u)) {//只有右节点route(u, 0);del(lson(u), key);} else if(lson(u) && rson(u)) {//左右都有//把大的那个转上来，并去另一个子树解决int cmd = (tree[lson(u)].rnd > tree[rson(u)].rnd);route(u, cmd);del(tree[u].chl[cmd], key);}}push_up(u);}
6. 查询排名rand_x
还是比较key, 小于往左, 大于往右往右说明 root的左儿子中的所有节点都 小于key所以排名应加上 左儿子的节点的个数 和 根节点的重复次数
int rank_x(int u, int key) {//求key的排名if(!u) return 0;if(key == tree[u].val) //返回左子树个数 + 1return tree[lson(u)].sz + 1;else if(key < tree[u].val) //小于就去左子树找return rank_x(lson(u), key);else //大于就去右子树, 类似于权值线段树return tree[lson(u)].sz +tree[u].recy +rank_x(rson(u), key);}
7. 查询 K 小值 kth
如果左子树节点个数大于等于 k , 说明 k 小值还在左子树如果左子树的节点个数加上根的重复次数仍然小于 k, 说明k小值在右子树int kth(int u, int k) {//查询k小值if(!u) return 0;if(tree[lson(u)].sz >= k) return kth(lson(u), k);else if(tree[lson(u)].sz + tree[u].recy < k)return kth(rson(u), k-tree[lson(u)].sz-tree[u].recy);else return tree[u].val;}
8. 求key的前驱 get_pre
只要根仍然大于等于key, 就向左子树找向右走记得取max, 前驱定义为小于key，且最大的数int get_pre(int u, int key) {if(!u) return -INF;if(key <= tree[u].val) return get_pre(lson(u), key);elsereturn max(tree[u].val, get_pre(rson(u), key));}
9. 求key的后继 get_suf
int get_suf(int u, int key) {if(!u) return INF;if(key >= tree[u].val) return get_suf(rson(u), key);elsereturn min(tree[u].val, get_suf(lson(u), key));}
完整代码
// #define debug#ifdef debug#include <time.h>#include "win_majiao.h"#endif#include <iostream>#include <algorithm>#include <vector>#include <string.h>#include <map>#include <set>#include <stack>#include <queue>#include <math.h>#define MAXN ((int)1e5+7)#define ll long long int#define INF (0x7f7f7f7f)#define QAQ (0)using namespace std;typedef vector<vector<int> > VVI;#define show(x...) \do { \cout << "[" << #x << " -> "; \err(x); \} while (0)void err() {cout << "]" << endl; }template<typename T, typename... A>void err(T a, A... x) {cout << a << ' '; err(x...); }namespace FastIO{char print_f[105];void read() {}void print() {putchar('\n'); }template <typename T, typename... T2>inline void read(T &x, T2 &... oth) {x = 0;char ch = getchar();ll f = 1;while (!isdigit(ch)) {if (ch == '-') f *= -1; ch = getchar();}while (isdigit(ch)) {x = x * 10 + ch - 48;ch = getchar();}x *= f;read(oth...);}template <typename T, typename... T2>inline void print(T x, T2... oth) {ll p3=-1;if(x<0) putchar('-'), x=-x;do{print_f[++p3] = x%10 + 48;} while(x/=10);while(p3>=0) putchar(print_f[p3--]);putchar(' ');print(oth...);}} // namespace FastIOusing FastIO::print;using FastIO::read;int n, m, Q, K, root, tot;#define lson(u) (tree[u].chl[0])#define rson(u) (tree[u].chl[1])struct Node {int chl[2], //chl[0]是左儿子 , chl[1]是右儿子val, //节点值sz, //该节点的为根节点个数recy, //该节点重复了几次rnd; //随机优先级 } tree[MAXN<<4];void push_up(int u) {//更新节点以u为根的树的节点个数tree[u].sz = tree[lson(u)].sz + tree[rson(u)].sz + tree[u].recy;}#define LROUTE 0#define RROUTE 1void route(int& u, int cmd) {//cmd=0左旋, cmd=1右旋int tmp = tree[u].chl[cmd^1];tree[u].chl[cmd^1] = tree[tmp].chl[cmd];tree[tmp].chl[cmd] = u;push_up(u), push_up(tmp);u = tmp;}void insert(int& u, int key) {if(!u) {u = ++tot;tree[u].sz = tree[u].recy = 1;tree[u].val = key;tree[u].rnd = rand(); //随机权值return ;}tree[u].sz ++;if(key == tree[u].val) {tree[u].recy ++; return ; }int cmd = (key > tree[u].val); //大于则向右插入insert(tree[u].chl[cmd], key);//插入后维护大根堆的性质//失衡的时候, 往与插入相反的方向旋转if(tree[u].rnd < tree[tree[u].chl[cmd]].rnd)route(u, cmd^1);push_up(u);}void del(int& u, int key) {if(!u) return ;if(key < tree[u].val) del(lson(u), key);else if(key > tree[u].val) del(rson(u), key);else {//4种删除情况if(!lson(u) && !rson(u)) {//叶子节点直接删除tree[u].sz --,tree[u].recy --;if(tree[u].recy == 0) u = 0;} else if(lson(u) && !rson(u)) {//只有左节点route(u, 1);del(rson(u), key);} else if(!lson(u) && rson(u)) {//只有右节点route(u, 0);del(lson(u), key);} else if(lson(u) && rson(u)) {//左右都有//把大的那个转上来，并去另一个子树解决int cmd = (tree[lson(u)].rnd > tree[rson(u)].rnd);route(u, cmd);del(tree[u].chl[cmd], key);}}push_up(u);}int rank_x(int u, int key) {//求key的排名if(!u) return 0;if(key == tree[u].val) //返回左子树个数 + 1return tree[lson(u)].sz + 1;else if(key < tree[u].val) //小于就去左子树找return rank_x(lson(u), key);else //大于就去右子树, 类似于权值线段树return tree[lson(u)].sz +tree[u].recy +rank_x(rson(u), key);}int kth(int u, int k) {//查询k大值if(!u) return 0;if(tree[lson(u)].sz >= k) return kth(lson(u), k);else if(tree[lson(u)].sz + tree[u].recy < k)return kth(rson(u), k-tree[lson(u)].sz-tree[u].recy);else return tree[u].val;}int get_pre(int u, int key) {if(!u) return -INF;if(key <= tree[u].val) return get_pre(lson(u), key);elsereturn max(tree[u].val, get_pre(rson(u), key));}int get_suf(int u, int key) {if(!u) return INF;if(key >= tree[u].val) return get_suf(rson(u), key);elsereturn min(tree[u].val, get_suf(lson(u), key));}signed main() {#ifdef debugfreopen("test.txt", "r", stdin);clock_t stime = clock();#endifread(n);int cmd, val, ans;for(int i=1; i<=n; i++) {read(cmd, val);switch (cmd) {case 1:insert(root, val);break;case 2:del(root, val);break;case 3:ans = rank_x(root, val);printf("%d\n", ans);break;case 4:ans = kth(root, val);printf("%d\n", ans);break;case 5:ans = get_pre(root, val);printf("%d\n", ans);break;case 6:ans = get_suf(root, val);printf("%d\n", ans);break;default:break;}}#ifdef debugclock_t etime = clock();printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);#endif return 0;}
![P3835-[模板]可持久化平衡树【无旋Treap】](https://www.400zi.cn/uploadfile/img/14/875/9e372e4d37d5c58546d0d441b50b2155.jpg)
