伸展树（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)。

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

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

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

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

物体的移动算法似乎显得很简单，然而寻路规划问题却十分复杂。考虑下面这个例子：

这个单位的初始位置在地图的下方，想要到达地图的顶部。如果物体所能侦测到的地方（粉色部分所示）并没有障碍，那么物体就会直接向上走到它的目标位置。但在距离顶端较近的位置时，物体侦测到了障碍，因而改变了方向。该物体将不得不行进一个“U”形的路径绕过障碍物（如红色路径所示）。通过对比可知，寻路系统能够通过搜索一个更大的范围（如蓝色区域所示），并寻找一个更短的路线（如蓝色路径所示），使物体避免绕这条由凹陷障碍物造成的远路。

当然，可以通过改进物体的移动算法解决上图所示的陷阱。即要么避免在地图上创建有凹陷的物体，要么标记整个凹陷物体的整个凸包为危险区域（即除非目标在该区域内，否则避免进入该区域），如下图所示：

而寻路系统则会让路径的决定提前，而不是像上图一样，物体直到移动到最后一刻才发现问题所在。对于“改进物体移动算法”和“使用寻路系统规划路径”两种方式有以下的折中：规划路径一般来说更慢，但效果更好；改进移动算法则会快一些，但有时候会卡住。如果游戏地图经常改变，那么路径规划的方式可能就意义不大了。我建议两者都使用：在更大的尺度、缓慢变换的地图和更长的路径上进行寻路规划，而对于局部区域、快速更改的地图和短的路径则使用改进的物体移动算法。

普通教科书上的寻路算法往往只应用在数学意义上的“图”上，即由顶点集合和边集合互相连接组成的结构。因此我们需要将一个栅格化的游戏地图转化为一个“图”：地图上的每一格可以作为一个顶点，而相邻的格子则各有一条边，如图所示：

我们只考虑。如果你没有关于图的背景知识，可以参见。之后我会讨论如何在游戏世界中。

大部分在AI和算法领域的寻路算法都是针对作为数学结构的“图”本身，而并非针对这种网格化游戏地图。我们希望寻找一种能利用游戏地图自身特征的方法。其实有些在二维网格图中我们认为是常识的事情，一些在普通图上使用的寻路算法本身可能并没有考虑到，例如如果两个物体距离较远，那么可能从一个物体到另一个物体的移动的时间和路径会较长（当然，假设空间中没有虫洞存在）。对于方向来说，如果方向是朝东，那么最优路径的路径也应当是大体往东走，而不是向西去。在网格中还可以从对称中获取信息，即先向北再向西，大部分情况下和先向西再向北等价。这些额外的信息可以让寻路算法更加快速。

Dijkstra算法简单说来，就是从起始点访问其他临近节点，并将该节点加入待检查节点集合中，使用松弛算法更新待检查节点的路径长度值。只要图不存在负权值的边，Dijkstra算法能够确保找到最短路径。在下面的图中，粉色的方格为起始点，蓝紫色的方格为目标点，青绿色的方格则为Dijkstra算法所扫描的节点。淡色的节点是距离起始点较远的节点。

贪心最好优先搜索算法大体与之类似，不同的是该算法对目标点的距离有一个估计值（启发值）。该算法并不在待检查节点集合中选取距离起始点近的节点进行下一步的计算，而是选择距离目标点近的节点。贪心最好优先搜索算法并不能保证寻找到最优路径，然而却能大大提高寻路速度，因为它使用了启发式方法引导了路径的走向。举例来说，如果目标节点在起始点的南方，那么贪心最好优先搜索算法会将注意力集中在向南的路径上。下图中的黄色节点指示了具有高启发值的节点（即到目标节点可能花费较大的节点），而黑色则是低启发值的节点（即到目标节点的花费较小的节点）。下图说明了相比于Dijkstra算法，贪心最好优先算法能够更加快速地寻路。

然而上述的例子仅仅是最简单的：即地图上没有障碍物。考虑前文中我们曾经提到的凹陷障碍物，Dijkstra算法仍然能够寻找到最短路径：

贪心最好优先算法虽然做了较少的计算，但却并不能找到一条较好的路径。

