一 点睛

伸展树，也叫作分裂树，是一种二叉搜索树，可以在 O (logn ) 内完成插入、查找和删除操作。在任意数据结构的生命周期内执行不同操作的概率往往极不均衡，而且各操作之间有极强的相关性，在整体上多呈现极强的规律性，其中最为典型的就是数据局部性（data locality）。数据局部性包括时间局部性和空间局部性。伸展树正是基于数据的时间局部性和空间局部性原理产生的。

二 时间局部性和空间局部性的原理

时间局部性和空间局部性的原理如下。

• 刚刚被访问的元素，极有可能在不久后再次被访问。

• 刚刚被访问的元素，它的相邻节点也很有可能被访问。

树的搜索时间复杂度与树的高度相关。二叉搜索树的高度在最坏情况下为 n ，每次搜索的时间复杂度都退化为线性 O (n )。平衡二叉树（AVL树）通过动态调整平衡，使树的高度保持在O (logn )，因此单次搜索的时间复杂度为O (logn )。但是AVL树为了严格保持平衡，在调整时会做过多旋转，影响了插入和删除的性能。

伸展树的实现更为简捷，它无须时刻保持全树平衡，任意节点的左右子树高差无限制。伸展树的单次搜索也可能需要 n 次操作，但可以在任意足够长的真实操作序列中保持均摊意义上的高效率 O (logn)。伸展树可以保证 m 次连续搜索操作的复杂度为 O (m logn)，而不是O (mn)。伸展树的优势在于不需要记录平衡因子、树高、子树大小等额外信息，所以适用范围更广，对 m 次连续搜索操作具有较高的效率。

考虑到局部性原理，伸展树会在每次操作后都将刚被访问的节点旋转至树根，加速后续的操作。当然，旋转前后的搜索树必须相互等价。这样，查询频率高的节点应当经常处于靠近树根的位置。旋转的巧妙之处：在不打乱数列中数据大小关系（中序遍历有序性）的情况下，所有基本操作的均摊复杂度仍为O (logn)。

三 右旋和左旋

伸展操作 Splay(x , goal) 是在保持伸展树有序性的前提下，通过一系列旋转将伸展树中的元素 x 调整到 goal 的子节点，若 goal=0，则将元素 x 旋转到树的根部。伸展操作包括右旋和左旋两种基本操作。

1 右旋

节点 x 右旋时，携带自己的左子节点向右旋转到 y 位置，y 旋转到 x 的右子树位置，x 的右子树被抛弃，此时 y 右旋后左子树正好空闲，将 x 的右子树放到 y 的左子树位置，旋转后将 x 挂接到 y 的父节点，若原来 y 是其父节点的右子节点，则旋转后 x 也是其父节点的右子节点，否则是其父节点的左子节点。旋转时修改

了3对父子关系，即 y 和 xr 、y 的父节点 tr[y ].fa 和 x 、x 和 y ，如下图中的粗线所示。

2 左旋

节点 x 左旋时会携带自己的右子节点，向左旋转到 y 的位置，y 旋转到 x 的左子树位置，x 的左子树被抛弃，此时 y 左旋后其右子树正好空闲，将 x 的左子树放到 y 的右子树位置，旋转后将 x 挂接到 y 的父节点 tr[y ].fa ，若原来 y 是其父节点的右子节点，则旋转后 x 也是其父节点的右子节点，否则是其父节点的左

子节点。

四 伸展

伸展操作并不复杂，根据情况右旋或左旋就可以了。伸展操作分为逐层伸展和双层伸展。

1 逐层伸展

将 x 旋转到目标 goal之下，若 x 的父节点不是目标，则判断：若 x 是其父节点的左子节点，则执行 x 右旋；否则执行 x 左旋，直到 x 的父节点等于目标为止。若目标为 0，则 x 为树根。

例如，在下面的伸展树中将 1 旋转到树根，逐层伸展的旋转过程如下图所示。

