当前位置：首页 > news >正文

[数据结构] 伸展树(Splay Tree)实战：从零构建无指针版核心操作与性能分析

news 2026/5/12 12:54:03

1. 伸展树基础：从指针到数组的思维转换

第一次接触伸展树时，我被教科书上的指针实现绕得头晕眼花。直到在嵌入式项目中遇到内存限制，才被迫尝试用数组模拟指针——结果意外打开了新世界的大门。无指针实现的核心在于用数组下标代替内存地址，用son[N][2]二维数组表示左右孩子（0左1右），dad[N]记录父节点下标。这种实现方式在算法竞赛中尤为常见，比如处理百万级数据时，数组结构比指针更节省内存且访问更快。

举个例子，传统指针版的节点定义是这样的：

struct Node { int val; Node *left, *right, *parent; };

而无指针版本只需要几个数组：

int val[N], son[N][2], dad[N], siz[N]; // N为最大节点数

实测在STM32F407芯片上，处理10万个节点时，无指针版本比指针版节省约30%内存，且操作速度提升15%。这是因为数组连续存储更符合CPU缓存局部性原理，而指针的动态分配会产生内存碎片。

2. 旋转操作的无指针实现技巧

旋转（spin）是伸展树的基石操作，它让目标节点上升一层。在无指针实现中，我们需要处理四个关键角色：

当前节点v
父节点f = dad[v]
祖父节点ff = dad[f]
需要转移的子树w = son[v][!k]（k表示v是f的左/右孩子）

这段代码是我在调试了7次后才稳定的精华版本：

void spin(int v) { int f = dad[v], ff = dad[f]; int k = (son[f][1] == v); // 判断v是左儿子(0)还是右儿子(1) int w = son[v][!k]; // 需要转移的子树 son[ff][son[ff][1] == f] = v; // 祖父认领新儿子 dad[v] = ff; son[v][!k] = f; // v接管f作为子节点 dad[f] = v; son[f][k] = w; // f接管w if(w) dad[w] = f; up(f); up(v); // 更新子树大小 }

调试时最容易踩的坑是忘记处理w为空的情况。比如当v是叶子节点时，son[v][!k]为0，此时若执行dad[w] = f就会引发内存错误。建议在操作前加上if(w)判断。

3. 伸展操作的优化策略

单纯的旋转只能让节点上升一层，而伸展（splay）操作通过组合旋转将节点提升到根。这里有个关键优化：双旋策略。当v-f-ff形成"直线型"（都是左孩子或都是右孩子）时，先旋转f再旋转v，可以更快平衡树结构。

这个策略在ACM竞赛中特别有效。去年我在一道题目中对比发现，双旋比单旋快40%：

void splay(int v, int to) { while(dad[v] != to) { int f = dad[v], ff = dad[f]; if(ff != to) spin((son[f][0]==v) == (son[ff][0]==f) ? f : v); spin(v); } if(!to) root = v; // 更新根节点 }

实际应用中，我常用势能分析法理解其O(log n)的均摊复杂度。想象每个节点储存着能量，频繁访问的节点通过伸展积累高能量，使得后续操作成本降低。这就像缓存热点数据一样自然。

4. 核心操作实战：从插入到删除

4.1 插入操作的边界处理

无指针实现的插入需要特别注意边界条件。比如首次插入时根节点为空，这时要初始化tot计数器：

void ins(int x) { int v = root, f = 0; while(v && val[v] != x) { f = v; v = son[v][x > val[v]]; // 根据大小选择方向 } if(v) { // 已存在相同值 cot[v]++; } else { // 新建节点 v = ++tot; val[v] = x; cot[v] = siz[v] = 1; dad[v] = f; if(f) son[f][x > val[f]] = v; } splay(v, 0); // 新节点伸展到根 }

在嵌入式设备中，我会预先分配固定大小的数组，并通过tot判断是否溢出。曾经因为忘记检查tot<N导致设备重启，这个教训让我养成了写防御性代码的习惯。

4.2 删除操作的精妙设计

删除是最容易出bug的操作。我的方案是先把前驱转到根，再把后继转到根的右孩子，此时待删节点一定在后继的左子树且没有孩子：

void del(int x) { int prev = next(x, 0); // 前驱 int succ = next(x, 1); // 后继 splay(prev, 0); splay(succ, prev); int del_node = son[succ][0]; if(cot[del_node] > 1) { cot[del_node]--; splay(del_node, 0); } else { son[succ][0] = 0; } }

这个设计来自一次深夜调试——当时直接删除根节点导致左右子树丢失。现在的方案虽然多了一次splay操作，但保证了结构稳定。在数据频繁更新的场景下，这种实现比普通BST可靠得多。