首页 > 笔记 > 左偏树学习总结

左偏树学习总结

在学OI的前期,我们接触了一种数据结构,叫做堆。它资瓷插入一个元素,查询最小/大元素和删除最小/大元素。然后就发现STL的$priority \ queue$可以直接用,非常的方便。

但是有时候题目让我们资瓷两个堆的合并,这样$priority \ queue$就不行了(但是pb_ds还是可以的)。这样我们就要手写左偏树。

什么是左偏树呢?首先,从名字上看,它是一棵树。其实它还是一棵二叉树。它的节点上存4个值:左、右子树的地址,权值,距离。

权值就是堆里面的值。距离表示这个节点到它子树里面最近的叶子节点的距离。叶子节点距离为0。下面提到的一个左偏树的距离也就是根节点的距离。

既然是一种特殊的数据结构,那肯定有它自己的性质。左偏树有几个性质(小根为例)。

性质一:节点的权值小于等于它左右儿子的权值。

堆的性质,很好理解。

性质二:节点的左儿子的距离不小于右儿子的距离。

在写平衡树的时候,我们是确保它的深度尽量的小,这样访问每个节点都很快。但是左偏树不需要这样,它的目的是快速提取最小节点和快速合并。所以它并不平衡,而且向左偏。但是距离和深度不一样,左偏树并不意味着左子树的节点数或是深度一定大于右子树。

性质三:节点的距离等于右儿子的距离+1。

没什么好说的= =

性质四:一个n个节点的左偏树距离最大为$log(n+1)-1$

这个怎么证明呢?我们可以一点一点来。

若左偏树的距离为一定值,则节点数最少的左偏树是完全二叉树。

节点最少的话,就是左右儿子距离一样,这就是完全二叉树了。

若一棵左偏树的距离为k,则这棵左偏树至少有$2^{k+1}-1$个节点。

距离为k的完全二叉树高度也是k,节点数就是$2^{k+1}-1$。

这样就可以证明性质四了。因为$n>=2^{k+1}-1$,所以$k<=log(n+1)-1$

有了性质,我们来讲讲它的操作。

1.合并

我们假设A的根节点小于等于B的根节点(否则交换A,B),把A的根节点作为新树C的根节点,剩下的事就是合并A的右子树和B了。

合并了A的右子树和B之后,A的右子树的距离可能会变大,当A的右子树 的距离大于A的左子树的距离时,性质二会被破坏。在这种情况下,我们只须要交换A的右子树和左子树。

而且因为A的右子树的距离可能会变,所以要更新A的距离=右儿子距离+1。这样就合并完了。

代码

我们来分析一下复杂度。我们可以看出每次我们都把它的右子树放下去合并。因为一棵树的距离取决于它右子树的距离(性质三),所以拆开的过程不会超过它的距离。根据性质四,不会超过$log(n_x+1)+log(n_y+1)-2$,复杂度就是$O(\log n_x+\log n_y)$

2.插入

插入一个节点,就是把一个点和一棵树合并起来。

因为其中一棵树只有一个节点,所以插入的效率是$O(\log n)$

3.删除最小/大点

因为根是最小/大点,所以可以直接把根的两个儿子合并起来。

因为只合并了一次,所以效率也是$O(\log n)$。

4.构造

把n个点构造成一棵左偏树的话,也非常常用。

第一种暴力的思想就是一个一个插入,效率$O(n\log n)$

第二种可以模仿一下二叉堆的构造

将n个节点放入队列。
不断地从队首取出两棵左偏树,将它们合并之后加入队尾。
当队列中只剩下一棵左偏树时,结束。

我们分析一下它的复杂度。设$n=2^k$,则复杂度为:

$${n \over 2} \times O(1)+{n \over 4} \times O(2)+{n \over 8} \times O(3)+ \cdots =O(n \times \sum_{i=1}^k{i \over 2^i})=O(n \times (2-{k+2\over 2^k}))=O(n)$$

5.删除任意节点