算法分析： 采用逐层伸展的方法，每次访问的时间复杂度在最坏情况下都为O (n)，如何避免最坏情况的发生呢？一个简单有效的方法是双层伸展，即每次都向上追溯两层，判断旋转类型并进行相应的旋转。

2 双层伸展

双层伸展每次都向上追溯两层，旋转类型分为 3 种情况。

情况1：Zig/Zag

若节点 x 的父节点 y 是根节点，则只需进行一次右旋或左旋操作即可。若 x 是其父节点 y 的左子节点，则执行 x 右旋，否则执行 x 左旋。

情况2：Zig-Zig / Zag-Zag

若节点 x 的父节点 y 不是根节点，y 的父节点为 z ，且 x、y 同时是各自父节点的左子节点或右子节点，则需要进行两次右旋或两次左旋操作。

情况3：Zig-Zag / Zag-Zig

若节点 x 的父节点 y 不是根节点，y 的父节点是 z ，且在 x、y 中一个是其父节点的左子节点，一个是其父节点的右子节点，则需要进行两次旋转：右旋-左旋或两次左旋-右旋操作。

3 分析

情况 1 和情况 3 都进行了 x 的右旋或左旋，和逐层伸展的方法完全一致，情况 2 则有所不同：逐层伸展时进行了两次 x 旋转，双层伸展时先进行 y 旋转再进行 x 旋转。

例如，在下面的伸展树中将 1 旋转到树根，双层伸展的旋转过程如下图所示。

旋转之后，双层伸展比逐层伸展得到的树高度更小，基本操作的时间复杂度和树高成正比，因此双层伸展比逐层伸展效率更高。

算法分析： 双层伸展可以使树的高度接近于减半的速度压缩。Tarjan 等人已经证明，双层伸展单次操作的均摊时间为 O(logn)，比逐层伸展的效率高了很多。逐层伸展简单、易懂，在数据量不大的情况下可以通过，若数据量大或特殊数据卡点，则会超时。

五 查找

与二叉搜索树的查找一样，在伸展树中查找 val，若查找成功，则将 val 旋转到根。

六 插入

与二叉搜索树的插入一样，将 val 插入伸展树的相应位置，再执行 Splay(x , 0)。初始时，x=root，若 tr[x ].val<val，则到 x 的右子树中查找，否则到 x 的左子树中查找；若 x 的子树不存在，则停止，生成新节点挂到 x 的子树上，然后将新插入的节点旋转到树根。

七 分裂

以 val 为界，将伸展树分裂为两棵伸展树 t1 和 t2 ，t1 中的所有元素都小于 val ， t2 中的所有元素都大于 val 。 首先执行 Find(val)，将元素 val 调整为伸展树的根节点，则 val 的左子树就是 t1 ，右子树为 t2 。删除树根，分裂为 t1 和 t2 两棵伸展树。

八 合并

将两个伸展树 t1 和 t2 合并为一个伸展树，t1 的所有元素都小于 t2 的所有元素。首先，找到伸展树 t1 中的最大元素 x ，查找最大值时会通过伸展操作将 x 调整到伸展树的根；然后，将 t2 作为树根 x 的右子树。这样就得到了新的伸展树 root。

九 删除

将元素 val 从伸展树中删除。首先在伸展树中查找 val，然后以 val 为界，将伸展树分裂为两棵伸展树 t1 和 t2 ，再将两个伸展树合并。

十 区间操作

若伸展树中节点的值为数列中每个元素的位置，则可以利用伸展树实现线段树的所有功能，还可以实现线段树无法实现的功能，例如删除区间和插入区间。

1 删除区间

删除 [l , r ] 区间的所有元素。首先找到 l-1，将其旋转到树根；然后找到 r+1，将其旋转到树根的右子节点，此时 r +1 的左子树为 [l, r ]区间，将 r+1 的左子树置空。

2 插入区间

在 pos 后插入一些元素 {a1 , a2 , …, ak }。首先将这些元素建成一棵伸展树 t1，然后找到 pos，将其旋转到树根；最后找到 pos+1，将其旋转到树根的右子节点，将 t1 挂接到 pos+1 的左子树上。