上文介绍了普通的平衡树,它简单(奇怪,鬼畜)的旋转操作确实死难写也难调(刚写挂一个),于是跑去学了一个不用旋转的平衡树,无旋 \(Treap (FHQ~~Treap)\)
只需要两个操作达到 \(bst,treap,splay\) 全部功能 ?? 太炫酷了
\(FHQ~~Treap\) 和普通的 \(Treap\) 一样每个节点维护两个值,一个是权值,一个是随机值
但是它不再是用旋转来维护,而是通过 \(split\) 和 \(merge\) 进行维护
把一个 \(Treap\) 分成两个
两种:按权值分,按子树大小分
复杂度 \(O(log n)\)
把权值小于 \(k\) 的节点都分到一棵树中,其余的点都分到另一棵树中
设第一棵树的权值小于第二棵树
如果当前节点权值小于 \(k\) 那么它的左子树都会分到第一棵树内,然后更新它的右子树
否则该节点的右子树都会分到第二棵子树内,然后更新它的左子树
注意理解 & 的含义
\(k = 9\) 的时候
void split(int root, int key, int &x, int &y) { // x, y即分裂出的两个树 if (root == 0) { x = y = 0;//递归边界 return; } if (Tree[root].Key <= key) { x = root; split(Tree[root].Right, key, Tree[root].Right, y); } else { y = root; split(Tree[root].Left, key, x, Tree[root].Left); } pushup(root); }
把一棵树分成两棵树,其中一棵的大小为 \(k\)
和 \(Treap\) 的 \(Kth\) 操作类似
如果当前点的左子树大小大于 \(k\) ,向左子树继续查找
否则的话该点的左子树一定在大小为 \(k\) 的树中,然后使右子树分出 \(k - siz[p] - 1\) 大小的子树
void split(int root, int sze, int &x, int &y) { if (root == 0) { x = y = 0; return; } if (Tree[Tree[root].Left].Size + 1 <= sze) { x = root; split(Tree[root].Right, sze - Tree[Tree[root].Left].sze - 1, Tree[root].Right, y); } else { y = root; split(Tree[root].Left, sze, x, Tree[root].Left); } push_up(root); }
到这才有平衡树内味了
把两个 \(Treap\) 合并,设第一个树的权值小于第二个树的权值
在这利用每个节点的随机值对两个树进行合并,来维护树的形态
如果第一个的随机值小,就保留它的左子树,把第一个 \(Treap\) 变成它的右子树,否则就保
留第二棵树的右儿子,指针指向它的左儿子
也可以理解为在第一棵树右子树插第二棵树,在第二棵树的左子树插第一个树,因为第一树
的权值都小于第二棵树,所以利用随机值来维护树的形态
时间复杂度 \(O(n)\)
int merge(int x, int y) { if (x == 0 || y == 0) return x + y; //相当于返回0 或者 返回 x, y 不为 0 的一个 if (Tree[x].Priority > Tree[y].Priority) { Tree[x].Right = merge(Tree[x].Right, y); pushup(x); return x; } else { Tree[y].Left = merge(x, Tree[y].Left); push_up(y); return y; }
把新节点 \(key\) 看做一棵树,先把选树按照 \(key\) 值分成两棵树,然后把新节点与它们两两合并
void insert(int key) { int x, y; split(Root, key - 1, x, y); Root = merge(merge(x, create(key)), y); }
先把整个树按照 \(key\) 分裂为 \(x, z\) ,然后按照 \(key - 1\) 把 \(x\) 分裂为 \(x, y\) ,显然此时 \(y\) 上
的结点的值都等于 \(key\),如果删掉一个点,就把 \(y\) 左右子树合并(根就没了),然后再合
并 \(x, y, z\) ,如果删除所有的权值为 \(key\) 的点,那就直接合并 \(x,z\) 就好了
void Delete(int key) { int x, y, z; split(Root, key, x, z); split(x, key - 1, x, y); if (y) { // 如果删除所有,就直接去掉这个if语句块,并且下面的只合并x, z y = merge(Tree[y].Left, Tree[y].Right); } Root = merge(merge(x, y), z); }
查权值为 \(key\) 的元素排名是多少
先按照 \(key - 1\) 分树,然后 \(key\) 的排名就为 \(key-1\) 的树的大小 + 1
int query_Rank(int key) { int x, y, ans; split (Root, key - 1, x, y); ans = Tree[x].Size + 1; Root = merge(x, y); return ans; }
和 \(Treap\) 的操作一个样
int query_Kth(int r) { int root = Root; while (true) { if (Tree[Tree[root].Left].Size + 1 == r) { break; } else if (Tree[Tree[root].Left].Size + 1 > r) { root = Tree[root].Left; } else { r -= Tree[Tree[root].Left].Size + 1; root = Tree[root].Right; } } return Tree[root].Key; }
还有一种写法就是按照树大小对树三分(比上面慢点)
int query_Kth(int r) { int x, y, z; split(Root, r - 1, x, y); split(y, 1, y, z); T ans = Tree[y].Key; Root = merge(merge(x, y), z); return ans; }
按照权值 \(key - 1\) 进行分树,然后在 \(key - 1\) 的树上找个最大值
int query_pre(int key) { int x, y, root, ans; split(Root, key - 1, x, y); root = x; while (Tree[root].Right) root = Tree[root].Right; ans = Tree[root].Key; Root = merge(x, y); return ans; }
和上面原理一个样,就是在另一棵树上取最小值
int query_suc(int key) { int x, y, root, ans; split(Root, key, x, y); root = y; while (Tree[root].Left) root = Tree[root].Left; ans = Tree[root].Key; Root = merge(x, y); return ans; }
查询元素是否存在
bool find(T key) { int x, y, z;bool ans; split(Root, key, x, z); split(x, key - 1, x, y); if (Tree[y].Size) ans = true; else ans = false; Root = merge(merge(x, y), z); return ans; }
垃圾回收优化
对于删除的那些节点,我们可以离线用栈存起来,如果新建节点中有找个点那就可以不用操作了
void Delete(int key) { int x, y, z; split(Root, key, x, z); split(x, key - 1, x, y); if (y) { if(Top < (MaxSize >> 8) - 5) Stack[++Top] = y; y = merge(Tree[y].Left, Tree[y].Right); } Root = merge(merge(x, y), z); } int Insert(int key) { int root = Top ? Stack[Top--] : ++Total; Tree[root].Key = key; Tree[root].Size = 1; Tree[root].Left = Tree[root].Right = 0; Tree[root].Priority = rad(); return root; }
本文参考:ctjcalc's blog
FHQ Treap小结(神级数据结构!)
fhq treap总结
%%%%%% 各位学长
\(finish\)