平衡树

什么是平衡树?


顾名思义,是一种平衡的树。


首先需要申明一个概念:二叉搜索树。

二叉搜索树:

二叉搜索树是一种十分神奇的树,也可以叫做二叉排序树、二叉查找树。

一个牛逼的性质:(多数情况下,也有例外)

对二叉搜索树而言,若它非空,每个节点的左儿子总是比他小,每个节点的右儿子总是比他大。

对于二叉搜索树的查找而言,是靠递归调用实现的,期望的时间复杂度是:\(O(nlogn)\)

那么就一定会有特殊情况,比如当数据很诡异的时候,这颗树就会退化成一条链,那么处理的时间复杂度就会变成:\(O(n^2)\)

所有我们在这个的基础上,就有了平衡树的概念。

平衡树的分类

一、treap

二、splay

三、RBT(红黑树)

四、AVL

是的以上四个,在本篇笔记中会涉及前两个,并且很草率地给出几段代码,以及浅显的涉及一下三和四。


在一般的二叉搜索树当中,如果退化换成了一条链,那对于所写的数据结构而言没有任何时间和代码量的优势。

所以在这个二叉搜索树上维护一个堆,是的,维护一个\(Heap\)。

\[ Tree + Heap= Treap \]

一、Treap

\(Treap\)是一种平衡树,但是他自己首先也是一颗二叉搜索树,其左子树和右子树也均为一个\(Treap\)。

\(Treap\)在一般二叉搜索树的基础上,还额外记录了一个数据,即为优先级。(假设节点的优先级大于该节点的孩子的优先级)
值得一提的是,对于\(Treap\)而言,它是一颗二叉搜索树,但是不一定是一个完全二叉树。与二叉堆不同。

Treap的各种操作

一、插入一个数K

因为满足二叉排序树,所以我们可以从根节点开始往下查找,每找到一个节点\(O\),会有如下四种情况:

1、\(O\) 为空,那就创建新节点,初始化,赋值\(key\)、\(pri\)。

2、\(k == O.key \)那么直接把 \(O.val + 1\) 即可。

3、\(k\)小于当前节点的\(key\)值,那就进入该节点的左儿子找。

4、\(k\)大于就去右边哇\(QwQ\)

但是简单的加完之后还要满足\(Treap\)的性质,所以我们还需要考虑在当前情况不满足堆的性质的时候的操作。

因为维护的堆性质不同,所以操作也不一样,维护大根堆和维护小根堆的操作相反。

旋转

左旋or右旋

image

从左边到右边的就是左旋,反之就是右旋。
经过观察可知,在旋转前后,这一部分的中序遍历均为BADCE,即旋转不破坏二叉排序树的性质,所以我们维护这个Treap的方式就是旋转啦。

我们首先来分析一下时间复杂度,旋转的操作是\(O(1)\)的,最多进行H次操作,所以插入的时间复杂度就是\(O(H)\)的,在期望的情况下\(H=O(logn)\),所以它的期望复杂度就是\(O(logn)\)。

回顾一下刚才的那个图,核心的节点是A和C,旋转时只需要调整节点D的位置,再调整A、C的父子关系,最后再维护完\(val\)和\(size\)。

再创建完新的节点之后,可以得到根节点到这个新节点的一条路径,递归回溯时,对这条路径上 的每两个点:将优先级大的放到父节点上去。看节点在左还是在右,就知道是进行左旋还是右旋。

原图
image

插入\(C-25\)
image

插入\(D-9\)
image

左旋
image

右旋
image

插入\(F-2\)
image

左旋
image

左旋
image

左旋
image

右旋
image

二、删除一个数K

因为\(Treap\)满足了堆的性质,所以当要删除的点在叶子节点的话直接删除就可以了,至于不在叶子节点的节点,需要找到优先级最大的儿子,向相反的方向旋转(既让优先级大的儿子至于尽可能高的位置)

删除最多进行 \(O(H)\)次旋转,期望复杂度是\(O(log n)\)

三、查询数K的排名

从根节点开始往下找,判断当前节点的\(key\)值。

大于\(K\)就继续向当前节点的左节点去找。

等于\(K\)就返回当前节点的左子树的\(size\)值+1。

小于\(K\)就先把答案加上当前节点的左子树的\(size\)值以及当前这个点的\(val\)值(\(val\)个相等的值)之后一点一点往下找就行啦\(QAQ\)。

因为\(Treap\)是随机化结构,所以可以证明\(Treap\)中查找的期望复杂度是\(O(logn)\)

四、查询排名为K的数

与第三个类似,递归查询。

\(K\)小于当前节点的左子树的大小,向左子树去找。

当\(K\)大于左子树的大小却小于左子树的大小+当前节点的\(val\)时,那么就说明该节点的\(key\)就是答案。

若\(K\)大于左子树的大小+当前节点的\(val\)时,向右边去找就可以了,但是\(K\)在向下递归的时候,需要减去左子树的大小和\(val\)

五、查询数K的前驱

前驱:在一段有序的序列里面最后一个比K小的数。

首先,因为是最后一个比\(K\)小的数,所以这个数一定在\(K\)的左子树上面,找到左子树就要向右子树啦,因为要保证尽可能的大,更新答案,答案赋一个极小值。

六、查询数K的后继

