平衡树学习笔记

这篇具有很好参考价值的文章主要介绍了平衡树学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

平衡树

平衡树就是为了实现一类元素在线性结构中动态变化的功能所需要的数据结构。

平衡树是一种基于二叉搜索树的数据结构。
满足:左儿子 \(<\)\(<\) 右儿子。
也就是一切小于根节点的在左边,一切大于根节点的在右边。
这样想要查找一个节点的位置时间复杂度就是 \(O(\log n)\)

平衡树主要有三种:Splay,fhq_Treap,Treap。
我这次主要讲前两种。
当然还有其他的像替罪羊树,红黑色。

Splay

Splay 是 LCT 的基础操作。
本人以为还是 Splay 比较好理解的。

核心操作

Splay 的基本操作就是将BST旋转,分左旋和右旋(其实都差不多)
旋转的要求:在不改变原有的中序遍历的前提下改变树的结构。
简化一下:把儿子节点与父亲节点的身份互换,且有BST性质。

旋转 \(zig(x)\),\(zag(x)\) 如下图:
平衡树学习笔记

具体描述

设要旋转的节点为 \(x\),它的父亲为 \(y\)\(y\) 的父亲为 \(z\)

  • \(y\) 的左儿子设为 \(x\) 的右儿子
  • \(x\) 的右儿子存在,将 \(x\) 的右儿子的父亲设为 \(y\)
  • \(x\) 的右儿子设为 \(y\)
  • \(y\) 的父亲设为 \(x\)
  • \(x\) 的父亲设为 \(z\)
  • \(z\) 存在,将 \(z\) 的某个子节点(原来 \(y\) 所在的子节点)设为 \(x\)

双旋操作

在 Splay 中,每加入一个新的节点就需要把它旋转到根。
设当前需旋转的节点为 \(x\),节点的旋转可分为以下三种:
\(1.\)\(x\) 的父亲是根,这时直接旋转即可。
\(2.\)父亲和 \(x\) 的儿子同侧(即同为左儿子或同为右儿子),这时先旋转父亲,再旋转 \(x\)
\(3.\)父亲和 \(x\) 的儿子不同侧,这时将 \(x\) 旋转两次。
如下图:
平衡树学习笔记
平衡树学习笔记

时间复杂度

对于这个时间复杂度的分析,我们需要用一下势能分析
\(siz(x)\) 表示以 \(x\) 为根节点的子树大小。
\(\phi(x)\) 表示在进行 \(x\) 次操作后的势能函数。
\(c(x)\) 表示时间的时间复杂度。
\(a(x)\) 表示均摊的时间复杂度。
所以根据定义,我们可以得出:
\(\phi(x)=\log(siz(x))\)
\(a(x)=c(x)+\phi(x)-\phi(x-1)\)
\(\sum a(x)=\phi(n)-\phi(0)+\sum c(x)\)
因为根据 \(\phi(x)=\log(siz(x))\),所以现在肯定有:\(|\phi(n)-\phi(0)|\le n\log n\)
考虑每一次的 \(\Delta\phi\)

对于zig:

