本文主要是介绍无旋平衡树 fhq treap,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
普通平衡树
您需要写一种数据结构,来维护一些数,其中需要提供以下操作:
- 插入一个整数 x x x。
- 删除一个整数 x x x (若有多个相同的数,只删除一个)
- 查询整数 x x x 的排名(排名定义为比当前数小的数的个数 + 1 +1 +1。若有多个相同的数,因输出最小的排名)
- 查询排名为 x x x 的数
- 求 x x x 的前驱(前驱定义为小于 x x x,且最大的数)
- 求 x x x的后继(后继定义为大于 x x x,且最小的数)
fhq treap 是二叉搜索树。若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。但这棵树可能会是一条链,这会让操作的复杂度卡到线性。
那么 fhq treap 通过给结点赋一个随机数,当作这个点的优先级,通过随机化让平衡树尽可能的平衡。那么,应该如何维护 fhq treap 呢?
存储
需要以下变量来存储:
struct fhqtreap{int ch[N][2] /*0 为左儿子 1 为右儿子*/ , val[N] /*结点的值*/ , key[N] /*结点的优先级*/, sz[N] /* 以该结点为根的子树的大小(包括它本身)*/, root /*树的根*/, cnt /*结点个数*/;
} T;
信息上传
在进行一些操作的时候,可能要将儿子的信息传到父亲身上。
inline void pushup(int rt) {sz[rt] = sz[ch[rt][0]] + sz[ch[rt][1]] + 1; //以左儿子为根的子树 + 右儿子为根的子树 + 它本身即为 1
}
新建结点
新建一个结点。
inline int newnode(int v) { // v 为新建的结点的值sz[++cnt] = 1; val[cnt] = v; key[cnt] = rand()/*随机一个优先级*/;return cnt;
}
合并子树
要按照优先级来合并两个子树和二叉搜索树的性质左小右大,这里规定,如果子树 x x x 的优先级比 y y y 高( k e y x < k e y y key_x < key_y keyx<keyy),那么将子树 y y y 合并到子树 x x x 的右儿子上。否则,将子树 x x x 合并到子树 y y y 的左儿子上。合并之后,需要把改变后的信息上传到父结点。
int merge(int x, int y) {//将 x 和 y 合并返回合并后的子树的编号if (!x || !y) return x + y;//如果有任何一个子树为空,那么返回另一个(如果两个都是空返回 0)if (key[x] < key[y]) {ch[x][1] = merge(ch[x][1], y); //递归pushup(x); return x;} else {ch[y][0] = merge(x, ch[y][0]);pushup(y); return y;}}
分裂子树
有两个方法,一个是根据权值分,另一个是根据大小分。这道题最方便的方法是用权值分,大小分在文艺平衡树讲。将所有点权小于等于传入的参数的点分裂到左子树,其他的分裂到右子树。递归求解即可,最后将分裂后子树的信息上传。
void split(int rt, int v, int &x, int &y) {//将 rt 分成两棵子树 x 和 y,带 & 方便修改if (!rt) x = y = 0;else {if (val[rt] <= v) {x = rt; //分给右子树split(ch[rt][1], v, ch[rt][1], y);} else {y = rt; //分给左子树split(ch[rt][0], v, x, ch[rt][0]);}pushup(rt);//上传}}
插入结点
要将结点插入正确的位置。先把树分为 x , y x,y x,y 两部分,然后把新的结点看做是一棵树,先与 x x x 合并,合并完之后将合并的整体与 y y y 合并。
inline void insert(int v) { //新建权值为 v 的点int x, y; split(root, v, x, y); // x 中的点权小于等于 v,y 中的点权大于 vroot = merge(merge(x, newnode(v)), y); // 因为 x 的点权是 v,所以和 <= v 的子树 x 合并,再与 y 合并}
删除结点
首先把树分为 x x x 和 z z z 两部分,设删除结点的权值为 a a a,再把 x x x 分为 x x x 和 y y y 两部分,使得 x x x 中结点的权值全部小于 a a a, y y y 中的全部大于 a a a。这就相当于传进的参数 v = a − 1 v = a - 1 v=a−1。 而且呢,权值为 a a a 的结点正好是 y y y 树的根(左小右大根相等)。 然后可以无视 y y y 的根结点,直接把 y y y 的左右孩子合并起来,这样就成功的删除了根结点,最后再把 x , y , z x,y,z x,y,z 合并起来就好。
inline void del(int v) { // 删除权值为 v 的点int x, y, z;split(root, v, x, z); split(x, v - 1, x, y);y = merge(ch[y][0], ch[y][1]); // 将左右儿子合并,忽视了根结点root = merge(merge(x, y), z);
}
求一个数的排名
考虑二叉查找树的性质,左儿子的值比父亲的小,右儿子的值比父亲大。那么,一个数的排名就是所有比它小的数加上他自己。
inline int lev(int v) {int x, y, res;split(root, v - 1, x, y);res = sz[x] + 1;root = merge(x, y); //分裂后别忘合并return res;}
求排名为任意值的数
从根结点出发,左子树中的数都比根结点小,右边的数都比根结点大。因为是从小到大排名,所以左子树的大小为它占的排名,而左子树的大小加一为当前结点排名,右子树的大小占的是倒数的排名。所以看看排名是不是在左子树的大小内,是的话向左子树走,不是的话再看看是不是正好排名相等,如果相等返回当前结点的值,不相等那么一定在右子树,那么向右子树走,向右子树走时要将左子树大小加根节点大小所占的排名减掉。
inline int kth(int rt, int v) {while (1) { // 用 while 循环if (v <= sz[ch[rt][0]]) rt = ch[rt][0];else if (v == sz[ch[rt][0]] + 1)return val[rt];else {v -= sz[ch[rt][0]] + 1;rt = ch[rt][1];}}}
求一个数的前驱
因为要小于 a a a ,那么按照 a − 1 a-1 a−1 的权值分裂成 x x x 和 y y y , x x x 中最大的一定是 ≤ a − 1 \leq a - 1 ≤a−1的,所以直接输出 x x x 中最大的数即可。 x x x 中最大的数还是根据左小右大,那么是最后一个右儿子即为最后一个点。
inline int pre(int v) {int x, y, res;split(root, v - 1, x, y);res = kth(x, sz[x]); // x 中最大的数root = merge(x, y); // 分裂后一定合并return res;}
求一个数的后继
与求前驱相似,只需找 ≥ a \ge a ≥a 的最小的数就可以了。
inline int suf(int v) {int x, y, res;split(root, v, x, y);res = kth(y, 1);root = merge(x, y);return res;}
Link
文艺平衡树
您需要写一种数据结构,来维护一个有序排列,支持翻转区间的操作。
懒标记下传
直接更新所有的儿子往往会超时,所以要用懒标记,用一个数,这个数为 0 0 0 或 1 1 1,用来表示是否需要反转。
inl void pushdown(reg int rt) {if (tag[rt]) {swap(ch[rt][0], ch[rt][1]);if (ch[rt][0]) tag[ch[rt][0]] ^= 1;if (ch[rt][1]) tag[ch[rt][1]] ^= 1;tag[rt] = 0;}
}
分裂子树
设给定的大小为 v v v,那么把树分成大小为 v v v 与大小为 s z r t − v sz_{rt} - v szrt−v 的两棵树。那么分的策略就是:先找左子树,左子树多了分给右子树,不够去和右子树要。
void split(reg int rt, reg int pos, reg int &x, reg int &y) {if (!rt) x = y = 0;else {pushdown(rt);if (pos <= sz[ch[rt][0]]) {y = rt;split(ch[rt][0], pos, x, ch[rt][0]);} else {x = rt;split(ch[rt][1], pos - sz[ch[rt][0]] - 1, ch[rt][1], y);}pushup(rt);}}
区间反转
将树的 l − 1 l - 1 l−1 部分分给 x x x,那么 y y y 表示的区间为 [ y , n ] [y,n] [y,n]。再将 y y y 分裂出一个 z z z,长度为 r − l + 1 r - l + 1 r−l+1。
inl void rev(reg int l, reg int r) {reg int x, y, z;split(root, l - 1, x, y);split(y, r - l + 1, y, z);tag[y] ^= 1;root = merge(x, merge(y, z));
}
中序遍历
AVL 可以通过中序遍历得到反转后的序列。
void output(reg int rt) {if (!rt) return;if (tag[rt]) pushdown(rt);output(ch[rt][0]);printf("%d ", val[rt]);output(ch[rt][1]);
}
Link
可持久化文艺平衡树
您需要写一种数据结构,来维护一个序列,其中需要提供以下操作(对于各个以往的历史版本):
- 在第 p p p 个数后插入数 x x x 。
- 删除第 p p p 个数。
- 翻转区间 [ l , r ] [l,r] [l,r],例如原序列是 { 5 , 4 , 3 , 2 , 1 } \{5,4,3,2,1\} {5,4,3,2,1},翻转区间 [ 2 , 4 ] [2,4] [2,4] 后,结果是 { 5 , 2 , 3 , 4 , 1 } \{5,2,3,4,1\} {5,2,3,4,1}。
- 查询区间 [ l , r ] [l,r] [l,r] 中所有数的和。
和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本(操作 4 4 4 即保持原版本无变化),新版本即编号为此次操作的序号。
本题强制在线。
克隆结点
在每次合并与分裂的时候,需要新建一个结点修改,而不是在原来结点上修改。介绍一个小技巧,每次删除结点的时候,用一个队列记录这个点所占用的空间被 释放了,之后复制结点复制再这个位置上就可以了。
int clone(int y) {int x;if (!q.empty()) {x = q.front();q.pop();} else x = ++tot;t[x] = t[y];return x;
}
Link
这篇关于无旋平衡树 fhq treap的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!