后继:在一段有序的序列里面第一个比\(K\)大的数

与操作五正好相反。\(QAQ\)


举个栗子:

bzoj3224普通平衡树

题意:写一个具有插入、删除、查\(rank\)、求前驱、后继功能的平衡树。\(N<=100000\)。

一句话题解:纯模板,记得在左旋右旋和\(insert\)中加取地址符,这个叫做引用,在子程序中改变该变量的值会导致主程序中该变量的值发生改变,类似将局部变量局部地拓展到某一个子程序中,变成一个类全局变量。

code


Another:

bzoj3173最长上升子序列

题意:给定一个空序列,将\(1—N\)数字插入序列中,给定插入的位置,每插入一个值求\(lis\)。\(N<=100000\).

一句话题解:正常的平衡树维护一个\(lis\),根据其中序遍历求这些\(lis\),用\(dfs\)把中序遍历存在一个数组中,跑一次\(lis\),存在数组里,然后输出\(N\)个局部最大就是答案啦。

code


二、Splay

\(Splay\)又称为伸展树,是对于二叉搜索树的一种改进,和二叉搜索树一样,伸展树也具有有序性。对于一个节点\(x\),左子树的每一个元素都小于\(x\),右子树的每一个元素都大于\(x\),同时\(Splay\)也具有其本身的旋转操作,多数为双旋,并且双旋的速度会优于单旋。

旋转:

\(zig\):右旋。

\(zag\):左旋。

将旋转组合一下,会得到奇特的效果

比如\(zig-zig\)

图片

第一次\(zig\),\(g\)成了\(p\)的右儿子,\(p\)的右儿子继承给了\(g\),\(g\)成了根,\(g\)的左子树不变。

第二次\(zig\),\(x\)成了根,\(p\)成了根的右儿子,所以\(p\)就继承了x的右儿子,\(p\)的右子树不变

至于\(zag-zag\)与上图类似。

着重讲一下复合旋转。

image

例如这个图,就需要\(zag-zig\)

首先\(zag\)一下,就成了一条链,\(p\)的右儿子继承了\(x\)的左儿子,\(c\)不变,\(a\)不变。

再\(zig\)一下,就变成了第二个图的样子。

特别重要的一点就是在旋转中他的中序遍历是不变的

如何快速判断这个中序遍历是啥?把这个树压扁然后就可以看到,两个节点中间的点仍然在两个节点中间。

\(zig-zag\)与\(zag-zig\)是不一样的!!

多种操作

查找第K大的数

首要的是要把标记下传,因为每次传标记可能还没有传到叶子结点,然后再判断当前这个点和当前这个节点的左子树大小的关系。往下找就行了

旋转某个点到某个点

首先下传标记,然后要不断的旋转,保证这个点到了要旋转到的点才停止,找到三层关系,之字型就符合复合旋转的操作,链式就是符合多次相同方向的旋转的操作

^ 就是两边相同就是真,相反就是假,59行的if就是判断他是不是之字形操作

之字形就是两次\(rotate(o,x)\)。

链形就是一次\(rotate(o,y)\),一次\(rotate(o,x)\)。

在\(rotate\)里面传进去的\(x\)或者\(y\)意思就是,把\(x\)节点或者\(y\)节点由下移到上去。

rotate

首先要把这个点三层关系找到,自己父亲爷爷,看看他们是不是全在各自的右节点的位置,如果都为0那就都在左节点的位置上,都为1就都在右,有0有1就表示是之字形的关系,然后下传标记

如果要移动到的点刚好是这个点的父亲节点,就直接移动。

不然就去分析其左右节点关系和继承儿子的关系,因为有 ^ 的存在,所以只用判断 ^ 的结果就好了

pushdown

如果当前节点的\(rev\)存在,就旋转左右子树即翻转左右区间。同时标记还要下传。

reverse

就是交换左右子树,即交换翻转区间

pushup

总结左右儿子的大小并且还要加上自身的一个

print

以其中序遍历输出,记得判断\(o\)得在\([l,r]\)区间输出

三、RBT

一、每个节点要么是红的,要么是黑的

二、根节点为黑

三、叶子结点为黑

四、若自身为红,则左右儿子为黑

五、每一个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑节点

六、红色节点向左倾斜

\(RBT\)有较多版本,一些为链为红或者黑,还有一些为点为红或者黑,但是红黑树是一种具有两种颜色的平衡查找树

旋转与\(Treap\)的旋转一样,但是颜色会出现一个翻转=。=然后就不会啦\(QAQ\)

红黑树博客

四、AVL树

特点:任何节点的两个子树的高度最大差别为1,但是对于\(AVL\)树而言有4种旋转方式,对应的是\(AVL\)树的四种情况,有\(LL\)、\(LR\)、\(RR\)、\(RL\)四种,因为最大高度差不能大于1,所以会有不平衡,然后对应起来去转就可以了.

QAQ后面我也不会啦

AVL树博客


By:Wahacer

资料来源

Treap:xqmmcqs——数据结构-Treap

Splay:IOI2004 国家集训队论文 杨思雨

RBT:结构之法算法之道blog之博主

AVL:AVL树(一)之 图文解析 和 C语言的实现

2017年9月20号

发表评论

电子邮件地址不会被公开。 必填项已用*标注