首页 > 其他分享 >Splay 学习笔记

Splay 学习笔记

时间:2024-04-14 09:01:36浏览次数:27  
标签:学习 结点 log zag 复杂度 笔记 Splay zig

为了 LCT 制造了一个 Splay ……

Splay 还是一种二叉排序树。我们想让他支持查询结点,删除结点等等。但是普通 BST 复杂度难以保证,于是 Splay 出现了。

【引入】

Splay 的思想和并查集的路径压缩类似。并查集的路径压缩允许出现一两次复杂度高的操作,但是经历过一次后就不会再有第二次了。

Splay 的基本思想就是在操作一个结点时,直接把这个结点放到根结点上。

【单旋与双旋】

区分三种操作:单旋、双旋、把某个结点转到根。

回想以前的数据结构,在操作一个结点时需要改变结点的位置的,旋转 Treap 的旋转操作非常具有特点。

单旋:zig(右旋) 和 zag(左旋)。

Splay 的特殊之处就在于,我们发明了一种 "双旋" 操作,一次操作可以让一个结点和他的祖父交换位置,且不改变二叉排序树的性质。

双旋的理念也很简单:要上升两层,那就做两次单旋。两次单旋共 \(2\times 2=4\) 种方案,衍生出 \(4\) 种双旋。

  1. zig-zig,即两次都是右旋操作。

    左侧的 \(x\) 是我们要转到根结点的结点,但是在这一次双旋里面,我们只考虑让他转到他的祖父结点 \(g\) 处。\(p\) 是 \(x\) 的父亲。

    右侧上下是两种旋转的方式:一种是转两次 \(x\),一种是先转 \(p\) 再转 \(x\)。Splay 在进行这种双旋时我们采取下面那种,具体原因后面会说。

  2. zag-zag,先转 \(p\) 后转 \(x\)。

  3. zag-zig,转两次 \(x\)。

    其实这种情况只能先转 \(x\),如右侧,如果先对 \(p\) zag,\(x\) 无法上升。

  4. zig-zag,转两次 \(x\)。

zag-zig 和 zig-zag 是只能转两次 \(x\) 的,没有疑问;但是 zig-zig 和 zag-zag 为什么要先转 \(p\)?这涉及到复杂度分析。

【复杂度分析】

【概念】

算 Splay 的复杂度首先要认识到什么是 "分摊复杂度":单次操作可能很慢,多次操作平均很快。

其次是 "势能":这是一个物理的概念。

当一个物体在一个高度,那当这个物体下落的时候,位置本身就会赋予物体下落的能量,我们称其为重力势能。高度越高,重力势能越大。

这个概念有什么特殊之处?当一个物体从位置 \(A\) 到了位置 \(B\),中间可能有各种乱七八糟的移动,但其重力势能的变化量,只有位置 \(B\) 与位置 \(A\) 的高度差产生的重力势能。

那这和复杂度分析有什么关系?

【势能分析法】

我们为了证明,人为定义一个起始势能 \(S\) 和结束势能 \(T\)。

不妨每次操作是 \(t_1,t_2,\dots,t_m\)。

总时间 \(=t_1+t_2+\cdots+t_m=\sum t_i+(T-S)-(T-S)\)。

我们希望 \(T-S\) 是个不太大的数,同时希望可以把 \(T-S\) 拆成 \(k_1+k_2+\cdots+k_m\),而且 \(t_i+k_i\le\) 单次操作复杂度上限 \(x\)。

如果我们真的设计出一个这样的势能函数,\(\sum t_i+(T-S)-(T-S)=-(T-S)+\sum (t_i+k_i)\le -(T-S)+m\cdot x\)。

(对较大的 \(t_i\) 放一个较小的 \(k_i\),对较小的 \(t_i\) 放一个较大的 \(k_i\),多退少补,总和是 \(T-S\))

目标是让 \(T-S\) 在 \(O(n\log n)\) 级别,让 \(x\) 在 \(O(\log n)\) 级别。这样总时间就是 \(O(n\log n+m\log n)\)。均摊每一次是 \(O(\frac{n}{m}\cdot \log n+\log n)\),一般就能直接视作 \(O(\log n)\) 的了。


令 \(s_i\) 为 \(i\) 子树规模,\(p_i=\log s_i\) 为 \(i\) 的势能。

\(S=\displaystyle\sum_{初始} p_i,T=\sum_{最终}p_i\)。

这里指的是 Splay 这颗 BST 在经历操作前和经历操作后。

