伸展树（Splay Tree）是平衡二叉搜索树的一种形式。

相对于 AVL，伸展树的实现更为简捷。伸展树无需时刻都严格地保持全树的平衡，但却能够在任何足够长的真实操作序列中，保持分摊意义上的高效率。伸展树也不需要对基本的二叉树节点结构，做任何附加的要求或改动，更不需要记录平衡因子或高度之类的额外信息，故适用范围更广。

所谓的“数据局部性”（data locality），包括两个方面的含义：

1）刚刚被访问过的元素，极有可能在不久之后再次被访问到

2）将被访问的某一元素，极有可能就处于不久之前被访问过的某个元素的附近

充分利用好此类特性，即可进一步地提高数据结构和算法的效率。

这里之所以提到这一特性，是因为在伸展树中，我们会利用此特性，即访问过的节点会被放置到树根处，以便于下次访问。

当然了，这一策略与“自调整列表”类似，它就是通过“即用即前移”的启发式策略，将最为常用的数据项集中于列表的前端，从而使得单次操作的时间成本大大降低。

连续的 m 次查找，若采用 AVL 则共需 o(nlogn) 时间；而在伸展树中，我们能在一段时间查找后使得查找更快。接下来就让我们看看伸展树的具体内容吧。

所谓逐层伸展，即：每访问过一个节点之后，随即反复地以它的父节点为轴，经适当的旋转将其提升一层，直至最终成为树根。

旋转的方式自然是 zig 或 zag 方法。

随着节点 E 的逐层上升，两侧子树的结构也不断地调整，故这一过程也形象地称作伸展（splaying），而采用这一调整策略的二叉搜索树也因此得名。

然而，如果仅仅是这样，则会在最坏的情况导致效率十分低下，因此，为实现真正意义上的伸展树，还须对以上策略做点微妙而本质的改进。

下面来看看逐层伸展的最坏情况：

可以看到，在五次访问之后，树的结构又恢复到了初始结构。当然这一实例，完全可以推广至规模任意的二叉搜索树。于是对于规模为任意n的伸展树，

只要按关键码单调的次序，周期性地反复进行查找，则无论总的访问次数 

m >> n 有多大，就分摊意义而言，每次访问都将需要 O(n) 时间！

因此我们需要尽可能的回避这样的最坏情况出现，双层伸展能帮助我们解决这个问题。

首先我们应该明白，最坏情况的问题出在哪里？

1）全树拓扑始终呈单链条结构，等价于一维列表；

2）被访问的节点的深度，呈周期性的算术级数演变，平均为 O(n) 。

为了解决可能会出现的最差情况，下面来看看新的思路：双层伸展

所谓双层伸展，即：每次都从当前节点v向上追溯两层（而不是仅一层），并根据其父亲p以及祖父g的相对位置，进行相应的旋转。

构思的精髓在于：向上追溯两层，而非一层。

那么接下来就来看看具体的实现思路吧。

在 g, p, v 这三代节点中，如果呈现 “之” 字形，则他们的旋转与 AVL 中的双旋完全等效，也就意味着这样的情况下双层伸展与逐层伸展时别无二致。即采用的是一般双旋进行调整。

就像这样，虽然名义上是双层伸展，但是实际上的操作仍然是一般双旋：

实际上：双层伸展主要针对的是 zig - zig 和 zag - zag 的情况，这是因为最坏情况通常出现在一棵树只有左子树或者只有右子树的情况（即呈单链的时）。

来这看看具体的实现：（注意 g，p，v 的祖孙关系）

这张图的上半部分采用了一般的双旋，两次旋转首先旋转了“父节点”，然后旋转“祖父节点”。

而下半部分采用了双层伸展策略，即两次的旋转首先旋转的是“祖父节点”，随后旋转“父节点”。

从局部上看好像没有多大的区别，但实际上这些局部的细微差异，会彻底的改变整体情况。

这样操作的效果，是一旦访问坏节点，对应路径的长度将随即减半。

从而让最坏的情况不至于持续发生！需要注意的是，并不能完全避免最坏情况的发生，只是降低发生概率。

下面一张的直观效果更明显：

通常我们考虑的是三代祖孙情况，即 g -> p -> v 三者。但如果 v 只有父亲而没有祖父呢？

出现这种情况，则必有 parent(v) == root(T)。即 v 的父亲节点一定是树根节点！

每轮调整中，这种情况至多（且在最后）出现一次！

此时只需要视具体形态，做单词旋转：zig(r) 或 zag(r)。如下图：

因为伸展树的查找也会引起整树的结构调整，因此 search 也需要重写。

其中 zig 和 zag 的旋转操作，可以在教材查找对应的示例图进行比对。多思考！！！

