Splay树实现详解：旋转、双旋与区间翻转实战

如果你在搜索平衡树资料，肯定会看到这句话：“Splay树，也称伸展树，能在均摊O(log n)时间内完成插入、查找和删除操作。”但真上手写代码时，你会发现这个“翻到根”的动作里全是细节。我从只会背模板到能用它轻松写区间翻转题，中间踩了无数个指针悬空、旋转方向写反的坑。这篇文章是完整经验记录，不讲虚的，只讲旋转为什么这么写、双旋为什么必不可少、插入删除里有哪些顺序陷阱、调试时怎么快速定位问题。适合正在学平衡树的学生、准备算法竞赛的选手，以及工作中需要区间操作场景的工程师。

1. 从AVL到Splay：为什么平衡树家族需要“伸展”这种新思路

1.1 传统平衡树的痛点

先聊聊经典的AVL树和红黑树。它们的思想很直接：每次插入或删除后，检查树上每个节点的平衡因子，一旦失衡就通过旋转调整。AVL树要求任意节点的左右子树高度差不超过1，红黑树用颜色约束最长路径不超最短路径两倍。这两种方案都能保证严格或近似平衡，但代价是：每次修改后可能需要回溯到根，逐个维护平衡信息，代码量大，边界情况多。

我当时学AVL树时最痛苦的就是四种旋转形态：LL、RR、LR、RL，每种还对应不同的调整顺序，稍不留神就转错。红黑树更不用说了，插入有5种情况，删除有6种，光是记忆这些case就能劝退一大半人。而Splay树的思路完全不同——它不追求任何时刻都平衡，只做一件事：把刚被访问的节点旋转到根。

1.2 Splay树的“蹭热点”哲学

Splay树的核心理念可以类比成“热点置顶”：谁被访问，谁就上首页。具体来说，每次查找、插入、删除之后，都要通过一系列旋转，把涉及的节点送到树根。

这个思路妙在哪里？它利用了程序的时间局部性——如果一个数据被访问了，它很可能很快再被访问。把热点数据放在树根附近，下次访问它的成本就极低。即便某次操作让树变得“歪歪扭扭”，后面某次访问又会把另一个节点顶到根，整体效果反而趋于均衡。

我常用一个比喻：想象一个热榜榜单，被点击最多的内容永远置顶，冷门内容慢慢沉底。Splay树就是这种“热榜机制”的树形实现。它不需要记录高度、不需要颜色标记，只需要维护每个节点子树的大小（size），实现成本比AVL和红黑树低得多。

1.3 均摊复杂度的直觉理解

很多人第一次看到“均摊O(log n)”会问：每次splay都可能把树转得更歪，凭什么说总体效率有保障？

简单地说，Splay树证明的核心在于：每次访问一个深度为d的节点，把它转上来消耗O(d)时间，但这个过程会“压缩”路径上的节点，让它们整体离根更近。你可以把树的势能理解为“所有节点深度之和”的某种加权形式，每次splay操作虽然消耗时间，但同时也把这个势能降下去一部分。整个过程是此消彼长的，均摊下来每个操作就只剩O(log n)了。

2. 旋转三式：zig、zig-zig、zig-zag到底怎么转

2.1 统一旋转函数：一个rotate搞定左旋和右旋

在写Splay树之前，先把最基础的单次旋转搞清楚。传统平衡树把旋转分成左旋和右旋两种，但Splay树习惯用ch[0]表示左孩子、ch[1]表示右孩子，然后用一个统一的rotate(x)函数表示“把x向上提一层”。

以右旋为例：如果x是y的左孩子，右旋就是把x提到y的位置，y变成x的右孩子，x原来的右子树变成y的左子树。反过来就是左旋。用C++写：

