大家好。数据结构与算法这一讲我们介绍第十二章
高级数据结构的最后内容也就是BST中的
伸展树。 那伸展树呢它是一种自组织的数据结构。
所谓自组织的数据结构呢也就是说
在这个数据结构的使用过程中我们根据它的一些使用频率等等这些情况呢进行调整。
例如我们在输入法里面我在输入一个词的时候,如果经常
使用这个词,那这个词呢就会在我这个词表里面慢慢的往前提。
然后就方便你能够检索得到。那这个是自组织的线性结构。
那对于我们BST来说呢我重要的是保持
它在中序的便利下是一个有序的。
那因此呢我们也是可以对它进行一些 调整,也就是说我并不在乎谁是树根,
那我如果是说我经常检索某一个关键码
那如果我能够有一种方法能够把它调到靠近根的这么一个位置,
那总体来说我整个这个检索这一组关键码的
情况呢我可能会达到统计上头的更优的一个性能。
那因此呢Tarjan就提出了一种叫做伸展树的这么一个
BST的结构。那这个伸展树它其实
对BST不进行任何的修改,它也不要着色,也不需要什么平衡因子。
只需要做什么呢?也就是我每次操作的时候 都去给它伸展一下,
把当前这个结点给它调整到根,这是它的一个实质的内容。
那这样的话,我们总体的统计性能是非常好的。
伸展树是一种非常实用的一种数据结构。
那我们调整的方法呢,
那分为几类情况。 有一类呢就是如果我这个当前结点它就在
我这个整个BST的根结点底下, 那我为了把当前结点调整到根,
我就是只需要进行一个单旋,那这个单旋呢我们
有一种是右旋zig,还有一种是左旋zag
这两个是对称的。那如果是它在比较靠近叶的方向、比较深的方向怎么办呢?
我为了让它尽快的达到根, 那我可以是三个关键码一组,这三个呢就是我当前结点,
我的父结点以及祖父结点。
那这三个结点一组的情况,那我们也是分为几类,那第一类呢就是一字形的。
那这个一字形呢我有一种是这个都在左边这样一瞬溜,
那还有一种呢是在右边一瞬溜,那这两种情况我们是对称的。
那如果是说我当前结点是X,它在孙结点的这个最底层的位置,
那我能够把它往上面抬的话呢我就是希望
给它抬到这三个结点里面的作为根结点。
那我就一直把它给拉到一个根的位置,
那我们就是这么转过来让X作为根结点。 那相应的呢也是对称的情况。
那在我们这么一个之字形的旋转中呢,
那我就是 当前结点,然后父结点和祖父结点它们
不是同一个方向,它可能是中间打了一个折
那这种情况呢,我为了要把这个孙结点 作为整个这个新的子树的根,
那我把它拿上去以后呢它的父和祖父
就分别挂在这个原来的孙结点的左右两侧,
那双旋呢它也是有两种这样的对称的
情况,我们都是往中间靠,也就是说调整完了以后都是
中间这样的一个支架形的一个看起来似乎比较平衡的结构。
那我们转完以后都是要保持BST
在中序便利下它还是一个有序的序列。
那我们看我这个Splay的过程其实呢它
本质上就是我从当前访问的这个结点出发,然后往根的方向,
我这个操作是在对于这个插入还有删除和检索
都是这样子进行,就是我这个操作的路径呢就是
我当前结点,然后呢再三个一组,我把这个当前结点旋到这三个结点的根,
然后我接着呢再从这个当前的新根出发
又往上面去找父结点、祖父结点,又是三个结点组成一组
那又去旋转,我一直这样子往根的方向去操作,
那一直到根的时候呢如果我跟
根结点是中间隔了两层,也就是说我还有父结点,父结点的父才是根,那还是三个一组,那就完成了这样的一个操作。
如果是说我旋到,到根的时候我自己的父结点
就是根结点了,那我就是两个一组作一组单旋的操作。
因此呢这个伸展树它最重要的就是
在当前结点完成了某一个插入删除或者是
检索的操作之后,我做一组旋转,把它给转到根 插入
和检索还比较好说,也就是我当前 刚操作过的那个结点,比如说刚插入呢就是那个新结点,
那它是个叶结点,那检索呢就是我检到哪就是那,然后我把它往上面
传,传到根。删除呢其实也很好办,就是我可以定义
我刚才被删的那个结点它的父就是我的当前结点,或者呢你也可以做别的定义,就是
比如说因为我们BST里面删除我是要找到左子树的
最大或者是右子树的最小
来替换这个当前的被算结点,那我也可以把这样的一个
实际的被删的那个位置的结点呢我给它作为
就是被删的结点,然后它的父结点我作为一个当前结点再往上面调整。
那我们再来细致的看一下
伸展树它的调整的过程。首先呢我们来看单旋,那假设
我这个当前结点x是作为y结点它的一个左子孩子,
那这个y结点如果我真的做单旋的时候,它一般来说是一个根的结点。
那我们转完以后呢,x作为新的根,然后y呢作为它的右孩子。
我们来看一下这个双旋结构。那这个双旋里面呢它有一类是一字形的双旋,还有一类是
之字形的双旋。那我们这个双旋呢它其实是涉及到当前结点,
它的父结点和祖父节点这三个一组,然后我们看它是一边顺的情况呢就是一字形的。
那如果是中间转一下就是之字形的,那我们看这个一字形的情况呢,我们其实
是做了两次的单旋,也就是说我们在
伸展树里面它其实最本质的操作就是这个单旋的操作,也就是说
zig往右旋,zag往左旋,那其它的操作都是由它来组合。
那回顾我们前面的这些红黑树还有AVL树,
它其实本质也这样,你如果是定义好了这个zig和zag操作,那
其它的操作都可以用这两种操作来组合。
那我们来看对于这样的一个左偏的这样的一个
一字形的情况,那我们这个单旋呢我是先要拿这个
父结点y跟它的祖父节点做一个zig,那我把它旋上去,
然后呢我再把这个当前结点和它的这个父结点呢
再做一次zig,也就是说两次zig,那注意这两次它的顺序是不能变的。
如果变了的话呢那我们得不到这样的一个结构。
那我们再来看之字形的
这样的双旋,那这个双旋的话呢那我们是从这个
孙结点出发,然后跟它的父结点
要先进行一次旋转,然后
我把这个当前结点转上去以后呢
它又跟这个祖父节点呢再进行一个单旋转。
那也是要注意这个操作的过程呢也是不能够乱的,像我们刚才
是这样的一个LR形的这样的一个结构。
那我们刚才旋的过程呢应该是先做这样的一个zag的
左旋,然后呢把x旋上去以后它再跟zig呢
做一个zig的右旋,这个也是不能够变的。
那我们可以看到伸展树它的调整过程,它其实是
一系列的双旋,然后就到,快要到根的时候呢,我再来看
是不是,嗯,还能双旋,不能双旋的话我再进行最后的一次单旋
然后就完成了这样的一个操作。
那整个这个过程它会使得数字结构呢
趋于平衡,而且我们在统计的意义下呢,
它确实是一个能够达到一个每次操作是log n的代价。
也就是说,总体来说树是比较平衡的,不会有退化成单链的这么一个情况。 那我们,
嗯,来看这样的一个例子。那我首先呢是检索到了A
这个节点。从 A 出发,那我三个三个一组来进行,嗯,双旋的操作。
那首先呢,那就是a它的父是b,然后它的祖父是c.这是一个一字形的结构。
那我们也是,嗯, 先要从父,嗯,跟祖父那一组单旋。b、c
选好了以后呢我在a呢,绕着b再做一次单旋,然后就完成了。
那我们这个a呢它旋到了这三个结点里面作为新的子树根,
然后我再往上面去找它的父和它的祖父。
这三个结点呢是之字形的这样的结构,那我们做双旋的调整。
然后,a又成为新的子树根。
然后呢,我们,嗯, 接着呢
往上面再找三个结点,嗯, 形成双旋。 嗯,双旋完成以后呢,
a就旋到了这个根结点的下面作为它的子孩子,
那这个时候我们就只能做一次单旋。那
单旋完了以后我们把a旋成了这个整个伸展树的子树根, 那我们的操作就完成了。
Splay的实现非常的简单,我们只需要将一个副指针
就是因为我们经常会要往根的方向上
追溯这些相应的祖先结点。 那在splay
里面呢,我们把这个,嗯,这个结点旋到根 是一个,嗯,
我们前面介绍过的,嗯,最常见的操作。 那还有更通用的操作呢是
把这个当前结点x旋转为它的
祖先路径上某一个结点f 它的子结点。
那这个操作呢它其实,嗯,也可以,嗯,用来实现我们前面说的
把这个x 旋转到根的操作。也就是我如果是
这个祖先路径上头的这么某一个结点,嗯,这个f 我把它复制为空
那就是它一个特例的的情况。那其它的,嗯,查找、插入、删除
跟前面的BST是非常类似的。那不同呢就是
我所有的这些相关的的操作之后,我都要记得做一次Splay。
那当然是对当前的结点作一次Splay,
那这样的话呢,我们能够使得这个伸展树 它能够达到很好的统计的性能。
那我们来看Splay操作,嗯,它的实现。
那这个Splay呢是,嗯, 把我这个当前结点x旋到它的某个
祖先结点f下面,作为f的孩子。
那首先呢我们定义这个当前结点
它的父结点是y,嗯,然后它的祖父结点是z的。
首先我们来看这个y结点是不是就是f
结点的子孩子。 如果是的话呢,那我们就不能够把这个x、y、z
这三个一组去旋转,那否则就是
这个,嗯,x作为根啦。它把这个整个这个f 呢又转在它自己下面。这就不行了。
因此,嗯,在这种情况下呢,我们就是只能是x
跟y呢做一下单旋。 那就是说,原来x是,嗯,这个,嗯,这个z它的一个孙结点。
那我现在单旋以后呢,把x 作为这个z的一个子结点。那
嗯, 也就是说,我因为是z这个等于这个f
的情况, 那这个时候呢就相当于我们已经完成了这样的一个操作。
那如果是说,嗯,我,这个y结点它的父结点呢
还不是f。也是说还离开远着呢!那我们就可以放心的
去做这样的一组双旋。 那这个,嗯,双旋呢就是
我首先看一下,嗯, 假设这个z呢它的左孩子是y,
也就是说,我们这个y呢是从z这个左边来的。
然后,我再看x跟y的这个关系,如果x还是从左边来的,
那其实我们就是做一字形的双旋。那这个双旋是
双应旋,而且一定要注意是先转这个父结点y,
再转这个,嗯, 当前结点x然后
就可以完成这样一组操作,这个顺序是不能够变的。
那如果是,嗯,x是y的右孩子,
那这个时候我们是进行之字形的调整。 那进行之字形的调整呢,注意这里呢是要先从
嗯, 我们孙结点的方向往父结点,嗯,往下面免去调整。
那这种情况呢那就是我先做一个 左旋zag,嗯,爸爸x呢调上去。
然后接着它调上去以后,x跟z这个呢,再去做一个zig。
嗯,那这个两个操作都是对x进行,that's
why 注意这个x它是发生了变化的。而且我们要注意需要从这个最底层往上面去做这两次旋转。
那,嗯,另外一组情况就是对称的啦,也就是说
嗯,这个,嗯,y是z的右孩子。
那如果,嗯,我们这个y呢
它的父结点就是等于f了。
那这个时候呢,也就是说我x呢
是要跟y做一个单旋。我把x调上去 作为这个f的子结点就行了。
就完成我们这个操作要求。那这个时候呢,我们就是,嗯,来看一下如果是x
作为y的左孩子,那我们就
嗯,对x做一个这样的右旋zig,否则呢,我们做一个
嗯,左旋的zag 。那如果是我们完成操作以后
这个,嗯,当前结点x它的父结点呢是空了
那这种情况是,嗯,什么情况呢?
这就是说 我整个这个x 节点它是作为伸展树的根结点了。
那因此呢我们就需要修改,嗯,这个权据变量root
我们把它登记为是x。 当然我们也可以
嗯,把这个root作为我们这个函数里面的参数
来传递,那里是作为一个权据变量来给它进行维护的。
那对于这个Splay树呢,我们有很多很多的应用。
那这些应用我特别是适合处理一些,嗯,一系列的这些元素的情况。那我们这里来看一下
这么一个例子。那如果是说我要求你删除
嗯,大于u小于v的这些所有结点,而u、v呢是我传递给你的
这个伸展树里面的,嗯,这两个结点。那u呢是要小于v的值的。
那这个运用呢非常的简单,
我首先呢就是把u给它转到根,
那就,嗯,保证它是v的祖先结点。 然后呢,我们运用前面的,
嗯,Splay 操作。 我把v 转到作为u的一个子结点,
因为v比u大所以呢,嗯,这个v呢也就是作为
u的右子的孩子。
那大于u 小于v 之间的所有结点其实就在这个
v结点的左孩子这一个分支,那我们把整个这个左子树都删掉就行了。
我们看这个例子,那我们假设我们要找的u呢是 35
那我们的v呢是60 。那经过旋转我们让这个 嗯,
u呢是一个子树根,然后v呢就是它的 右子孩子。那这个
v的整个左子树就是所有的处于u、v之间的这些结点。 那我们把这个左子树删除就行了。
那这个函数的操作非常的简单,那首先呢调用splay我们把u传到根,
那它的参数呢就是u和NULL,
嗯,那就是NULL是作为,嗯,u的一个祖先路径
上的某一个结点,我们特殊定义NULL呢就是 我让u当作子树根了。
那接着呢我们再调用Splay,我传的参数是v,
然后它的一个祖先的节点是u,那就是把v给
旋转成为u的一个直接的子结点,那在这里是它的
右子结点,那接着呢我把v的整个左子树都给删除,那就完成了这个操作。
Splay树它是一个在均摊意义下头的平衡的二叉搜索树。
那如果是说有n个结点 我有m组操作,当然这个m是要大于等于n的,
那我们可以证明呢在均摊意义下
这一组操作它总共的时间是m乘以log
n的这个代价。
那因为是总共有m个操作,因此均摊到每一个操作呢它的代价就是log
n的。 也就是说如果我一直维持Splay的这样的
性能,也就是说它的这样的一个操作过程,每次
插入删除和检索之后我都做一次Splay
那我就可以使得这个树再统计一下它是平衡的。
我们能达到一个非常好的检索性能,而且因为它的维护呢是非常简单的,
那因此Splay树是得到了非常广泛的应用,是很实用的一种索引结构。
那我们再来看一下生产
树的一些变种,譬如这个半伸展这样的一个变种。
那它的一个区别呢主要是对一字形的旋转。
那我们前面一字形的旋转呢我们是把这个当前结点
跟它的父和祖父整个给它翻一边,
然后把当前结点作为子树根,然后父呢作为它的孩子,然后呢祖父作为它的孙结点。
那半伸展呢它是对这样的一字形的它把它变成一个支架形的这样的一个结构。
那这里呢这个当前结点x它并没有传到这个新的子树根,那没有关系。
我后面的操作呢,我把这个当前结点 转为这个x结点它的父结点,然后再往上面去
找另外的这个两个结点,三个一组进行继续的操作。
对于我们支字形的那个旋转呢,它的旋转结构是类似,
但是它在继续做旋转的时候也是我并不拿
前面这个当前结点x来继续操作,我只是用它的
一个父结点作为新的当前结点然后再去找一组继续操作。这个呢就有点像我们输入法里面呢
我并不是说把我刚检的这样的一个词就直接贪心的放在
整个这个跟拼音对应的这个词表里面的第一个,而是
慢慢慢慢的往上传。那大家思考一下
这样的一个半伸展跟我们前面的全伸展它有什么样的不同的应用场景?
然后给大家一些思考题呢就是我首先还可以
调研一下Splay有哪一些各种变种,还有就是它有什么样的应用。
另外呢我们可以对一些开元的像
STL啊还有一些Linux操作系统啊这样的
开元的系统啊我们去调研一下,看看
Splay还有红黑树、AVL树它们的应用情况是什么样的
我们可以发现在早期的开元的一些项目里面呢AVL还是大量存在的,
那现在呢是更多的被红黑树和Splay所取代,因为红黑树相对
AVL树呢它的这个统计性能呢要好一些呢,而且它更易于维护,更易于编写。
那Splay呢它就更方便实现了。那大家去
比较一下这些开元系统里面我们这几种
平衡的二叉搜索树它的应用情况。
谢谢大家。