在有了 splay 这个核心的节点伸展函数之后，下面的功能就会相较于简单的多！

与常规的 BST 中的 search 方法不同，在伸展树中由于涉及到节点的伸展，因此可能会改变树的拓扑结构，因此不再属于静态操作。

一般情况下，我们可以调用 BST 的插入算法，然后再将新节点伸展至根节点。其中会首先调用 BST:: search() 算法。

然而，在重写的 splay 方法中，已经集成了过 search 方法，因此这样的话未免太过繁琐，下面会给出一种更好的办法。

即直接在树根附近完成新节点的接入：（e大于t->data，在右侧嫁接）

1）通过伸展树的 search 直接定位到目标节点的父节点 _hot；并且 _hot 会被移动至树根节点处；

2）根据目标节点的大小与 _hot 节点的大小对，对把树拆成两部分，再将目标节点拼接上去；

尽管伸展树并不需要记录和维护节点高度，为与其它平衡二叉搜索树的实现保持统一，这里还是对节点的高度做了及时的更新。出于效率的考虑，实际应用中可视情况，省略这类更新。

同 insert 类似，我们仍然选择在树根附近完成对目标节点的删除！

1）通过伸展树的 search 方法找到目标节点，并将目标节点伸展至树根处；

2）在原右子树中找到最小值，令其作为新的树根节点；这个新的树根节点的值一定小于全部右子树，同时大于全部左子树。

将代码对照着图例理解起来并不难，但是其中有一句注释需要额外注意下：在 R 中再次查找 e：注定失败，但其中的最小节点必伸展至根（且无左孩子），故可令其以L作为左子树。

为什么在 R 中查找 e 后最小节点被伸展至根节点就一定没有左孩子呢？实际上着得益于二叉搜索树的特点：当找到最小孩子后，其在二叉树中一定是最小的值，则其他值都应该存在于该最小节点的右子树上，因此该最小节点一定没有左子树。

同时，如此不仅删除了v，而且既然新树根m在原树中是v的直接后继，故数据局部性也得到了利用！

在伸展树中，我们无需记录节点高度或平衡因子；编程实现也简单易行 --- 优于 AVL 树。

就复杂度而言，伸展树与 AVL 树相当，都是 O(logn)。

在伸展树中，充分利用了局部性，每一次的搜索操作，都会使得被搜索的目标提前至根，一段时间之后，常用的搜索结果必然会集中于根部附近，从而导致缓存的命中率极高。

其中 k 区域就是一段时间之后的缓存结果。效率甚至可以更高，达到自适应的 O(logk)。

前面已经提到，即使伸展树可以降低最坏情况出现的概率，但仍然不能杜绝单次最坏情况的出现。

伸展树不适用于对效率敏感的场合，例如手术操作系统之类的，必须拥有极快的反应速度。

复杂度的分析也稍显复杂。

最后，欢迎大家关注我的微信公众号：火锅只爱鸳鸯锅！

是c++程序 以正确运行过 完全正确 能从一个文本输入 从一个文本输出 用于对集合的划分 是一个经典问题的运行程序

谭浩强教授，我国著名计算机教育专家。1934年生。1958年清华大学毕业。学生时代曾担任清华大学学生会主席、北京市人民代表。他是我国计算机普及和高校计算机基础教育开拓者之一，现任全国高等院校计算机基础教育研究会会长、教育部全国计算机应用技术证书考试委员会主任委员。  谭浩强教授创造了3个世界纪录：（1）20年来他（及和他人合作）共编著出版了130本计算机著作，此外主编了250多本计算机书籍，是出版科技著作数量最多的人。（2）他编著和主编的书发行量超过4500万册，是读者最多的科技作家。我国平均每30人、知识分子每1.5人就拥有1本谭浩强教授编著的书。（3）他和别人合作编著的《BASIC语言》发行了1200万册，创科技书籍发行量的世界纪录。此外，他编著的《C程序设计》发行了600万册。他曾在中央电视台主讲了BASIC，FORTRAN，COBOL，Pascal，QBASIC，C，Visual  Basic七种计算机语言，观众超过300万人。  在我国学习计算机的人中很少有不知道谭浩强教授的。他善于用容易理解的方法和语言说明复杂的概念。许多人认为他开创了计算机书籍贴近大众的新风，为我国的计算机普及事业做出了重要的贡献。  谭浩强教授曾获全国高校教学成果国家级奖、国家科技进步奖，以及北京市政府授予的“有突出贡献专家”称号。《计算机世界》报组织的“世纪评选”把他评为我国“20世纪最有影响的IT人物”10个人之一（排在第2位）。他的功绩是把千百万群众带入计算机的大门。

