这会儿想说点关于数据结构的硬核内容。Splay 树伸展树你可能听说过也可能在平衡树的题解里见过它的大名但始终没动手写过。这玩意在 C 竞赛、数据结构实验、甚至某些工程场景里都挺能打因为它的思路跟 AVL 树、红黑树完全不是一个路子——不靠高度约束靠“用一次移动一个节点”的伸展操作顺带完成整棵树的自我调整。这篇我直接按平时的写法来先把 Splay 的原理拆开讲透然后给出可以抄走的完整 C 实现最后把踩过的坑、调 bug 的招数一并交代清楚。适合已经掌握二叉搜索树、想进阶平衡树的读者也适合做数据结构实验报告、期末复习时临时抱佛脚的朋友。1. 为什么需要 Splay 树平衡二叉搜索树的差异化选项1.1 从 BST 退化说起二叉搜索树BST是很多高级数据结构的底子插入、删除、查找都依赖树高。理想情况下一棵平衡的 BST 树高是 O(log n)操作自然也是 O(log n)。但普通 BST 有一个致命毛病——它不控制形状。如果你按升序插入 1、2、3、4、5树就会一路往右偏最终变成一条链查找最后一个节点要 O(n) 步跟数组顺序扫没区别。平衡树家族的思路基本都是“防止树偏得太厉害”AVL 树靠严格的高度差限制红黑树靠颜色约束路径上的黑色节点数量。这两种方案都会在插入、删除后做旋转把树“掰”回平衡状态。问题是旋转本身有代价而且为了维护“绝对平衡”或“近似平衡”每个节点都得额外存高度或颜色信息。Splay 树在这个问题上的切入点完全不同。它不追求树在任何时刻都接近完美平衡——它只保证一件事最近访问过的节点下一次访问会很快。这个思路听起来有点跳跃但背后有局部性原理支撑在实际使用中如果一个数据刚被查过往往很快还会再被查。Splay 树利用这个规律把每次访问的节点通过旋转一路“伸展”到树根于是整个访问路径上的节点都被翻新了一遍。1.2 Splay 树的核心思路与适用场景Splay 树解决问题的核心手段就是“伸展操作”splay。给定一个节点 x通过一系列旋转把 x 变成整棵树的根。这个过程中x 的祖先们会重新分布到 x 的子树中树的形态发生局部重构。每次查询、插入、删除后都执行一次伸展树的形态就不会长期停留在一条链上。这种做法的好处很务实不需要额外维护平衡因子或颜色位节点里只需要左右孩子、父节点、值和子树大小等信息实现起来比红黑树简单不止一个量级而且均摊复杂度是 O(log n)——注意是均摊不是每次操作都严格 O(log n)。用势能分析可以证明任意连续 m 次操作的总体复杂度是 O(m log n)这就足够应付大量实际场景。我个人的体感是Splay 适合两类人一是需要写平衡树但不想熬红黑树的竞赛党、实验党二是要做区间翻转、区间移动这类序列操作的场景。这类操作涉及对某个区间整体打标记、平移、合并用 AVL 或红黑树实现非常别扭而 Splay 因为可以把任意区间“抽”到一棵子树里处理起来几乎是量身定做。后面第 5 节我会专门展开这个玩法。2. 旋转与伸展先把核心操作彻底讲透2.1 单旋zig 与 zag旋转是 Splay 树的基本动作理解它之前需要先接受一个事实二叉搜索树的中序遍历顺序是“天条”旋转只能在保持中序不变的前提下调整局部父子关系。中序不变意味着左子树全比根小、右子树全比根大的相对顺序不能乱。旋转分成两种镜像动作。右旋zig针对的是“当前节点是父节点的左孩子”这种情况把父节点 y 拉下来变成 x 的右孩子同时把 x 原来的右孩子 B 过继给 y 当左孩子。左旋zag则完全对称针对“当前节点是父节点的右孩子”的情况。你可以把旋转理解成在树上“提”一个节点你想让哪个节点往上走就把父节点往反方向压下去。关键细节是那个“过继”的孩子——它原来的位置会被父节点占据所以必须换到父节点的另一侧挂上。这个孩子可能是空节点操作时要注意判空。2.2 双旋zig-zig 与 zig-zag单旋只能让节点上移一层而 splay 操作需要把一个节点从深度很深的位置一路提到根。如果只是反复单旋最坏情况下会出问题——这恰恰是早期“自调整树”实现中最容易犯的错误。正确的做法是双旋也叫双层旋转分两种形态zig-zig一字型当前节点 x 和它的父节点 y、祖父节点 z 处在同一条直线上。比如 x 是 y 的左孩子y 也是 z 的左孩子。这时候先旋 y再旋 x。zig-zag之字型x 是 y 的左孩子但 y 是 z 的右孩子方向相反。这时候先旋 x再旋 x也就是说旋两次 x但第一次旋完 x 变成了 y 的位置第二次从 z 下面继续旋。为什么要区分这两种形态关键在 zig-zig。如果 zig-zig 也旋两次 x就会造成一条“长链”在伸展过程中虽然目标节点上移了但树的整体高度并没有得到很好的改善反而可能让后续操作退化。先旋父节点再旋当前节点能把链中间的节点也带上来一层调整效果明显更好。这个细节是 Splay 树均摊复杂度分析成立的基础。2.3 为什么是“双层旋”而不是“一直单旋”用一个生活中的类比来理解。想象你在一家排队很长的食堂窗口打饭你排在队伍尾部想快点到窗口前。如果每次只往前挪一位单旋队伍中间的人没有明显变化你挪的次数等于深度——深度大时依然很慢。但如果每次你先让前面的人往旁边闪开相当于把父节点往上带一层你再顺势跨两步整条队伍的重心会快速变化。严谨一点说只用单旋的“naive splay”在最坏情况下会退化每次操作都可能 O(n)均摊分析不成立。双层旋转保证了访问路径上节点深度整体减半的效果这是势能法证明的核心依据。实际写代码时splay 函数的循环体就靠判断“当前节点、父节点、祖父节点三者的方向关系”来决定先转谁这部分的写法我会在第 3 节直接给出。3. C 实现结构体、内存池与核心函数代码3.1 节点结构定义与内存分配我把节点定义放在结构体里用静态数组预分配内存。竞赛里常见的数据范围是 n 10^5开的数组大小直接设为MAXN 100010省去反复 new/delete 的碎时间和指针边界判断。const int MAXN 100010; struct Node { int ch[2]; // ch[0] 左孩子, ch[1] 右孩子 int fa; // 父节点编号, 根节点的 fa 为 0 int val; // 节点存储的值 int cnt; // 该值出现的次数支持重复值 int sz; // 子树大小含自身, 用于排名类查询 int lazy; // 懒标记, 区间翻转时用, 普通平衡树可忽略 } tr[MAXN]; int root, tot; // 根节点编号, 已用节点总数这里有几个设计细节要解释。cnt是为了让平衡树支持重复值——同一个值插入两次不新建节点只把次数加一这样查排名、找前驱后继都方便。sz是子树节点总数在查“第 k 大”的时候要依赖它做剪枝。lazy是懒标记纯做平衡树时用不上但做文艺平衡树区间翻转时必须保留我先写在这里第 5 节会用到。内存分配采用“内存池”思路节点编号从 1 开始递增tot取出一个新节点。树根存储在root变量里所有操作最终都以root为入口。3.2 rotate 旋转函数的完整实现旋转是 Splay 的原子操作。我习惯把左旋和右旋合并成一个函数用k来区分方向。k 0 表示当前节点是父节点的左孩子执行右旋k 1 表示当前节点是父节点的右孩子执行左旋。void pushup(int x) { tr[x].sz tr[tr[x].ch[0]].sz tr[tr[x].ch[1]].sz tr[x].cnt; } void rotate(int x) { int y tr[x].fa; // x 的父节点 int z tr[y].fa; // x 的祖父节点 int k (tr[y].ch[1] x); // k 0 表示 x 是左孩子, k 1 表示右孩子 // 第一步把 x 的“另一侧孩子”接给 y // 右旋时 x 的右孩子过继给 y 当左孩子; 左旋时 x 的左孩子过继给 y 当右孩子 if (tr[x].ch[k ^ 1]) tr[tr[x].ch[k ^ 1]].fa y; tr[y].ch[k] tr[x].ch[k ^ 1]; // 第二步把 y 变成 x 的孩子 tr[x].ch[k ^ 1] y; tr[y].fa x; // 第三步把 x 接到原来的祖父 z 上 tr[x].fa z; if (z) tr[z].ch[tr[z].ch[1] y] x; // 旋转后 y 变成了 x 的孩子, 先更新 y 的子树大小, 再更新 x pushup(y); pushup(x); }这段代码我第一次写的时候也晕了很久后来总结出记忆口诀三步接替先孩子后父亲再祖父。第一步处理的是“过继”的孙辈节点第二步翻转父子关系第三步处理祖父节点的指针。顺序不能乱否则会出现某个节点同时被两个节点指向或者某个节点的 fa 指向错误位置。特别注意if (z)的判断——如果 z 是 0说明 y 原本是根x 旋转后直接成为新根此时root应该更新为 x。我习惯在 splay 函数里统一更新 root所以 rotate 里只处理父指针不直接动 root。3.3 splay 伸展函数的完整实现splay 函数的目标是把节点 x 通过双旋提升为某个节点 goal 的直接孩子当 goal 为 0 时x 直接成为整棵树的根。这里有个常见写法是利用栈先做懒标记下传再做旋转我把两部分都放在这个函数里保证区间操作时不会因为残留懒标记而出错。int stk[MAXN]; // 用于存放从根到目标节点的路径 void splay(int x, int goal) { int y x, top 0; stk[top] y; while (tr[y].fa ! goal) { y tr[y].fa; stk[top] y; } // 从根到 x 依次下传懒标记 while (top) pushdown(stk[top--]); while (tr[x].fa ! goal) { int y tr[x].fa; int z tr[y].fa; if (z ! goal) { // 判断是 zig-zig 还是 zig-zag if ((tr[y].ch[0] x) ^ (tr[z].ch[0] y)) { rotate(x); // zig-zag: 方向不同, 先旋 x } else { rotate(y); // zig-zig: 方向相同, 先旋 y } } rotate(x); // 最后必然还要旋一次 x } if (goal 0) root x; // goal 为 0 表示要伸展到根 }判断方向的代码(tr[y].ch[0] x) ^ (tr[z].ch[0] y)挺巧妙的。如果 x 是 y 的左孩子ch[0] x 为真y 是 z 的左孩子ch[0] y 为真异或结果为假说明是同向做 zig-zig先旋 y。如果两边方向不同异或为真做 zig-zag先旋 x。为什么还要先处理懒标记因为如果树上有区间翻转的懒标记节点真实的孩子位置可能还没换过来直接旋转会转错对象。先把从根到 x 路径上的所有懒标记按从上到下的顺序下传掉再做旋转才能保证孩子关系是“真实”的。4. 基础操作落地插入、删除、前驱后继、第 K 大4.1 插入节点查找失败后建新节点插入操作遵循 BST 的常规查找逻辑但多了一个要点插入完成后必须 splay。这不是为了炫技而是通过伸展把新节点提升到根让后续操作的复杂度能够正确均摊。void insert(int val) { int u root, p 0; while (u tr[u].val ! val) { p u; u tr[u].ch[val tr[u].val]; } if (u) { // 值已经存在, 次数加一即可 tr[u].cnt; splay(u, 0); return; } // 建立新节点 u tot; tr[u].val val; tr[u].fa p; tr[u].cnt tr[u].sz 1; tr[u].ch[0] tr[u].ch[1] 0; if (p) tr[p].ch[val tr[p].val] u; splay(u, 0); }我这里把cnt后再 splay或者先 splay 再cnt都试过实测效果一样。但要注意如果值已存在sz也要更新。我习惯先cnt然后 splay——splay 过程中的 pushup 会沿着路径把 sz 更新上来比较省心。插入时还有个小细节新节点的左右孩子要清空。因为tot分配的内存池可能是旧的残留值不清空会残留上一轮使用时的孩子指针后续遍历时会访问野地址。这个坑我踩过不止一次静态数组内存池最容易出这个问题。4.2 删除节点利用前驱后继巧妙拼接删除单节点的经典套路是“找前驱和后继抽中间”。这个做法依赖哨兵节点在树里预先插入-INF和INF两个值保证任何操作都能找到前驱后继不会因为边界情况返回空节点。void erase(int val) { // 找 val 的前驱 pre严格小于 val 的最大值 int pre get_pre(val); // 找 val 的后继 nxt严格大于 val 的最小值 int nxt get_nxt(val); splay(pre, 0); // pre 成为根 splay(nxt, pre); // nxt 成为 pre 的右孩子 int u tr[nxt].ch[0]; // 此时 val 所在的节点一定在 nxt 的左子树 if (tr[u].cnt 1) { tr[u].cnt--; pushup(u); } else { tr[nxt].ch[0] 0; // 直接断开 } pushup(nxt); pushup(pre); }这个写法的思路是因为 pre val nxtBST 的性质决定了 val 在以 pre 为根时一定位于 pre 的右子树再以 nxt 为根时nxt 是 pre 的右孩子而 val 只能在 nxt 的左子树中。splay 两次之后val 节点就被单独“孤立”成了 nxt 的左孩子这时候删除就是断开一个指针的功夫。实测这个写法在重复值场景下也正确如果 cnt 1只减次数不删节点如果 cnt 1直接移除节点。4.3 查询类操作排名与前驱后继查询前驱后继同样是 BST 的基本查找但我会在找到目标后顺手 splay。这么做并不改变答案但能把目标节点提升到根为后续操作提速。int get_pre(int val) { int u root, res 0; while (u) { if (tr[u].val val) { res u; u tr[u].ch[1]; } else { u tr[u].ch[0]; } } splay(res, 0); return res; } int get_nxt(int val) { int u root, res 0; while (u) { if (tr[u].val val) { res u; u tr[u].ch[0]; } else { u tr[u].ch[1]; } } splay(res, 0); return res; }求排名和按排名查值则要依赖sz。求 val 的排名先查有多少严格小于 val 的数再加 1。按排名查值从根出发看左子树大小决定往哪边走。int get_rank(int val) { insert(val); // 插入后 val 会成为根 int ans tr[tr[root].ch[0]].sz 1; // 左子树大小 1 erase(val); // 再删掉 return ans; } int kth(int k) { int u root; while (true) { int ls tr[u].ch[0]; if (tr[ls].sz k) { u ls; } else if (tr[ls].sz tr[u].cnt k) { splay(u, 0); return tr[u].val; } else { k - tr[ls].sz tr[u].cnt; u tr[u].ch[1]; } } }get_rank里的 insert 再 erase 这种做法看起来有点暴力但胜在好写、正确性高竞赛里常用。它利用的就是插入后的 splay 效果val 节点已经在根上排名一眼就能从根的左子树大小算出来。代价是每次求排名要两次 splay均摊复杂度依然是对的。5. 进阶应用用 Splay 做区间翻转文艺平衡树5.1 序列操作的本质按下标建树Splay 树真正让 AVL 和红黑树羡慕的场景是序列操作。这里的套路是把“下标”当作二叉搜索树的键值中序遍历结果就是数组本身。比如你有数组 [1, 2, 3, 4, 5]建出的树中序遍历依次输出就是 1 到 5。这时候翻转区间 [l, r]等价于把树中对应部分找出来然后整体交换左右子树同时为子树的每个节点打上翻转标记。建树不必一个一个 insert 到根那样 O(n log n) 能过但没必要。更优做法是递归建树每次取区间中点作为当前子树的根中点的左区间建左子树右区间建右子树。void build(int u, int l, int r, int f) { if (l r) return; int mid (l r) 1; u mid; tr[u].fa f; tr[u].val mid; // 这里直接用下标作为值, 也可以改为读入的数组值 tr[u].lazy 0; tr[u].ch[0] tr[u].ch[1] 0; build(tr[u].ch[0], l, mid - 1, u); build(tr[u].ch[1], mid 1, r, u); pushup(u); }这里有个实用技巧区间翻转题目往往还需要在数组首尾加两个哨兵节点。比如原始数组长度是 n我会建 n2 个节点下标 1 到 n2分别对应哨兵、真数组、哨兵。这样翻转 [1, n] 时就能把 0 号位和 n1 号位当作前驱和后继避免边界判断。5.2 懒标记与 pushdown区间翻转如果不打懒标记每次把整棵子树每个节点都翻一遍复杂度直接 O(k log n)不是我们想要的。懒标记的思想是给子树根打上“需要翻转”的标记先不动孩子等下次访问到这个节点时再真正交换左右孩子并把标记传递给孩子们。void pushdown(int x) { if (tr[x].lazy) { swap(tr[x].ch[0], tr[x].ch[1]); if (tr[x].ch[0]) tr[tr[x].ch[0]].lazy ^ 1; if (tr[x].ch[1]) tr[tr[x].ch[1]].lazy ^ 1; tr[x].lazy 0; } }lazy 标记用异或 1 来翻转是因为同一区间翻转两次等于没翻。交换左右孩子就是翻转的实际动作标记只是推迟了这个动作的执行时间。需要注意pushdown 的调用时机很讲究。我踩过的坑是splay 伸展过程中旋转前必须把路径上的懒标记全部下传否则旋转时看到的孩子位置是旧的树结构会乱。所以 splay 函数里我特意先收集从根到目标节点的路径并用栈保存再从上到下依次 pushdown最后才开始旋转循环。5.3 完整区间翻转流程要翻转区间 [l, r]在带哨兵的树上操作步骤非常清晰把下标 l 的前一个位置也就是 l-1对应节点 lsplay 到根。把下标 r 的后一个位置也就是 r1对应节点 r2splay 到 l 节点的右孩子。此时 r1 节点的左子树恰好就是区间 [l, r]直接给它的根打上 lazy 标记。void reverse(int l, int r) { l--; r; // 这里 l、r 传入的是原始数组下标, 加哨兵后要偏移 splay(l, 0); splay(r, l); tr[tr[r].ch[0]].lazy ^ 1; }下面这段是完整的区间翻转 main 逻辑示例。假设数组长度为 n进行 m 次翻转操作最后输出整个数组int main() { int n, m; cin n m; for (int i 2; i n 1; i) tr[i].val i - 1; // 节点 i 对应数组下标 i-1 build(root, 1, n 2, 0); root 1; // build 时传的引用会让 root 最终指向整个树根 while (m--) { int l, r; cin l r; // 因为加了两个哨兵, 实际节点下标要整体加 1 reverse(l 1, r 1); } // 中序遍历输出 dfs(root); return 0; } void dfs(int u) { if (!u) return; pushdown(u); dfs(tr[u].ch[0]); if (tr[u].val 1 tr[u].val n) cout tr[u].val ; dfs(tr[u].ch[1]); }这段代码里reverse(l 1, r 1)的偏移容易出错我吃过一次亏。原因在于build 时区间范围是 1 到 n2哨兵占用了下标 1 和 n2真实数据从下标 2 开始。所以翻转原始 [l, r] 时需要把 l 和 r 都加 1才能对应到树上的节点编号。边界偏移是个高频 bug 点写的时候最好画个图确认。.reverse操作本身不真正动树只打标记。输出时通过 dfs 中序遍历边 pushdown 边输出就能得到翻转后的正确序列。整个实现结构清晰代码量也不大是我见过所有平衡树里做区间翻转最顺手的一种。6. 复杂度、应用场景与踩坑笔记6.1 均摊复杂度下界与势能思想很多读者会问Splay 树不保证每次操作 O(log n)它凭什么敢叫平衡树答案在于均摊复杂度。这里不推导完整势能函数只说直觉把树的“混乱程度”看作势能每次 splay 都把势能消耗一部分同时为下次操作积累一部分。势能法可以证明连续 m 次操作的总体复杂度是 O(m log n)平均下来每次就是 O(log n)。实际跑题的时候单次操作偶尔会出现较慢的情况比如刚插入一个很深的位置然后立刻查询但连续的多次操作整体效率是有保障的。竞赛里 Splay 的常数比 AVL 大一点但比红黑树好写得多所以很多人愿意为了编码效率选它。写 Splay 时还有个经验法则插入、删除、查询后一定要记得 splay。很多新手写着写着就把伸展忘了或者只在某些路径上 splay结果复杂度分析直接失效树会逐渐退化。这个习惯我从第一次写 Splay 就养成凡是有一个节点从深位置被访问过就顺手把它提到根。6.2 典型应用场景盘点Splay 树的应用场景比想象中广。我在竞赛和项目里见到的典型用法有这几类普通平衡树全家桶插入、删除、求前驱后继、求排名、第 k 大。这类题目用 Splay 写代码量比红黑树少一半对重复值的支持也天然友好。区间翻转、区间插入、区间删除、区间求和所有需要“把数组的一段单独拎出来处理”的操作Splay 几乎都是最优解。文艺平衡树洛谷 P3396 等就是经典题目。Link-Cut TreeLCT的辅助树底层LCT 用 Splay 维护实路径上的节点集合利用的就是 Splay 可以快速把路径抽出来重新拼接的能力。学 LCT 之前不把 Splay 写熟后面会非常吃力。可持久化平衡树的简单替代虽然 Splay 本身不太适合可持久化因为形态改动大但在某些需要维护历史版本的题目里可以用别的平衡树Splay 主要承担快速重构的任务。如果你在做数据结构期末实验有一个“平衡树综合实验”的题目Splay 几乎是最友好的选项。AVL 和红黑树的旋转逻辑更繁琐Treap 虽然好写但做不了区间翻转Splay 在这两者之间找到了一个很好的平衡点。6.3 我踩过的坑与调试建议最后把这几年写 Splay 遇到的问题集中整理一下这些基本都是常规文档里不会写的。段错误 / 无限循环优先查父指针。旋转三步中只要有一条父指针没更新树就会断链。我在 rotate 里漏过if (z) tr[z].ch[tr[z].ch[1] y] x的判断导致祖父节点的孩子指针没有指向旋转后的 x后面遍历时直接访问到悬空节点。排查办法在 rotate 结束后临时输出每个节点的 fa、ch[0]、ch[1]对照中序遍历检查父链。懒标记没有在 splay 前下传区间翻转结果错乱。这个问题最隐蔽因为它不会崩溃只是翻转后的数组顺序不对。我加了一组测试数据才意识到是 splay 过程中旋转前没 pushdown。标准做法就是 3.3 节写的路径栈收集从上到下的路径逐个下传。内存池没有初始化孩子为 0。新节点从 tot 取出时ch[0] 和 ch[1] 可能残留上次使用的地址。没清空时插入后循环遍历会走进野节点。我现在统一在创建节点处赋tr[u].ch[0] tr[u].ch[1] 0不留侥幸。数组开小一。Splay 需要哨兵节点操作次数多也会临时分配节点。我习惯开MAXN 5在两侧各留一点余量。因为数组越界在 C 里是未定义行为有时候不崩溃但结果诡异排查起来很浪费时间。调试时加一个中序遍历打印函数。不管实现了多少个操作我都会先在 main 里跑一组小数据比如插入 1 到 7输出中序遍历确认是 1 2 3 4 5 6 7再翻转 [2, 5]输出确认是 1 5 4 3 2 6 7。这个验证函数能救回大量排查时间。如果中序都不对先别查 splay 之外的问题——树的基本结构没搭对后面的操作全是空中楼阁。最后说个小技巧Splay 的调试不要靠 print 堆栈最好写一个debug()函数递归输出整棵树的节点关系编号、val、fa、左右孩子每次操作后调用一次观察树形变化。这个方法帮我定位过至少十个隐蔽 bug。Splay 树是我个人觉得平衡树里最值得手写一遍的。它不像 AVL 那样拘谨也不像红黑树那样复杂用一种很聪明的方式把“近期访问的元素”和“树的形态”绑定在一起。把这套代码吃透后面接触 LCT、序列操作类题目会轻松很多。如果你正在做数据结构实验或者备战竞赛建议先把第 3 节的 rotate 和 splay 函数亲手敲一遍再补上第 4 节的基础操作最后试着运行第 5 节的区间翻转。跑通的那一刻你会对“旋转”这两个字有一种全新的理解。