查找——图文翔解伸展树SplayTree

伸展树

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它由Daniel Sleator和Robert Tarjan创造，后者对其进行了改进。

假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splaytree应运而生。splaytree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

（以前我们在《数据结构》这门课中学过最优二叉树，那是一种静态树，提前算好各个查询的概率，把高概率的查询放在靠近树根的位置，并不实用。）

伸展树能在O(logn)内完成插入、查找和删除作。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。

下面仔细图解一下伸展树的基本操作：

当查找到一个结点后，需要进行“伸展”操作，把这个结点移动到树根。至于伸展操作有两种方式：自底向上和自顶向下。

自底向上

所谓的自底向上就是像AVL树那样的“左旋”、“右旋”，多次操作之后把此结点旋转到树根，但这种方式，需要保存查找路径上的各个结点的指针以供旋转之用。

（既然下面要讲更方便实用的自顶向下法，这里就不仔细图解自底向上的旋转方式了，有兴趣的朋友可google之）

自顶向下

当我们沿着树向下搜索某个节点X的时候，我们将搜索路径上的节点及其子树移走。我们构建两棵临时的树──左树和右树。

没有被移走的节点构成的树称作中树。在伸展操作的过程中：

1、当前节点X是中树的根。

2、左树L保存小于X的节点。

3、右树R保存大于X的节点。

开始时候，X是树T的根，左右树L和R都是空的。

（关键字：边访问，边肢解）

（我们以一个查找2结点的实例，来图解SplayTree的伸展过程，这个史上最清晰的图解，你一定能看的明白^_^）

好了，看完这个例子，你一定对SplayTree的伸展操作有了清晰的理解了。至于代码实现，网上随便一搜一大坨，在这里就不粘贴浪费篇幅了，有兴趣的朋友请Google之。

删除操作

伸展树的删除操作很简单，就是先访问目标结点，把结点移动到树根，然后再删除树根结点，把左右子树连接在一起即可。

伸展树的区间操作

在实际应用中，伸展树的中序遍历即为我们维护的数列，这就引出一个问题，怎么在伸展树中表示某个区间？

比如我们要提取区间[a,b]，那么我们将a前面一个数对应的结点转到树根，将b 后面一个结点对应的结点转到树根的右边，那么根右边的左子树就对应了区间[a,b]。原因很简单，将a 前面一个数对应的结点转到树根后， a 及a 后面的数就在根的右子树上，然后又将b后面一个结点对应的结点转到树根的右边，那么[a,b]这个区间就是下图中B所示的子树。

利用区间操作我们可以实现线段树的一些功能，比如回答对区间的询问（最大值，最小值等）。

与线段树相比，伸展树功能更强大，它能解决以下两个线段树不能解决的问题：

（1） 在a后面插入一些数。方法是：首先利用要插入的数构造一棵伸展树，接着，将a 转到根，并将a 后面一个数对应的结点转到根结点的右边，最后将这棵新的子树挂到根右子结点的左子结点上。

（2） 删除区间[a,b]内的数。首先提取[a,b]区间，直接删除即可。

优点

1、时间复杂度低，伸展树的各种基本操作的平摊复杂度都是O(log n)的。在树状数据结构中，无疑是非常优秀的。

2、空间要求不高。与红黑树需要记录每个节点的颜色、AVL树需要记录平衡因子不同，伸展树不需要记录任何信息以保持树的平衡。

3、算法简单，编程容易。伸展树的基本操作都是以Splay操作为基础的，而Splay操作中只需根据当前节点的位置进行旋转操作即可。

虽然伸展树算法与AVL树在时间复杂度上相差不多，甚至有时候会比AVL树慢一些，但伸展树的编程复杂度大大低于AVL树。

缺点

1、它们需要更多的局部调整，尤其是在查找期间。（很多其它数据结构仅需在更新期间进行调整，查找期间则不用）

2、一系列查找操作中的某一个可能会耗时较长，这在实时应用程序中可能是个不足之处。

3、它有可能会变成一条链。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级的——O(logn)

举个栗子

要每次读入一个数，并且在前面输入的数中找到一个与该数相差最小的一个。

我们很容易想到O(n2)的算法：每次读入一个数，再将前面输入的数一次查找一遍，求出与当前数的最小差值，记入总结果T。若n很大，这样的算法效率太低。而如果使用线段树记录已经读入的数，就需要记下一个2M的大数组，空间复杂度略高。而红黑树与平衡二叉树虽然在时间效率、空间复杂度上都比较优秀，但过高的编程复杂度却让人望而却步。于是我们想到了伸展树算法。

进一步分析本题，解题中，涉及到对于有序集的三种操作：插入、求前趋、求后继。而对于这三种操作，伸展树的时间复杂度都非常优秀，于是我们设计如下算法：

开始时，树S为空，总和T为零。每次读入一个数p，执行Insert(p,S)，将p插入伸展树S。这时，p也被调整到伸展树的根节点。这时，求出p点左子树中的最右点和右子树中的最左点，这两个点分别是有序集中p的前趋和后继。然后求得最小差值，加入最后结果T。

伸展树的基本操作的平摊复杂度都是O(log n)的，所以整个算法的时间复杂度是O(nlog n)。