前言
上文介绍了普通的平衡树，它简单（奇怪，鬼畜）的旋转操作确实死难写也难调（刚写挂一个），于是跑去学了一个不用旋转的平衡树，无旋 \(Treap (FHQ~~Treap)\)
只需要两个操作达到 \(bst，treap，splay\) 全部功能 ？？ 太炫酷了
概况
\(FHQ~~Treap\) 和普通的 \(Treap\) 一样每个节点维护两个值，一个是权值，一个是随机值
但是它不再是用旋转来维护，而是通过 \(split\) 和 \(merge\) 进行维护
操作
split（分树）
把一个 \(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);
}
merge（合并）
到这才有平衡树内味了
把两个 \(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;
}
Insert
把新节点 \(key\) 看做一棵树，先把选树按照 \(key\) 值分成两棵树，然后把新节点与它们两两合并
void insert(int key) {
int x, y;
split(Root, key - 1, x, y);
Root = merge(merge(x, create(key)), y);
}
Delete
先把整个树按照 \(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);
}
query_Rank
查权值为 \(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;
}
query_Kth
和 \(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;
}
query_pre
按照权值 \(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;
}
query_suc
和上面原理一个样，就是在另一棵树上取最小值
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;
}
find
查询元素是否存在
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
%%%%%% 各位学长
\(finish\)