企业官网建设流程全解析

这会儿想说点关于数据结构的硬核内容。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 < nxt，BST 的性质决定了 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，我会建 n+2 个节点，下标 1 到 n+2，分别对应哨兵、真数组、哨兵。这样翻转 [1, n] 时就能把 0 号位和 n+1 号位当作前驱和后继，避免边界判断。

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]，在带哨兵的树上操作步骤非常清晰：

1. 把下标 l 的前一个位置（也就是 l-1，对应节点 l）splay 到根。
2. 把下标 r 的后一个位置（也就是 r+1，对应节点 r+2）splay 到 l 节点的右孩子。
3. 此时 r+1 节点的左子树恰好就是区间 [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 到 n+2，哨兵占用了下标 1 和 n+2，真实数据从下标 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 Tree（LCT）的辅助树底层：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 节的区间翻转。跑通的那一刻，你会对“旋转”这两个字有一种全新的理解。