\[\Delta\phi=\phi'(p)-\phi'(p)+\phi'(x)-\phi(x)=\phi'(p)-\phi(x)\le\phi'(x)-\phi(x) \]

平衡树学习笔记

对于zig-zig

\[\Delta\phi=\phi'(z)+\phi'(y)+\phi'(x)-\phi(z)-\phi(y)-\phi(x) \]
\[=\phi'(z)-\phi'(y)-\phi(y)-\phi(x) \]
\[\le\phi'(x)+\phi'(z)-2\phi(x) \]
\[\le 3\phi'(x)-3\phi(x)+(\phi(x)+\phi'(z)-2\phi'(x)) \]
\[\le 3(\phi'(x)-\phi(x))-2k \]

平衡树学习笔记

那么Splay到根的均摊代价为 \(O(logn)\)\(zig\) 只有一次操作,所以只会使均摊代价增加\(k\)
再算上 \(\phi(n)-\phi(0)=n\log n\)
所以总时间复杂度为 \(O(n\log n)\)

操作实现

讲了核心操作和时间复杂度后,我们来看看它可以支持的操作。
注:由于我们只能保证 Splay 本身的时间复杂度,所以我们就必须只能通过旋转来实现一些操作。

查询数值

给定一个数 \(k\),查询排名为 \(k\) 的数。

  • \(k\) 小于等于左子树大小,就向左子树走
  • 否则,将 \(k\) 先减去左子树大小和当前节点的 \(cnt\),使得 \(k\), 等于在右子树中的排名。然而若 \(k\) 小于等于 \(0\),说明已经找到,进行旋转,并返回当前节点权值。

查询 \(x\) 的前驱和后继

我们先将 \(x\) 节点旋转到根节点。

  • 前驱:就是 \(x\) 左子树中最右边的节点。
  • 后继:就是 \(x\) 右子树中最左边的节点。

删除节点 \(x\)

我们需要先将 \(x\) 旋转到根节点,从而去得到它的前驱和后继。
然后将前驱旋转到根,再将后继旋转到根,就会得到下图:
平衡树学习笔记
直接把 \(x\) 删去即可。

查询区间 \(\left[l,r\right]\)

我们需要将 \(l\) 的前驱旋转到根,再将 \(r\) 的后继旋转到根节点,点像删除操作。
\(l\) 前驱的右子树就是整个 \([l,r]\) 区间了。

fhq_Treap(无旋Treap)

前言

首先,我们要 \(sto\) 范浩强 \(orz\)
dalao 发明了 fhq_Treap,因为 fhq_Treap 是三种平衡树中最强悍的一种了,它可以维护值域,可以维护下标,可以维护区间修改,它还可以完成可持久化操作。其唯一弱于 splay 的就是在维护 LCT 上。

什么是 fhq_Treap

fhp_Treap 首先是一个 Treap。
而 Treap 是什么呢
Treap=BST+Heap。
所以 Treap 就是一个拥有二叉搜索树的性质,但是每一个节点都通过一个附加权值来满足符合堆的性质。
而这个附加权值就是 Treap 的一个关键,它是通过随机生成一个 \(key\) 来维护一个近似的平衡。
而我们随机生成的 \(key\) 要想让它退化成链的概率是微乎其微的。(教练:你让随机 \(key\) 退化成链的概率就像你出门被核弹直接创死的概率一样小。)
但是一个旋转的 Treap 是有点恶心的。
所以,我们的无旋 Treap 就登场了。

核心操作

我们要想 Treap 不旋转,我们就需要一个可以顶替旋转的一种操作来实现,那就是拆分与合并。

split

split 就是把 Treap 以 \(k\) 值分为两棵 Treap。
对于我们遍历到每一个点,假如它的权值小于 \(k\),那么它的左子树,就要分到左子树里,然后再遍历它的右儿子,反之亦然。
因为它的最多操作次数就是一直分到底,时间复杂度就是 \(O(\log n)\)
对于前 \(k\) 个版的,就像找第 \(k\) 大的感觉。每次减掉 \(siz\)
这个用递归就可以实现了。

merge

merge 就是把被分开的两颗 Treap 合并起来。
因为第一个 Treap 的权值都比较小,我们比较一下它的 \(kay\),假如第一个的 \(key\) 小,我们就可以直接保留它的所有左子树,再把第二个 Treap 变成它的右儿子,反之亦然。
也就是说,我们其实是遍历了第一个 Treap 的根定为最大节点,第二个 Treap 的根就是最小节点,时间复杂度就是 \(O(\log n)\) 了。

操作实现

插入数值

插入一个权值为 \(v\) 的点。

  • 把 Treap 以权值 \(v\) 分成两颗。
  • 将权值 \(v\) 插入。
  • 再把两颗 Treap 合并以来。
    平衡树学习笔记

删除数值

删除一个权值为 \(v\) 的点,很类似于插入操作。

  • 把 Treap 以权值 \(v\) 分成两颗。
  • 将权值 \(v\) 删去。
  • 再把两颗 Treap 合并以来。

查询指定值的排名

如果是在一个有序的序列中查询排名,我们可以二分查找这个序列,然后根据找到的元素的下标来确定排名,假设下标从 \(1\) 开始,那么排名就为该元素的下标 \(i\)。那么,在它之前,也就有 \(i−1\) 个元素。由此,我们可以得到排名的一种定义:在有序序列中,一个元素的排名就是它前面的元素的个数 \(+1\)
在 fhq_Treap 上,我们就直接按 \(key−1\) 分裂树,查一下值小于等于 \(key−1\) 的树的大小,再 \(+1\) 即可。

总结

平衡树大体就利用 BST 性质,通过一些如旋转,分裂合并的操作来实现将我们需要进行修改的节点或子树独立出来,在进行修改。文章来源地址https://www.toymoban.com/news/detail-438189.html

到了这里,关于平衡树学习笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 论文笔记:基于概念漂移的在线类非平衡学习系统研究

    论文:A Systematic Study of Online Class Imbalance Learning With Concept Drift 发表:2018年发表在TNNLS上 源代码:? 作为一个新兴的研究课题,在线类非平衡学习往往结合了类非平衡和概念漂移的挑战。它处理具有非常倾斜的类分布的数据流,其中可能发生概念漂移。它最近受到越来越多的

    2024年02月11日
    浏览(76)
  • Qt学习笔记之二--创建一个简单的qt互动界面(超级无敌巨详细,0基础也能会,主打的就是图多,语句通俗)

      选择第一个选项,然后两个下一步------ 直到   这里要选择基类,我们选择Qwiget  至于为什么,可以看看我收藏的这篇博客QMainWindow和QWidget的区别_qwidget和qmainwindow_独行侠_阿涛的博客-CSDN博客 ok,创建完成后,我们使用快捷键Ctrl+R来运行一下,看看是否会弹出小窗口,弹出说

    2024年02月05日
    浏览(54)
  • Vue3学习(仅为了记录,参考意义不大)

    vue-cli是创建vue2.0的脚手架工具,create-vue是创建vue3的脚手架工具,create-vue构建速度非常快 setup语法糖: 总结: 开启深度监听同样的写法 beforeUnmount和unmounted对应beforeDestoryed和destoryed defineProps原理还是props,只不过在setup里面可以去接收使用 父组件里面写v-model,子组件里defi

    2024年02月09日
    浏览(36)
  • 为了快速掌握使用 ChatGPT,我应该着重学习什么?

    当然!下面是更详细的学习计划,包含了每个章节的内容和建议的学习时间: 章节一:ChatGPT简介 ChatGPT是什么(10分钟) 了解ChatGPT是一个基于深度学习的自然语言处理模型,能够生成人类般的对话回复。 应用领域和用途(10分钟) 探索ChatGPT在客户支持、虚拟助手、教育等领

    2024年02月12日
    浏览(75)
  • 为了实现上网自由,我做了一个多功能串口服务器

    项目作者:小华的物联网嵌入式之旅 介绍:从事电气自动化行业,多次获得物联网设计竞赛,爱好嵌入式设计开发,物联网开发。 设计方案思路的由来,是因为我们现在的开发板基本需要通过串口与WIFI模组或以太网模组连接以实现联网功能,如果多个开发板就要配多个模组

    2024年02月12日
    浏览(37)
  • Go中第一类函数

    什么是第一类函数? 支持第一类函数的语言允许将函数分配给变量,作为参数传递给其他函数,并从其他函数返回。Go 支持第一类函数。 在本教程中,我们将讨论第一类函数的语法和各种用例。 匿名函数 让我们从一个简单的例子开始,它为变量分配一个函数。 Run in playgr

    2024年02月05日
    浏览(29)
  • 关于credal set和credal decision tree的一点思考(其实就是论文笔记)

    阅读Abellán老师的Credal-C4.5时,发现好难。。。然后又额外补充了一些论文,终于稍微懂一点点了,所以记录如下。 credal set在DS theory的定义如下 [1]: 这句话的意思是(证据理论中的)credal set是一个概率的凸集,这里面的概率p(x)受到上界pl函数和下界bel函数的控制(约束),

    2024年02月12日
    浏览(44)
  • 【阅读笔记】一种暗通道优先的快速自动白平衡算法

    自动白平衡算法中存在白色区域检测错误导致白平衡失效的问题,作者提出了一种基于暗通道优先的白平衡算法。 图像中白色区域或者高饱和度区域的光线透射率较低,根据以上特性利用暗通道法计算图像中白色区域。 作者使用何凯明提出的基于暗通道优先的方法来估计光

    2024年02月15日
    浏览(42)
  • Amazon SageMaker简直就是机器学习平台的天花板

    最近参与了亚马逊云科技【云上探索实验】活动,通过Amazon SageMaker基于Stable Diffusion模型,非常简单快速搭建的第一个AIGC,一开始以为非常复杂,不懂动手操作,但实际上操作非常简单,没有想象中的恐怖,整体体验非常愉快,我先对Amazon SageMaker简单介绍,然后对基于Stabl

    2023年04月09日
    浏览(52)
  • 加密货币量化交易系统的设计与实现(0.1最初版本,为了应付毕设的版本)

    注意: 写这个程序的目的是进行加密货币投资理财,但是我刚好要毕业了,需要些毕业设计,所以和导师商量了一下把原本的《基于表情识别的人工智能睡眠质量监测助手》换成了我自己的《加密货币量化交易系统的设计与实现》,这个设计里的后端服务模块(基于springbo

    2024年02月02日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包