struct Node { int val; // 节点值 int size; // 子树大小 Node *ch[2]; // 左右孩子 Node *fa; // 父节点指针 Node(int v) : val(v), size(1) { ch[0] = ch[1] = fa = nullptr; } }; void pushup(Node *x) { x->size = 1; if (x->ch[0]) x->size += x->ch[0]->size; if (x->ch[1]) x->size += x->ch[1]->size; } void rotate(Node *x) { Node *y = x->fa; // x的父节点 Node *z = y->fa; // y的父节点 int k = (x == y->ch[1]); // x是y的哪个孩子，0左1右 // 第一步：把x挂到z上，替代y的位置 if (z) { if (y == z->ch[0]) z->ch[0] = x; else z->ch[1] = x; } x->fa = z; // 第二步：x的另外一个孩子过继给y y->ch[k] = x->ch[k ^ 1]; if (x->ch[k ^ 1]) x->ch[k ^ 1]->fa = y; // 第三步：y变成x的孩子 x->ch[k ^ 1] = y; y->fa = x; // 更新信息，注意先更新y再更新x pushup(y); pushup(x); }

这里的关键是用k ^ 1表示x的另一个孩子方向，代码简洁且左右旋共用。我第一次手写时总在ch[k]和ch[k ^ 1]之间绕晕，后来记住一个口诀：把x的“外侧子树”让给y，把y“让位”给x。

2.2 三种伸展模式

把节点x转到根，不是简单地一直调用rotate(x)就行。Splay树定义了三种情况：

• zig（单旋）：当x的父节点是根时，直接rotate(x)。
• zig-zig（同侧双旋）：当x、x的父节点y、y的父节点z三者都在同一侧（比如x是y的左孩子，y也是z的左孩子），先rotate(y)，再rotate(x)。
• zig-zag（异侧双旋）：当三者不在同一侧，先rotate(x)，再rotate(x)。

写成代码：

void splay(Node *x, Node *goal) { while (x->fa != goal) { Node *y = x->fa; if (y->fa != goal) { if ((y == y->fa->ch[1]) == (x == y->ch[1])) { rotate(y); // zig-zig } else { rotate(x); // zig-zag } } rotate(x); // zig 或双旋的最后一步 } if (!goal) root = x; }

这里goal参数非常重要：我们不一定每次都要转到根，有时想把某个节点转到另一个节点的孩子位置。当goal = nullptr时表示转到根节点，此时要更新root。

2.3 为什么zig-zig要先转父节点

这是初学者最容易忽略的问题：同为双旋，为什么zig-zig不直接连续两次rotate(x)？

我写了一个小实验对比过。假设有一条“向左链”的极端结构：z的左孩子是y，y的左孩子是x。如果连续两次rotate(x)：

• 第一次：x上移，y变成x的右孩子，z的左孩子变成x。
• 第二次：x上移，z变成x的右孩子，x原来的右子树变成z的左子树。

你会得到一棵“右倾”的树，链还是那么长，只是方向变了。而如果先转y：y上移替代z，x再上移替代y，整棵树的整体高度明显更矮。

这个差异是Splay树证明的核心：只有zig-zig采用“先父后子”的顺序，才能真正压缩路径长度，从而保证均摊复杂度。如果只用单旋或错误的双旋顺序，最坏情况下访问最深层节点会导致树退化成链表，均摊复杂度会掉到O(n)。

3. 核心操作代码拆解：splay、插入、删除与信息维护

3.1 插入操作：先BST插入，再splay到根

Splay树的插入分两步走：

1. 按二叉搜索树的规则找到插入位置，新建节点。
2. 把新节点splay到根。

void insert(int v) { if (!root) { root = new Node(v); return; } Node *cur = root, *par = nullptr; while (cur) { par = cur; cur = cur->ch[v > cur->val]; // v大往右，v小往左 } cur = new Node(v); cur->fa = par; if (v > par->val) par->ch[1] = cur; else par->ch[0] = cur; splay(cur, nullptr); // 新节点转到根 }

为什么插入后一定要splay一次？两个原因：一是新插入的节点极有可能马上被访问，把它放根上能加速后续查找；二是splay过程会顺带修正插入路径上的不平衡，让树整体更健康。

3.2 删除操作：splay到根后分类合并

Splay树的删除比插入复杂一点。目标是删除值为v的节点：

1. 先按BST规则找到该节点，找不到直接返回。
2. 把它splay到根。
3. 根据左右子树情况合并。

合并逻辑分三种情况：

• 根没有左孩子：直接把右孩子作为新根。
• 根没有右孩子：直接把左孩子作为新根。
• 两棵子树都在：找到左子树中最大值节点mx，把它splay成根的左孩子。由于mx是左子树最大，它必然没有右孩子，此时把整个右子树拼到mx的右孩子上，mx作为新根。

void erase(int v) { Node *cur = root; while (cur && cur->val != v) { if (v < cur->val) cur = cur->ch[0]; else cur = cur->ch[1]; } if (!cur) return; splay(cur, nullptr); // 要删的节点转到根 if (!cur->ch[0]) { // 没有左孩子 root = cur->ch[1]; if (root) root->fa = nullptr; delete cur; return; } if (!cur->ch[1]) { // 没有右孩子 root = cur->ch[0]; root->fa = nullptr; delete cur; return; } // 找左子树中最大的节点 Node *mx = cur->ch[0]; while (mx->ch[1]) mx = mx->ch[1]; splay(mx, cur); // mx成为cur的左孩子 // 拼接右子树 mx->ch[1] = cur->ch[1]; cur->ch[1]->fa = mx; root = mx; root->fa = nullptr; pushup(mx); delete cur; }

注意while (mx->ch[1])这一步必须先把mxsplay到cur的左孩子位置。因为mx是左子树中的最大节点，它没有右孩子，所以拼接时只需维护一次fa指针。这个“先把最大值转到目标节点孩子位置”的技巧，是Splay树删除操作不出错的核心。

3.3 pushup的更新顺序

在rotate函数中，我特意写了“先更新y再更新x”。为什么？

因为旋转之后，y变成了x的孩子，x原来的某个子树过继给了y。此时y的子树结构已经改变，而x的子树结构依赖于y的信息。所以必须先把旧的y更新正确，再更新x。顺序反了会导致size统计错误，后续插入删除的排名、选择操作全部乱套。

这算是我踩过的一个比较隐蔽的坑。当时splay操作一切正常，但kth函数总是返回错误的节点，排查了很久才发现是pushup(y); pushup(x);写成了pushup(x); pushup(y);。

3.4 查找第k小节点

因为每个节点维护了子树大小size，Splay树可以很方便地支持按排名查询：

int kth(int k) { Node *cur = root; while (cur) { int leftSize = (cur->ch[0] ? cur->ch[0]->size : 0); if (k <= leftSize) { cur = cur->ch[0]; } else if (k == leftSize + 1) { splay(cur, nullptr); // 顺手转到根 return cur->val; } else { k -= leftSize + 1; cur = cur->ch[1]; } } return -1; }

查找后顺手splay到根，是Splay树的风格——每次访问都提升节点位置，提高后续访问效率。

4. 进阶玩法：把Splay树当“区间容器”用

4.1 从二叉搜索树到序列维护

Splay树最大的价值不在“平衡树”，而在它能用中序遍历表示一个序列，把区间操作变成树上的旋转操作。

具体做法：将序列下标作为BST的键值顺序，中序遍历就是原序列。此时Splay树的“排名k”就是序列中的第k个位置，kth函数用来定位某个下标对应的节点。

最实用的两个操作是区间翻转和区间提取。比如经典题目“文艺平衡树”：维护一个序列，支持对某个区间执行翻转操作。

4.2 哨兵节点与区间提取

要在Splay树中提取区间[l, r]，标准套路是：

1. 在序列两端插入哨兵节点（下标0和下标n+1），这样始终有真实节点可操作。
2. 把第l个节点splay到根。
3. 把第r+2个节点splay到根节点的右孩子位置。

此时，根节点的右孩子的左子树，恰好就是区间[l, r]。为什么是r+2？因为哨兵占了0号位，原第1个元素在新树里是第2个节点（rank为2）。所以提取原序列l位置，实际对应树上rankl+1，提取右边界对应rankr+3，而r+2是区间最后一个元素，所以把r+1位置的哨兵转到根右侧。

我在初学阶段经常把下标搞混。建议在写代码前先画一棵带哨兵的中序序列，标好每个节点的rank，再对号入座写splay参数。

4.3 文艺平衡树的完整核心代码

为支持区间翻转，每个节点加一个lazy懒标记，表示“以该节点为根的子树是否需要翻转”。

void pushdown(Node *x) { if (x && x->lazy) { swap(x->ch[0], x->ch[1]); if (x->ch[0]) x->ch[0]->lazy ^= 1; if (x->ch[1]) x->ch[1]->lazy ^= 1; x->lazy = 0; } } void reverseRange(int l, int r) { // 哨兵版下标：第l个元素对应rank l，第r个对应rank r+2 Node *left = kth(l); // 第l-1个节点到根 Node *right = kth(r + 2); // 第r+1个节点到根的右孩子 splay(left, nullptr); splay(right, left); Node *target = right->ch[0]; // 区间就是right的左子树 target->lazy ^= 1; }

区间提取后，对整棵子树打懒标记，翻转时只需交换左右孩子，并下传标记。查询时遇到懒标记先pushdown，再进行下钻。这是标准的“懒传播”思路，和线段树的懒标记如出一辙，只是一棵按值组织，一棵按下标组织。

4.4 区间最大子段和等其他维护

翻转之外，Splay树还能做很多线段树能做的事，比如区间求和、区间最大子段和、区间赋值等。只要在pushup时合并左右子树的信息即可。

比如维护最大子段和，节点需要存储四个值：区间和sum、前缀最大lmax、后缀最大rmax、整体最大maxSub。pushup时：

x->sum = l->sum + r->sum; x->lmax = max(l->lmax, l->sum + r->lmax); x->rmax = max(r->rmax, r->sum + l->rmax); x->maxSub = max({l->maxSub, r->maxSub, l->rmax + r->lmax});

这套公式和线段树完全一致，区别只是Splay树需要处理中间节点本身的权值。Splay树做区间操作的另一个好处是：支持在任意位置插入和删除一段序列。只要先把要操作的位置提取出来，再把新序列构造成一棵平衡树接上去就行。这个能力是静态线段树很难做到的。

5. 摊还复杂度与实战选型：Splay不是银弹

5.1 什么时候该用Splay树

我个人的经验是：如果你是刚入门平衡树，想写一个支持插入删除查找排名的数据结构，首选不是Splay，而是Treap或FHQ Treap。它们代码更短、理解更简单、常数也更小。但如果你遇到下面这些需求，Splay是很好的选择：

• 需要维护一个序列，支持区间翻转、区间插入、区间删除。
• 需要对一个动态序列执行分割和合并操作。
• 需要频繁访问某个区间，并且在访问后希望这个区间附近节点保持在高位。

特别是在“文艺平衡树”类问题中，Splay几乎是标准解法。FHQ Treap也能做区间翻转，但Splay的“splay到目标位置”操作天然适配区间提取。

5.2 与其他平衡树的对比

注意Splay单次操作最坏可以达到O(n)，比如反复访问最深层节点时单次旋转次数是O(n)。但均摊意义下，这种最坏情况的发生频率被势能约束住了。如果对单次操作延迟敏感、不能接受偶发长耗时，Splay就不是合适的选择。

5.3 一个实战判断标准

我现在的选择逻辑很简单：

• 只要“普通平衡树”（动态前驱、后继、排名、第k小），直接上Treap，代码量小，不容易写错。
• 要“区间序列操作”（翻转、插入删除一段、区间查询合并），上Splay。
• 需要“可持久化平衡树”，上FHQ Treap（无旋转，方便复制节点）。
• 参加竞赛时如果时间紧张，优先写Treap保底，再用Splay做区间大题。

这样分工之后，我不会在每一题里都纠结数据结构选型问题，能把精力集中在算法思路上。

6. 实测踩坑记录与调试三板斧

6.1 经典错误：旋转后root没有更新

如果你在splay之后直接访问root，发现root的fa不是nullptr，或者root指向的节点不对，十有八九是rotate函数里splay到根后忘更新root。我的习惯是：splay函数的最后统一判断：

if (!goal) root = x;

同时在rotate函数中不直接改root，只调整父子指针关系。这样分层清晰：rotate只负责“提一层”，splay负责“转到目标”，root的维护集中在splay尾部。

6.2 经典错误：pushdown写在哪

区间操作需要懒标记，但翻转向下传递的时机非常讲究。常见错误是：查询/下钻时没有先pushdown，导致树的实际结构与中序遍历不一致。

我的规则是：任何进入孩子节点的操作前，先pushdown当前节点。包括kth函数、splay函数、erase函数里的路径查找。尤其splay中旋转前必须先pushdown所有相关节点，否则翻转标记可能导致旋转方向错误。

6.3 经典错误：数组越界的隐含后果

有些人习惯用数组模拟指针（int ch[N][2]）代替new节点。这没问题，但建树时要提前申请足够空间，特别是区间插入一段长为m的序列时，需要m个新节点。我吃过亏：开小了导致分配节点后数组越界，程序跑起来时好时坏，极难排查。

建议用数组实现时统一宏定义N = 100010之类的上限，建树前统计最大节点数，用一个tot指针动态分配。用指针new方案则要小心内存泄漏，不过在竞赛环境影响不大。

6.4 调试三板斧

Splay出bug的根本难点在于指针关系复杂，肉眼几乎看不出问题。我目前最推荐的三板斧：

第一，中序遍历验证。Splay树的中序遍历必须是原序列（或有序序列）。写一个dfs打印中序结果，任何一步操作后对照一下，能快速发现结构问题。

void dfs(Node *x) { if (!x) return; pushdown(x); dfs(x->ch[0]); printf("%d ", x->val); dfs(x->ch[1]); }

第二，对拍验证。生成随机操作序列，用数组或vector暴力模拟，和Splay树跑同一个操作，输出结果对比。一旦不一致，缩小到最小复现数据再手推。

第三，画图手推。旋转代码写完后，手动构造一个三节点或四节点的小树，把每次旋转前后的形态画出来，逐行对照代码中的指针修改。这个办法虽然笨，但能治愈“旋转方向搞反”的顽疾。

6.5 一个稳定的小技巧

最后分享一个我一直在用的工程小习惯：在节点结构体里加一个int id或者直接用内存地址，打印调试信息时同时输出节点值和它的内存编号，这样能分清楚两个相同值的不同节点。

比如：

void debugPrint(Node *x) { if (!x) return; printf("node=%p val=%d size=%d fa=%p ", x, x->val, x->size, x->fa); if (x->ch[0]) printf("l=%p ", x->ch[0]); if (x->ch[1]) printf("r=%p ", x->ch[1]); printf("\n"); }

把每个节点的父子关系完整打出来，对照中序序列检查，基本能确定90%的指针bug。

大概每个认真写过Splay树的人，都有过“三个小时调不出一个旋转”的崩溃经历。我自己也不例外，但踩完这些坑后的收获非常大——Splay树的实现过程本质上是对二叉搜索树、旋转、信息维护、懒标记传播的综合训练。学会它之后，再看各种平衡树和区间数据结构的实现，思路都会清晰很多。最后给个小建议：初学阶段把代码注释写全，用随机数据对拍验证，比反复读教程有用得多。要是这篇文章能帮你少熬几个debug的夜，那就值了。