数据结构与算法分析 —— C 语言描述：伸展树

伸展树（splay tree）保证从空树开始任意连续 M 次对树的操作最多花费 时间。虽然这种保证并不排除任意一次操作花费 时间的可能，而且这样的界也不如每次操作最坏情形的界 那么短，但是实际效果是一样的 —— 不存在坏的输入序列。一般来说，当 M 次操作的序列总的最坏情形运行时间为 时，我们就说它的摊还（amortized）运行时间为 。因此，一颗伸展树每次操作的摊还代价是 。经过一系列的操作之后，有的可能花费时间多一些，有的可能更少一些。

伸展树是基于这样的事实：对于二叉查找树来说，每次操作最坏情形时间 并不坏，只要它相对不常发生就行。任何一次访问即使花费 ，仍然可能飞快。二叉查找树的问题在于，虽然一系列访问整体都有可能发生不良操作，但是很很罕见。此时，累积的运行时间很重要。具有最坏情形运行时间 但保证对任意 M 次连续操作最多花费 运行时间的查找树数据结构确实令人满意，因为不存在坏的操作序列。

伸展树的基本想法是，当一个节点被访问后，它就要经过一系列 AVL 树的旋转后放到根上。注意，如果一个节点很深，那么在其路径上就存在许多的节点也相对较深，通过重新构造可以使对所有这些节点的进一步访问所花费的时间变少。因此，如果节点过深，那么我们还要求重新构造应具有平衡这棵树（到某种程度）的作用。除在理论上给出好的时间界外，这种方法还可能有实际的效用，因为在许多应用中当一个节点被访问时，它就很可能不久再被访问到。研究表明，这种情况的发生比人们预料的要频繁得多。另外，伸展树还不要求保留高度或平衡信息，因此它在某种程度上节省空间并简化代码（特别是当实现例程经过审慎考虑而被写出的时候）。

一个简单的想法

实施上面描述的重新构造的一种方法是执行单旋转，从下向上进行。这意味着我们将在访问路径上的每一个节点和它们的父节点间实施旋转。

展开

展开（splaying）的思路类似于前面介绍的旋转的想法，不过在旋转如何实施上我们稍微有些选择的余地。我们仍然从底部向上沿着访问路径旋转。令 X 是在访问路径上的一个（非根）节点，我们将在这个路径上实施旋转操作。如果 X 的父节点是树根，那么我们只要旋转 X 和树根。这就是沿着访问路径上的最后的旋转。否则，X 就有父亲（P）和祖父（G），存在两种情形以及对称的情形要考虑。第一种情形是之字形（zig-zag）情形。这里，X 是右儿子，P是左儿子（反之亦然）。如果是这种情形，那么我们就执行一次像 AVL 那样的双旋转。否则，出现另一种一字型（zig-zig）情形：X 和 P 或者都是左儿子，或者都是右儿子。

虽然从一些小例子很难看出来，但是展开操作不仅将访问的节点移动到根处，而且还有把访问路径上的大部分节点的深度大致减少一半的效果（某些浅的节点最多向下推后两个层次）。

当访问路径太长而导致超出正常查找时间的时候，这些旋转将对未来的操作有益。当访问耗时很少的时候，这些旋转则不那么有益甚至有害。极端的情形是经过若干插入而形成的初始树。所有的插入都是花费常数时间的操作，会导致坏的初始树。此时，我们会得到一棵很差的树，但是运行却比预计的快，从而总的较少运行时间补偿了损失。这样，少数真正麻烦的访问却留给我们一棵几乎平衡的树，其代价使我们必须返还某些已经省下的时间。可以证明，每个操作绝不会落后 这个时间 —— 我们总是遵守这个时间，即使偶尔有些不良操作。

我们可以通过访问要删除的节点实行删除操作。这种操作将节点上推到根处。如果删除该节点，则得到两棵子树 和 （左子树和右子树）。如果我们找到 中最大的元素（这很容易），那么就将这个元素旋转到 的根下，而此时 将有一个没有右儿子的根。可以使 成为右儿子从而结束删除。

对伸展树的分析很困难，因为树的结构经常变化。另一方面，伸展树的编程要比 AVL 树简单得多，这是因为要考虑的情形少并且没有平衡信息需要存储。实际经验指出，在实践中它可以转化成更快的程序代码，不过这种情况还远非完美。最后，需要指出，伸展树有几种变化，它们在实践中甚至运行得更好。