文章目录
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;}