伸展树

计算机术语

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。

存在的意义

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

重构方法

先前，已经存在两种重构方法：

1、单旋：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边。（除非x就是树根）

2、搬移至树根：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边，然后重复这个操作直至x成为树根。

splay tree的重构方法和搬移至树根的方法相似，它也会沿着查找路径做自底向上的旋转，将被查找条目移至树根。但不同的是，它的旋转是成对进行的，顺序取决于查找路径的结构。为了在节点x处对树进行splay操作，我们需要重复下面的步骤，直至x成为树根为止：

1、第一种情况：如果x的父节点p(x)是树根，则旋转连接x和p(x)的边。（这种情况是最后一步）

2、第二种情况：如果p(x)不是树根，而且x和p(x)本身都是左孩子或者都是右孩子，则先旋转连接p(x)和x的祖父节点g(x)的边，然后再旋转连接x和p(x)的边。

3、第三种情况：如果p(x)不是树根，而且x是左孩子，p(x)是右孩子，或者相反，则先旋转连接x和p(x)的边，再旋转连接x和新的p(x)的边。

在节点x处进行splay操作的时间是和查找x所需的时间成比例的。splay操作不单是把x搬移到了树根，而且还把查找路径上的每个节点的深度都大致减掉了一半。

支持的操作

伸展操作

伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转将伸展树S中的元素x调整至树的根部。在调整的过程中，要分以下三种情况分别处理：

情况一：节点x的父节点y是根节点。这时，如果x是y的左孩子，我们进行一次Zig（右旋）操作；如果x是y的右孩子，则我们进行一次Zag（左旋）操作。经过旋转，x成为二叉查找树S的根节点，调整结束。即：如果当前结点父结点即为根结点，那么我们只需要进行一次简单旋转即可完成任务，我们称这种旋转为单旋转。

情况二：节点x的父节点y不是根节点，y的父节点为z，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时，我们进行一次Zig-Zig操作或者Zag-Zag操作。即：设当前结点为X，X的父结点为Y，Y的父结点为Z，如果Y和X同为其父亲的左孩子或右孩子，那么我们先旋转Y，再旋转X。我们称这种旋转为一字形旋转。

情况三：节点x的父节点y不是根节点，y的父节点为z，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次Zig-Zag操作或者Zag-Zig操作。即：这时我们连续旋转两次X。我们称这种旋转为之字形旋转。

如图4所示，执行Splay(1,S)，我们将元素1调整到了伸展树S的根部。再执行Splay(2,S)，如图5所示，我们从直观上可以看出在经过调整后，伸展树比原来“平衡”了许多。而伸展操作的过程并不复杂，只需要根据情况进行旋转就可以了，而三种旋转都是由基本得左旋和右旋组成的，实现较为简单。

查找操作

Find(x,S)：判断元素x是否在伸展树S表示的有序集中。

首先，与在二叉查找树中的查找操作一样，在伸展树中查找元素x。如果x在树中，则再执行Splay(x,S)调整伸展树。

加入操作

Insert(x,S)：将元素x插入伸展树S表示的有序集中。

首先，也与处理普通的二叉查找树一样，将x插入到伸展树S中的相应位置上，再执行Splay(x,S)。

删除操作

Delete(x,S)：将元素x从伸展树S所表示的有序集中删除。

首先，用在二叉查找树中查找元素的方法找到x的位置。如果x没有孩子或只有一个孩子，那么直接将x删去，并通过Splay操作，将x节点的父节点调整

到伸展树的根节点处。否则，则向下查找x的后继y，用y替代x的位置，最后执行Splay(y,S)，将y调整为伸展树的根。

合并操作

join(S1,S2)：将两个伸展树S1与S2合并成为一个伸展树。其中S1的所有元素都小于S2的所有元素。首先，我们找到伸展树S1中最大的一个元素x，再通过Splay(x,S1)将x调整到伸展树S1的根。然后再将S2作为x节点的右子树。这样，就得到了新的伸展树S。

启发式合并

当S1和S2元素大小任意时，将规模小的伸展树上的节点一一插入规模大的伸展树，总时间复杂度O(Nlg^2N)。

划分操作

Split(x,S)：以x为界，将伸展树S分离为两棵伸展树S1和S2，其中S1中所有元素都小于x，S2中的所有元素都大于x。首先执行Find(x,S)，将元素x调整为伸展树的根节点，则x的左子树就是S1，而右子树为S2。

其他操作

除了上面介绍的五种基本操作，伸展树还支持求最大值、求最小值、求前趋、求后继等多种操作，这些基本操作也都是建立在伸展操作的基础上的。

通常来说，每进行一种操作后都会进行一次Splay操作，这样可以保证每次操作的平摊时间复杂度是O(logn)。

优势

由于Splay Tree仅仅是不断调整，并没有引入额外的标记，因而树结构与标准红黑树没有任何不同，从空间角度来看，它比Treap、SBT、AVL要高效得多。因为结构不变，因此只要是通过左旋和右旋进行的操作对Splay Tree性质都没有丝毫影响，因而它也提供了BST中最丰富的功能，包括快速的拆分和合并，并且实现极为便捷。这一点是其它结构较难实现的。其时间效率也相当稳定，和Treap基本相当，常数较高。

缺点

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

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省