因为左偏树没有平衡树的性质,所以我们没法删除权值为特定值的点,也没法查找特定值的点的位置。

但是要删除某特定位置的点还是能做到的。我们先和删除最值一样,把它的孩子合并起来。

因为我们合并后的新树的距离可能会改变,所以要更新一下q的距离。

假如q的距离是p的距离+1,那么无论p是左右子树都不需要调整。

假如p的距离+1小于q的距离,就改下q的距离,而且假如p是左子树的话需要交换子树。由于q的距离小了,还需要更新它的父亲。

假如p距离变大了的话,看看p是不是左子树,是左子树的话就结束了。但是p是右子树的话,就有两种可能,假如p的距离仍然小于q的左子树,那就直接改q的距离就好了;大于的话还要换下子树,向上走。(在这里还有一种情况就是原来的左右子树距离一样,那就不用更新q的距离,直接结束就好了)

下面分两种情况讨论删除操作的时间复杂度。

情况1:p的距离减小了。在这种情况下,由于q的距离只能缩小,当循环结束时,要么根节点处理完了,q为空;要么p是q的右子树并且$dis[p]+1=dis[q]$;如果$dis[p]+1>dis[q]$,那么p一定是q的左子树,否则会出现q的右子树距离缩小了,但是加1以后却大于q的距离的情况,不符合左偏树的性质三。不论哪种情况,删除操作都可以结束了。注意到,每一次循环,p的距离都会加1,而在循环体内,$dis[p]+1$最终将成为某个节点的距离。根据性质四,任何的距离都不会超过$\log n$,所以循环体的执行次数不会超过$\log n$。

情况2:p的距离增大了。在这种情况下,我们将必然一直从右子树向上调整,直至q为空或p是q的左子树时停止。一直从右子树升上来这个事实说明了循环的次数不会超过$\log n$(性质四)。

最后我们看到这样一个事实,就是这两种情况只会发生其中一个。如果某种情况的调整结束后,我们已经知道要么q为空,要么$dis[p]+1=dis[q]$,要么p是q的左子树。这三种情况都不会导致另一情况发生。直观上来讲,如果合并后的新子树导致了父节点的一系列距离调整的话,要么就一直是往小调整,要么是一直往大调整,不会出现交替的情况。这样效率就是$O(\log n)$

但是说了这么多,有一个操作是还是$O(n)$的:找到某个节点所在左偏树的根。因为需要一直走father走到根。我试了好几种方法优化都实现不了。也许这就是让人理性愉悦的数据结构吧2333333

一个板子:luogu3377

目前效率第一,欢迎超越。

第二:luogu3273

这题多了几个操作。

1.合并两个堆:直接merge
2.把某个点加:把这个点删了,再加一个更新了权值之后的点。
3.整个堆加:在根上打mark
4.全局加:记个全局mark
5.查询单点:一路加上所有父亲的mark再输出
6.查询堆最大值:直接输出
7.查询全局最大值。。

第七个操作需要把所有堆的根提取出来再建个堆。每次merge都要把并进去的堆的最大值删掉,单点加和整堆加都需要更新最大值。

有很多细节要注意

效率也是第一。。

下一道luogu3261

这题就是每个点建个左偏树,记录这个点上的人。dfs的时候先把儿子上的人merge到这个点上,然后判断堆顶上的是否大于生命值,小于就弹出去。统计一下就好了。

效率还是第一。。

cogs526

裸题


8 COMMENTS

  1. attack2017-11-05 上午10:21

    你好,能问一下你的图片是用什么软件做的么?

  2. 好人35262017-12-07 下午11:08

    luogu3216是[HNOI2011]数学作业是一道矩阵乘啊。。。
    求原题

  3. Doube_Suzerain2018-05-03 上午11:14

    dalao,蒟蒻问一下:
    "若左偏树的距离为一定值,则节点数最少的左偏树是完全二叉树"
    这句话中的“距离为一定值”,是什么意思啊?是指根节点的距离一定吗QAQ

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×