问题在于最好优先搜索算法的贪心属性。由于算法仅仅考虑从目前节点到最终节点的花费，而忽略之前路径已经进行的耗费，因此即使在路径可能错误的情况下仍然要移动物体。

1968年提出的A*算法结合了贪心最好优先搜索算法和Dijsktra算法的优点。A*算法不仅拥有发式算法的快速，同时，A*算法建立在启发式之上，能够保证在启发值无法保证最优的情况下，生成确定的最短路径。

下面我们主要讨论A*算法。A*是目前最流行的寻路算法，因为它十分灵活，能够被应用于各种需要寻路的场景中。

与Dijkstra算法相似的是，A*算法也能保证找到最短路径。同时A*算法也像贪心最好优先搜索算法一样，使用一种启发值对算法进行引导。在刚才的简单寻路问题中，它能够像贪心最好优先搜索算法一样快：

而在后面的具有凹陷障碍物的地图中，A*算法也能够找到与Dijkstra算法所找到的相同的最短路径。

该算法的秘诀在于，它结合了Dijkstra算法使用的节点信息（倾向于距离起点较近的节点），以及贪心最好优先搜索算法的信息（倾向于距离目标较近的节点）。之后在讨论A*算法时，我们使用g(n)表示从起点到任意节点n的路径花费，h(n)表示从节点n到目标节点路径花费的估计值（启发值）。在上面的图中，黄色体现了节点距离目标较远，而青色体现了节点距离起点较远。A*算法在物体移动的同时平衡这两者的值。定义f(n)=g(n)+h(n)，A*算法将每次检测具有最小f(n)值的节点。

之后的系列文章将主要探讨、、等，并讨论与游戏中寻路问题相关的一系列话题。

启发式函数h(n)告诉A*从任何结点n到目标结点的最小代价评估值。因此选择一个好的启发式函数很重要。

启发式函数在A* 中的作用

启发式函数可以用来控制A*的行为。

• 一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A* 算法演变成Dijkstra算法，就能保证找到最短路径。
• 如果h(n)总是比从n移动到目标的代价小（或相等），那么A* 保证能找到一条最短路径。h(n)越小，A* 需要扩展的点越多，运行速度越慢。
• 如果h(n)正好等于从n移动到目标的代价，那么A* 将只遵循最佳路径而不会扩展到其他任何结点，能够运行地很快。尽管这不可能在所有情况下发生，但你仍可以在某些特殊情况下让h(n)正好等于实际代价值。只要所给的信息完善，A* 将运行得很完美。
• 如果h(n)比从n移动到目标的代价高，则A* 不能保证找到一条最短路径，但它可以运行得更快。
• 另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，同时A* 算法演变成贪婪最佳优先搜索算法（Greedy Best-First-Search）。

所以h(n)的选择成了一个有趣的情况，它取决于我们想要A* 算法中获得什么结果。h(n)合适的时候，我们会非常快速地得到最短路径。如果h(n)估计的代价太低，我们仍会得到最短路径，但运行速度会减慢。如果估计的代价太高，我们就放弃最短路径，但A* 将运行得更快。

在游戏开发中，A* 的这个特性非常有用。例如，你可能会发现在某些情况下，你宁愿有一个“好”的路径而不是一个“完美”的路径。为了平衡g(n)和h(n)之间的关系，你可以修改其中的任何一个。

注释： 从技术上来看，如果启发式函数值低估了实际代价，A* 算法应该被称为简单的A算法(simply A)。不过，我将继续称之为A* 算法，因为它们的实现是相同的，而且游戏编程社区对A算法和A* 算法并不区分对待。

A* 基于启发式函数和代价函数来改变其行为的能力在游戏中非常有用。速度和准确性之间的折衷可以提高游戏速度。对于大多数游戏而言，你并不需要两个点之间的最佳路径。你只需要知道就足够了。你所需要的路径往往取决于游戏中接下来要发生什么，或是运行游戏的计算机有多快。

假设你的游戏中有两种地形，平原和山地，它们的移动代价分别是1和3，A* 算法沿着平原搜索的路径长度是沿着山区的三倍。这是因为可能有一条绕着山地的平原路径。你可以把两个地图单位之间的启发式距离设为/71044/ 

谭浩强教授，我国著名计算机教育专家。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