一个结点的 \(s_i\) 显然 \(\le n\),所以 \(S,T\) 显然都 \(\le n\log n\),则 \(-(T-S)\le n\log n\)。接下来的任务就是把 \((T-S)\) 拆成 \(m\) 个 \(k_i\)。

我们认为一次单旋操作是 "\(1\) 次" 操作。

结论:让 \(x\) 转上祖父的双旋操作次数 $\le $

标签:学习,结点,log,zag,复杂度,笔记,Splay,zig
From: https://www.cnblogs.com/FLY-lai/p/18129897

相关文章

  • 《自动机理论、语言和计算导论》阅读笔记:p139-p171
    《自动机理论、语言和计算导论》学习第7天,p139-p171总结,总计33页。一、技术总结1.reversalp139,Thereversalofastringa1a2...anisthestringwrittenbackwards,thatisanan-1...a1.2.homomorphismAstringhomomorphismisafunctiononstringsthatwokrs......
  • 架构学习-多任务
    架构学习-多任务:进程,线程,协程多任务参考架构学习-多任务:进程,线程,协程多任务多任务处理:是指计算机同时运行多个程序的能力。比如说,我们在使用电脑的时候,可以边听音乐,边写文档。从物理层面上看,最早的CPU都是单核的,也就是同一时间只能执行一条指令。单核CPU是如何支......
  • [笔记]数位dp例题及详解-下
    【接上回】-数位dp例题及详解-上共\(4\)道难度较高、较有思考性的题。附上数位dp题单:https://www.luogu.com.cn/training/494976#problems小小的总述:数位dp是这样的,状态表示越简洁,dp数组越小巧,进而时空消耗就越少。所以我们刷题的时候,可以先无脑把\(f\)数组的每一维都设为与......
  • Spring学习笔记
    一、Spring启示录阅读以下代码:packagecom.powernode.oa.controller;importcom.powernode.oa.service.UserService;importcom.powernode.oa.service.impl.UserServiceImpl;publicclassUserController{privateUserServiceuserService=newUserServiceImpl();......
  • Living-Dream 系列笔记 第53期
    妙妙题大合集。T1令\(dp_{i,j}\)表示分离出以\(i\)为根的恰含\(j\)节点的树所需的最小删边数。有初始状态\(dp_{i,1}=\)其子节点个数,其余为\(\infty\)。对于答案,我们考虑到对于每个节点\(i\),除了其子树内的删边数之外,它的父节点与它的连边也应删去(注意根节点\(root......
  • 有限元方法[Matlab]-笔记
    <<MATLABCodesforFiniteElementAnalysis-SolidsandStructures(Ferreira)>>笔记chapter01matlabbasic略第二章:离散系统笔记、例题Matlab代码problem1.m%MATLABcodesforFiniteElementAnalysis%Problem1:3springsproblem%clearme......
  • 多项式学习笔记
    1.前置知识1.1基础\(f(x)=\sum_{i=0}^na_ix^i\)被称为一个\(n\)次多项式。\(\degf(x)\)表示多项式的次数。\(f(x)g(x)=h(x)\)称为多项式乘法,也叫多项式卷积,满足\(h_n=\sum_{i+j=n}f_ig_j\)。1.2点值给定一个多项式\(f(x)\),再给\(m\)个点\(x_1,\dot......
  • [深度学习]多层感知机(MLP)
    多层感知机(MLP)1.单层感知机1.1感知机线性回归输出的是一个实数,感知机输出的是一个离散的类。1.2训练感知机①如果分类正确的话y<w,x>为正数,负号后变为一个正数,和\(0\)取\(max\)之后得\(0\),则梯度不进行更新②如果分类错了,y<w,x>为负数,的判断条件成立,就进行梯度更新。......
  • 学习 GitHub 风格的 Markdown 语法和格式化 - 带有示例
    Markdown是一种轻量级、开源、易读易写的文本格式化方法,你可以在任何IDE或编辑器中将其作为纯文本使用。在GitHub上写作时,你可以使用Markdown语法和HTML元素来扩展Markdown的功能。你可以在GitHub的各个地方使用Markdown语法,比如README文件、wiki、评论、拉取请......
  • [学习笔记] 树上差分 - 图论
    前置知识:树,LCA,前缀和与差分边差分这个名字是在网上看到的,不理解为什么要叫这么一个名字,可能是因为它与树链修改有关。当然,用于树链修改单点查询非常方便~看这个图,该图是以点1为根进行DFS的。如果我们要把从3->4这条树链上所有的点统统加上1,可以都转化为对到根节点的......