杂
啊淦,, 不知道咕了多久了已经 对没错现在还要咕, 现在才想起来写, 忘干净了都快, qvq, 一看这种代码一大片的就完全提不起劲儿的说
BST -- 二叉查找树, 任意左儿子 < 父亲节点 , 任意右儿子 > 父亲节点 (对每个节点都符合
Splay -- 是一种 BST, 它通过不断将某个节点旋转到根节点, 使得整棵树仍然满足二叉查找树的性质, 并且保持平衡而不至于退化为链, 它由 Daniel Sleator 和 Robert Tarjan 发明, Tarjan np!!
维护的信息
\(rt\) | \(tot\) | \(f[i]\) | \(o[i][0/1]\) | \(v[i]\) | \(cnt[i]\) | \(sz[i]\) |
---|---|---|---|---|---|---|
根节点编号 | 节点个数 | 父亲 | 左 / 右儿子编号 | 节点权值 | 权值出现次数 | 子树大小 |
因为存在 左子树任意节点的值 < 根节点的值 < 右子树任意节点的值 的性质, 我们能从这棵树上查找某个值
- Various operations
- the basic
\(maintain(p)\) : 改变节点位置后更新节点的 \(size\)
\(get(p)\) : 判断某节点为左儿子还是右儿子
\(clear(p)\) : 销毁节点
- void maintain(int p) {
- sz[p] = sz[o[p][0]] + sz[o[p][1]];
- }
- bool get(int p) {
- return o[f[p]][1] = p;
- }
- void clear(int p) {
- o[p][0] = o[p][1] = f[p] = v[p] = sz[p] = cnt[p] = 0;
- }
- rotate
旋转操作 >>>>
以左图到右图为例, 现在要将 p 节点向上移一个位置, 将 1-p-fp-3 这条链往右移一个位置, 2 的父亲由右上的 p 换为左上的 fp(旋转之后的结果),, 过程中我们要维护这棵树 BST 的性质,
过程:
fp 为 p 的父亲, ffp 为 fp 的父亲, oo 表示 p 为左儿子还是右儿子
让 fp 的儿子 o[fp][oo] 变为 2 o[p][oo ^ 1], 让 2 f[o[p][oo ^ 1]] 的父亲变为 fp
让 p 的儿子 o[p][oo ^ 1] 变为 fp , 让 fp 的父亲 f[fp] 变为 p
如果存在 fp 的父亲 ffp(fp 不是根节点), 让 ffp 的儿子 o[ffp][get[fp]] 变为 p,p 的父亲变为 ffp
? \(\lll - 相互 -\ggg\)
- void rotate(int p) {
- int fp = f[p], ffp = f[fp], oo = get(p);
- o[fp][oo] = o[p][oo ^ 1];
- f[o[p][oo ^ 1]] = fp;
- o[p][oo ^ 1] = fp;
- f[fp] = p; f[p] = ffp;
- if(ffp) o[ffp][fp == o[ffp][1]] = p;
- maintain(fp);
- maintain(p);
- }
咕着, 三天内更完 [真香警告]
Splay
来源: http://www.bubuko.com/infodetail-3651515.html