1.2  当代最优秀的程序设计语言

1.5  面向对象的程序设计语言

3  数据类型、运算符与表达式

顺序结构程序设计举例  60

1.3  C＋＋程序的构成和书写形式

第2章  数据类型与表达式

2.5  算术运算符与算术表达式

2.5.2  算术表达式和运算符的优先级与结合性

2.5.3  表达式中各类数值型数据间的混合运算

2.6  赋值运算符与赋值表达式

2.7  逗号运算符与逗号表达式

第2篇  面向过程的程序设计

3.1  面向过程的程序设计和算法

*3.4.2  在输入流与输出流中使用控制符

3.8  条件运算符和条件表达式

4.4.3  对被调用函数的声明和函数原型

*5.6  C＋＋处理字符串的方法——字符串类与字符串变量

6.3.2  用指针变量作函数参数接收数组地址

6.5.2  用指向函数的指针作函数参数

6.7  指针数组和指向指针的指针

6.8  有关指针的数据类型和指针运算的小结

第7章  自定义数据类型

7.1.2  结构体类型变量的定义方法及其初始化

7.1.6  结构体类型数据作为函数参数

第3篇  基于对象的程序设计

8.1  面向对象程序设计方法概述

8.4.1  通过对象名和成员运算符访问对象中的成员

8.4.2  通过指向对象的指针访问对象中的成员

8.4.3  通过对象的引用变量来访问对象中的成员

8.5.2  类声明和成员函数定义的分离

8.5.3  面向对象程序设计中的几个名词

8.6  类和对象的简单应用举例

第9章  关于类和对象的进一步讨论

9.1.4  用参数初始化表对数据成员初始化

9.3  调用构造函数和析构函数的顺序

10.4  运算符重载函数作为类成员函数和友元函数

10.7  重载流插入运算符和流提取运算符

第4篇  面向对象的程序设计

11.5  派生类的构造函数和析构函数

11.9  继承在软件开发中的重要意义

13.1.2  C＋＋的I／O对C的发展——类型安全和可扩展性

14.1.3  在函数声明中进行异常情况指定

附录B  运算符与结合性

《清华大学计算机系列教材：数据结构（第2版）》第二版在保持原书基本框架和特色的基础上，对主要各章，如第一、二、三、四、六及九章等，作了增删和修改。

　　《清华大学计算机系列教材：数据结构（第2版）》系统地介绍了各种类型的数据结构和查找、排序的各种方法。对每一种数据结构，除了详细阐述其基本概念和具体实现外，并尽可能对每种操作给出类PASCAL的算法，对查找和排序的各种算法，还着重在时间上作出定量或定性的分析比较。最后一章讨论文件的各种组织方法。

　　《清华大学计算机系列教材：数据结构（第2版）》概念清楚，内容丰富，并有配套的《数据结构题集》（第二版），既便于教学，又便于自学。

　　《清华大学计算机系列教材：数据结构（第2版）》可作为计算机类专业和信息类相关专业的教材，也可供从事计算机工程与应用工作的科技工作者参考。

1.3  数据结构的发展简史及它在计算机科学中所处的地位

2.4  一元多项式的表示及相加

3.4.2  链队列——队列的链式存储结构

3.4.3  循环队列——队列的顺序存储结构

第五章  数组和广义表

第六章  树和二叉树

6.1  树的结构定义和基本操作

6.3  遍历二叉树和线索二叉树

7.6.1  从某个源点到其余各顶点的最短路径

第八章  动态存储管理

8.2  可利用空间表及分配方法

10.7  各种内部排序方法的比较讨论

第十一章  外部排序

12.5  直接存取文件（散列文件）

附录一  类PASCAL语言扩充部分的语法图

附录三  过程和函数索引

《面向对象的C++数据结构算法实现与解析》是采用面向对象的c++语言数据结构教材的学习辅导书，主要内容包括采用c++语言的类、模板、虚函数、友元、友类编写的各种主要数据存储结构的算法、基本操作成员函数、调用这些成员函数的主程序和程序运行结果以及各主要数据存储结构的图示。《面向对象的C++数据结构算法实现与解析》还介绍了stl模板的应用。

　　《面向对象的C++数据结构算法实现与解析》结合存储结构和算法，配合大量的图示，对于一些较难理解的算法，还配有文字说明。

　　《面向对象的C++数据结构算法实现与解析》适用于高等学校学生和自学者，同时也是很好的考研参考书。

2.4  队列的应用——排队和排队机的模拟

5.3  图的深度优先遍历和广度优先遍历

6.3  哈希表的插入、删除及查找

推荐帖子 最新更新时间： 02:19