目录
1 从 BST 到平衡树
众所众知,二叉搜索树(BST)是一棵能方便实现插入、删除,找前驱、后驱,按排名找数、找数的排名的数据结构,但是在构造数据下,ta 的单次复杂度甚至有 \(O(N)\)。因此,平衡树就登场了,ta 的单次复杂度仅为 \(O(\log N)\)。
map/set 等 STL 的实现方式也是平衡树的一种——红黑树。
2 替罪羊树
2.1 替罪羊树的维护
替罪羊树就是比较优雅的暴力啦。
众所周知,一棵树不平衡了怎么办?重建呗(反正对于不同的二叉搜索树,其中序遍历不变)。例如:
中序遍历:\([1,2,3,4,5,6]\)。
重建:
此时,该 BST 就平衡了不少。
那么,我们只要在该树不平衡时,重建就可以了。
设某树的左子树有 \(lsize\) 个点(包括未删除的点,下同),右子树上有 \(rsize\) 个点,我们定义该树的不平衡率为 \(\alpha'=\dfrac{\max(lsize,rsize)}{lsize + rsize}\)。
显然,\(0.5 \le \alpha' \le 1\)(两种极端情况分别为:左右子树节点数相等、左右子树其中有一个子树为空),且 \(\alpha'\) 越大,该树越不平衡。
所以,我们只要设定一个阈值 \(\alpha\),使得某树不平衡率 \(\alpha' > \alpha\) 时重建即可。
一般来说,\(\alpha\) 为 \(0.7\) 或 \(0.75\)。
还有一种情况,替罪羊树的删除是打标,而不真正删掉,所以当删除的节点个数为 \(del\), \(\dfrac{del}{lsize + rsize} > \beta\) 时,也要重建。
同样的,一般来说,\(\beta\) 为 \(0.3\)。
2.2 替罪羊树的基本操作
2.2.1 替罪羊树的结点信息
lc
、rc
:左右儿子。不存在则为 \(-1\)。
fa
:父亲。
val
、cnt
:结点的值及个数。
nodesize
、avsize
、numsize
:该子树的总结点数目、未打标(也就是未删除)结点数目、存储的数字个数(也就是 \(\sum cnt\))。
del
:是否被删除。
root
:树根。空树则为 \(-1\)。
struct tNode
{
int lc, rc, fa, val, cnt, nodesize, avsize, numsize;
bool del;
}tree[N << 1];
int root;
Scapegoat_Tree() { root = -1; }
2.2.2 替罪羊树的空间利用
由于替罪羊树删除为打标,因此替罪羊树的空间利用是一个问题。
所以定义内存池(用栈实现)mem
,使用 newmem
函数来新建节点,返回新结点的编号。用 used
表示到现在为止使用过(包括已删除)的结点的编号,inst
表示栈中结点数目。
int used, inst;
stack<int>mem;
int newmem()
{
if(inst > 0) // 栈非空,弹出栈顶
{
inst--;
int top = mem.top();
mem.pop();
return top;
}
return ++used; // 否则再建一个节点
}
2.2.3 替罪羊树的重建
首先,最基础的,对于已知的位置,初始化点。
void Add_Node(int nid, int val, int fa)
{
tree[nid].fa = fa, tree[nid].lc = tree[nid].rc = -1, tree[nid].val = val;
tree[nid].cnt = tree[nid].nodesize = tree[nid].avsize = tree[nid].numsize = 1, tree[nid].del = false;
}
找到某个值的位置。若不存在,返回一个结点,使得该值可作为该结点的左儿子或右儿子。
int Find_Pos(int x, int val)
{
if(val < tree[x].val && tree[x].lc != -1) // 可能在左子树
return Find_Pos(tree[x].lc, val);
if(val > tree[x].val && tree[x].rc != -1) // 可能在右子树
return Find_Pos(tree[x].rc, val);
return x; // 找到目标结点
}
还有 Update
函数,用来更新祖先结点的 nodesize
、avsize
、numsize
,用 nodeadd
、avadd
、numadd
来表示祖先结点的 nodesize
、avsize
、numsize
需要加上的值。
void Update(int x, int nodeadd, int avadd, int numadd)
{
if(x == -1) // 跳到头了
return ;
tree[x].nodesize += nodeadd, tree[x].avsize += avadd, tree[x].numsize += numadd;
Update(tree[x].fa, nodeadd, avadd, numadd); // 向上跳
}
然后就是替罪羊树的核心重建。
第一步是求中序遍历。
// 在结构体外
int seqsize;
struct tSeq
{
int val, cnt;
}tseq[N << 1];
// 在结构体内
void Dfs(int x)
{
if(x == -1) // 跳到了空结点
return;
Dfs(tree[x].lc); // 先遍历左子树
if(!tree[x].del) // 如果未删除
tseq[++seqsize].val = tree[x].val, tseq[seqsize].cnt = tree[x].cnt, mem.push(x), inst++;
Dfs(tree[x].rc); // 最后遍历右子树
}
ReAdd
函数,对区间 \([l, r]\) 进行重建,父节点为 fa
,并返回根节点。
int ReAdd(int l, int r, int fa)
{
if(l > r)
return -1;
int mid = (l + r) >> 1; // 取中间的结点
int nid = newmem(); // 取出新的结点
tree[nid].fa = fa;
tree[nid].cnt = tseq[mid].cnt;
tree[nid].val = tseq[mid].val;
tree[nid].lc = ReAdd(l, mid - 1, nid); // 递归左边
tree[nid].rc = ReAdd(mid + 1, r, nid); // 递归右边
tree[nid].numsize = tree[tree[nid].lc].numsize + tree[tree[nid].rc].numsize + tseq[mid].cnt;
tree[nid].nodesize = tree[nid].avsize = r - l + 1; // 注意已经自动删掉了打标了的结点
return nid;
}
ReBuild
,对已知的结点 \(x\) 做重建。
void ReBuild(int x)
{
seqsize = 0;
Dfs(x);
if(x == root)
root = ReAdd(1, seqsize, -1);
else
{
Update(x, tree[x].avsize - tree[x].nodesize, 0, 0);
if(tree[tree[x].fa].lc == x)
tree[tree[x].fa].lc = ReAdd(1, seqsize, tree[x].fa);
else
tree[tree[x].fa].rc = ReAdd(1, seqsize, tree[x].fa);
}
}
最后,当我们修改结点的时候,只有根结点到 \(val\) 代表的结点这一条路径上的结点可能会不平衡,所以从根节点开始,向下递归看是否要重建。
// 在结构体外
const double Alpha = 0.75, Beta = 0.3;
// 在结构体内
void Find_ReBuild(int x, int val)
{
if(double(max(tree[tree[x].lc].nodesize, tree[tree[x].rc].nodesize)) > (tree[x].nodesize - 1) * Alpha || double(tree[x].nodesize - tree[x].avsize) > tree[x].nodesize * Beta) // 对应要重建的两种情况
{
ReBuild(x); // 重建
return ;
}
if(tree[x].val != val) // 继续往下找
Find_ReBuild((tree[x].val > val)?tree[x].lc:tree[x].rc, val);
}
剩下的操作就很简单了。
2.2.4 替罪羊树的插入、删除
插入函数 Add
,用 Find_Pos
函数找到位置,再讨论在何处插入。
void Add(int val)
{
if(root == -1) // 为空树
{
Add_Node(root = newmem(), val, -1);
return ;
}
int p = Find_Pos(root, val); // 找到应插入的位置
if(tree[p].val == val) // 树中有这个结点
{
tree[p].cnt++;
if(tree[p].del) // 删除了就复活
tree[p].del = false, Update(p, 0, 1, 1);
else
Update(p, 0, 0, 1);
}
else if(tree[p].val > val) // 树中无该结点,判断新加的结点是左儿子还是右儿子
Add_Node(tree[p].lc = newmem(), val, p), Update(p, 1, 1, 1);
else
Add_Node(tree[p].rc = newmem(), val, p), Update(p, 1, 1, 1);
Find_ReBuild(root, val); // 判断是否重建
}
删除函数 Del
,也是用 Find_Pos
函数找到位置,再删除,判断是否打标。
void Del(int val)
{
int p = Find_Pos(root, val); // 找到应删除的位置
tree[p].cnt--;
if(!tree[p].cnt) // 需要打标
tree[p].del = true, Update(p, 0, -1, -1);
else
Update(p, 0, 0, -1);
Find_ReBuild(root, val); // 判断是否重建
}
2.2.5 替罪羊树的按数找排名、按排名找数
Find_Rank
函数,查找 \(val\) 的排名,从根节点递归查找。
int Find_Rank(int val)
{
int x = root, ans = 0;
while(tree[x].val != val)
{
if(x == -1) // 如果到了空树,那么 ans + 1 即为答案
return ans + 1;
if(val < tree[x].val) // 如果 val 比当前根的 val 小,那么在左子树
x = tree[x].lc;
else
ans += tree[tree[x].lc].numsize + tree[x].cnt, x = tree[x].rc; // 否则在右子树,比 val 小的数有当前的左子树的 numsize + 当前根的 cnt
}
if(tree[x].lc != -1) // 左子树不为空,还有当前左子树的 numsize 没有算
ans += tree[tree[x].lc].numsize;
return ans + 1;
}
Find_Num
函数,查找排名为 \(rank\) 的数,同样从根节点递归查找。
int Find_Num(int rank)
{
int x = root, rrank = rank;
while(true)
{
if(rrank <= tree[tree[x].lc].numsize) // 如果 rank 不大于左子树的 numsize,那么就是左子树的第 rank 个
x = tree[x].lc;
else // 否则要么是根,要么在右子树
{
rrank -= tree[tree[x].lc].numsize; // 先将 rank 减去左子树的 numsize
if(rrank <= tree[x].cnt) // rank 小于等于根节点的 cnt,就在根节点
return tree[x].val;
rrank -= tree[x].cnt, x = tree[x].rc; // 否则在右子树,根的值应该比答案小,减去根的 cnt
}
}
}
2.2.6 替罪羊树的找前驱、后继
思维上略微复杂。
为了方便,定义 \(isrc(x)\) 表示 \(x\) 是否是一个结点的右儿子,是则为 \(1\),不是则为 \(0\)。
首先用 Find_Pos
函数找到 \(val\) 的位置(记为 \(p\)),is_rc
表示上一个结点是否为该结点的右儿子。如果它是上一个结点是该结点的左儿子,一定往上跳(若答案在某个跳过的点的左子树上,答案不受影响),若是右儿子,那么如果比 \(val\) 小且存在,那么一定为该点,否则如果其有左儿子,在左儿子上找最大值。如果上述均不满足,那么往上跳 \(^\dag\)。
\(^\dag\) 一开始,无论 \(isrc(p)\) 值如何,is_rc
的初始值为 \(\text{true}\),这样,在一开始就能检查左子树是否有答案(见代码)。
该做法的正确性:答案有两种情况:
- 在 \(p\) 的左子树上;
- 在 \(p\) 的某个祖先的左子树上。
易证这些数能覆盖所有 \(<val\) 的数。
若答案在 \(p\) 的左子树上,那么一开始即已经检查到。
否则,如果当前的点为 \(x\),那么若 \(isrc(x) = 0\),那么往上跳。这样除了 \(p\) 左子树上的数就没有 \(< val\) 的数了。若 \(isrc(x) = 1\),那么答案在左子树(因为 \(< val\) 的数只在 \(x\) 的左子树上)。还有一种特殊情况,答案为某个祖先,需要判断一下。
特别的,无需担心左子树有结点但全被打标的情况,因为此时左子树的 \(\beta' = 1 \ge \beta\)。
int tans;
void Dfs_Pre(int x)
{
if(tree[x].rc != -1)
Dfs_Pre(tree[x].rc);
if(tans != -1)
return ;
if(!tree[x].del)
{
tans = tree[x].val;
return ;
}
if(tree[x].lc != -1)
Dfs_Pre(tree[x].lc);
}
int Find_Pre(int x, int val, bool is_rc)
{
tans = -1;
if(!is_rc) // is_rc = 0,向上跳
return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false);
if(!tree[x].del && tree[x].val < val) // 答案为某个祖先
return tree[x].val;
if(tree[x].lc != -1) // is_rc = 1 且左子树不为空
{
Dfs_Pre(tree[x].lc);
return tans;
}
return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false); // 继续往上
}
找后继代码 Dfs_Nxt
和 Find_Nxt
几乎与找前驱类似,原理也类似,相当于 Dfs_Pre
函数和 Find_Pre
函数全部反过来。
void Dfs_Nxt(int x)
{
if(tree[x].lc != -1)
Dfs_Nxt(tree[x].lc);
if(tans != -1)
return ;
if(!tree[x].del)
{
tans = tree[x].val;
return ;
}
if(tree[x].rc != -1)
Dfs_Nxt(tree[x].rc);
}
int Find_Nxt(int x, int val, bool is_lc)
{
tans = -1;
if(!is_lc)
return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
if(!tree[x].del && tree[x].val > val)
return tree[x].val;
if(tree[x].rc != -1)
{
Dfs_Nxt(tree[x].rc);
return tans;
}
return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
}
2.3 替罪羊树完整代码
抽象的 \(258\) 行。
/** {
* problem: 替罪羊树
* site: \
* author: _Z_F_R_
* date: 2023-10-05 14:26:30
**/
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const double Alpha = 0.75, Beta = 0.3;
int seqsize;
struct tSeq
{
int val, cnt;
}tseq[N << 1];
struct Scapegoat_Tree
{
struct tNode
{
int lc, rc, fa, val, cnt, nodesize, avsize, numsize;
bool del;
}tree[N << 1];
int root, used, inst;
Scapegoat_Tree() { root = -1; }
stack<int>mem;
int newmem()
{
if(inst > 0)
{
inst--;
int top = mem.top();
mem.pop();
return top;
}
return ++used;
}
void Add_Node(int nid, int val, int fa)
{
tree[nid].fa = fa, tree[nid].lc = tree[nid].rc = -1, tree[nid].val = val;
tree[nid].cnt = tree[nid].nodesize = tree[nid].avsize = tree[nid].numsize = 1, tree[nid].del = false;
}
int Find_Pos(int x, int val)
{
if(val < tree[x].val && tree[x].lc != -1)
return Find_Pos(tree[x].lc, val);
if(val > tree[x].val && tree[x].rc != -1)
return Find_Pos(tree[x].rc, val);
return x;
}
void Update(int x, int nodeadd, int avadd, int numadd)
{
if(x == -1)
return ;
tree[x].nodesize += nodeadd, tree[x].avsize += avadd, tree[x].numsize += numadd;
Update(tree[x].fa, nodeadd, avadd, numadd);
}
void Dfs(int x)
{
if(x == -1)
return;
Dfs(tree[x].lc);
if(!tree[x].del)
tseq[++seqsize].val = tree[x].val, tseq[seqsize].cnt = tree[x].cnt, mem.push(x), inst++;
Dfs(tree[x].rc);
}
int ReAdd(int l, int r, int fa)
{
if(l > r)
return -1;
int mid = (l + r) >> 1;
int nid = newmem();
tree[nid].fa = fa;
tree[nid].cnt = tseq[mid].cnt;
tree[nid].val = tseq[mid].val;
tree[nid].lc = ReAdd(l, mid - 1, nid);
tree[nid].rc = ReAdd(mid + 1, r, nid);
tree[nid].numsize = tree[tree[nid].lc].numsize + tree[tree[nid].rc].numsize + tseq[mid].cnt;
tree[nid].nodesize = tree[nid].avsize = r - l + 1;
return nid;
}
void ReBuild(int x)
{
seqsize = 0;
Dfs(x);
if(x == root)
root = ReAdd(1, seqsize, -1);
else
{
Update(x, tree[x].avsize - tree[x].nodesize, 0, 0);
if(tree[tree[x].fa].lc == x)
tree[tree[x].fa].lc = ReAdd(1, seqsize, tree[x].fa);
else
tree[tree[x].fa].rc = ReAdd(1, seqsize, tree[x].fa);
}
}
void Find_ReBuild(int x, int val)
{
if(double(max(tree[tree[x].lc].nodesize, tree[tree[x].rc].nodesize)) > (tree[x].nodesize - 1) * Alpha || double(tree[x].nodesize - tree[x].avsize) > tree[x].nodesize * Beta)
{
ReBuild(x);
return ;
}
if(tree[x].val != val)
Find_ReBuild((tree[x].val > val)?tree[x].lc:tree[x].rc, val);
}
void Add(int val)
{
if(root == -1)
{
Add_Node(root = newmem(), val, -1);
return ;
}
int p = Find_Pos(root, val);
if(tree[p].val == val)
{
tree[p].cnt++;
if(tree[p].del)
tree[p].del = false, Update(p, 0, 1, 1);
else
Update(p, 0, 0, 1);
}
else if(tree[p].val > val)
Add_Node(tree[p].lc = newmem(), val, p), Update(p, 1, 1, 1);
else
Add_Node(tree[p].rc = newmem(), val, p), Update(p, 1, 1, 1);
Find_ReBuild(root, val);
}
void Del(int val)
{
int p = Find_Pos(root, val);
tree[p].cnt--;
if(!tree[p].cnt)
tree[p].del = true, Update(p, 0, -1, -1);
else
Update(p, 0, 0, -1);
Find_ReBuild(root, val);
}
int Find_Rank(int val)
{
int x = root, ans = 0;
while(tree[x].val != val)
{
if(x == -1)
return ans + 1;
if(val < tree[x].val)
x = tree[x].lc;
else
ans += tree[tree[x].lc].numsize + tree[x].cnt, x = tree[x].rc;
}
if(tree[x].lc != -1)
ans += tree[tree[x].lc].numsize;
return ans + 1;
}
int Find_Num(int rank)
{
int x = root, rrank = rank;
while(true)
{
if(rrank <= tree[tree[x].lc].numsize)
x = tree[x].lc;
else
{
rrank -= tree[tree[x].lc].numsize;
if(rrank <= tree[x].cnt)
return tree[x].val;
rrank -= tree[x].cnt, x = tree[x].rc;
}
}
}
int tans;
void Dfs_Pre(int x)
{
if(tree[x].rc != -1)
Dfs_Pre(tree[x].rc);
if(tans != -1)
return ;
if(!tree[x].del)
{
tans = tree[x].val;
return ;
}
if(tree[x].lc != -1)
Dfs_Pre(tree[x].lc);
}
int Find_Pre(int x, int val, bool is_rc)
{
tans = -1;
if(!is_rc)
return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false);
if(!tree[x].del && tree[x].val < val)
return tree[x].val;
if(tree[x].lc != -1)
{
Dfs_Pre(tree[x].lc);
return tans;
}
return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false);
}
void Dfs_Nxt(int x)
{
if(tree[x].lc != -1)
Dfs_Nxt(tree[x].lc);
if(tans != -1)
return ;
if(!tree[x].del)
{
tans = tree[x].val;
return ;
}
if(tree[x].rc != -1)
Dfs_Nxt(tree[x].rc);
}
int Find_Nxt(int x, int val, bool is_lc)
{
tans = -1;
if(!is_lc)
return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
if(!tree[x].del && tree[x].val > val)
return tree[x].val;
if(tree[x].rc != -1)
{
Dfs_Nxt(tree[x].rc);
return tans;
}
return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
}
void Print()
{
printf("%d\n", root);
int i;
for(i = 1; i <= used; i++)
printf("%d : [%d] fa : %d lc : %d rc : %d cnt : %d val : %d size : [%d, %d, %d]\n", i, tree[i].del, tree[i].fa, tree[i].lc, tree[i].rc, tree[i].cnt, tree[i].val, tree[i].nodesize, tree[i].avsize, tree[i].numsize);
}
}bst;
int main()
{
int n;
scanf("%d", &n);
while(n--)
{
int op, val;
scanf("%d %d", &op, &val);
if(op == 1)
bst.Add(val);
else if(op == 2)
bst.Del(val);
else if(op == 3)
printf("%d\n", bst.Find_Rank(val));
else if(op == 4)
printf("%d\n", bst.Find_Num(val));
else if(op == 5)
printf("%d\n", bst.Find_Pre(bst.Find_Pos(bst.root, val), val, true));
else
printf("%d\n", bst.Find_Nxt(bst.Find_Pos(bst.root, val), val, true));
}
}
敬请期待后续 Treap / FHQ Treap / Splay 等多种平衡树
参考:
https://blog.csdn.net/a_forever_dream/article/details/81984236