首页 > 其他 > 详细

Splay

时间:2020-07-30 22:05:03      阅读:114      评论:0      收藏:0      [点我收藏+]

啊淦,,不知道咕了多久了已经 对没错现在还要咕,现在才想起来写,忘干净了都快,qvq,一看这种代码一大片的就完全提不起劲儿的说

Splay简述&结构

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的性质,

过程:

  1. fp 为 p 的父亲,ffp 为 fp 的父亲,oo 表示 p 为左儿子还是右儿子
  2. 让 fp 的儿子 o[fp][oo]变为 2 o[p][oo ^ 1],让 2 f[o[p][oo ^ 1]] 的父亲变为 fp
  3. 让 p 的儿子 o[p][oo ^ 1] 变为 fp ,让 fp 的父亲 f[fp] 变为 p
  4. 如果存在 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

原文:https://www.cnblogs.com/moziii/p/13406629.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!