高级数据结构-03：伸展树

预备知识

二叉树枚举

给定 $n$ 个节点，可以通过栈操作序列枚举不同拓扑结构的二叉树。在深度优先遍历或树的动态生成过程中，每一次向左下方深入可视为一次 Push，每一次向父节点或右子树回溯可视为一次 Pop。包含 $n$ 个节点的二叉树，其生成过程包含 $n$ 次 Push 和 $n$ 次 Pop。

不同的 Push 与 Pop 组合对应不同的二叉树形态。针对特定节点数，可以记录每种二叉树形态对应的有效操作序列：

上述序列满足一个基本约束：任意前缀中，Pop 次数不能超过 Push 次数。否则相当于访问空树的父节点，对应非法树结构。带有这种前缀非负约束的序列生成问题，与多种经典组合计数问题同构。

卡塔兰数

网格路径问题

上述栈排列问题可以抽象为网格路径问题：在一个 $n \times n$ 的二维网格中，寻找从左下角到右上角的最短路径。每一步只能向右（对应 Push）或向上（对应 Pop）。

若不加约束，最短路径数为 $\binom{2n}{n}$ ，即在 $2n$ 步中选择 $n$ 步向右。为了满足前缀非负约束，即任意时刻向上的步数不能超过向右的步数，需要限制路径不能越过主对角线，只能在对角线及以下区域移动。

如路径示意图所示，一条合法的路径可以被等价编码为不同的符号串：

字符序列表示：OCOOOCCOCOCC （其中 O 代表横向的 Open/Push，C 代表纵向的 Close/Pop）。
括号嵌套表示：()((( ))()())。其中左括号 ( 对应向右一步，右括号 ) 对应向上一步。对角线不被穿越，等价于括号字符串中任意前缀的右括号数量不超过左括号数量。

计算合法路径数量时，可以使用反射原理。若一条路径越过主对角线，则它必然与对角线上方一单位的直线 $y = x + 1$ 相交。

找到该路径与 $y = x + 1$ 的第一个交点，并将交点之后的路径部分关于这条直线对称翻转。翻转前，原路径终点是 $(n, n)$ ；翻转后，终点变为 $(n-1, n+1)$ 。由于从 $(0,0)$ 到 $(n-1, n+1)$ 的任意单调路径都必然穿过 $y = x + 1$ ，于是得到一个双射：从 $(0,0)$ 到 $(n, n)$ 的所有非法路径，与从 $(0,0)$ 到 $(n-1, n+1)$ 的所有无约束路径一一对应。

到达 $(n-1, n+1)$ 的路径数为 $\binom{2n}{n-1}$ 或 $\binom{2n}{n+1}$ 。因此，合法路径总数等于总路径数减去非法路径数，得到卡塔兰数的减法定义式：

$C_{n}=\binom{2n}{n}-\binom{2n}{n+1}$

帕斯卡三角形中的中心列分布

卡塔兰数的减法公式 $C_{n}=\binom{2n}{n}-\binom{2n}{n+1}$ 可以从帕斯卡三角形的中央列分布中观察到。中心列数据 $\binom{2n}{n}$ 减去相邻列数据 $\binom{2n}{n+1}$ ，得到卡塔兰数序列：

深度 2n	中心列项 (n2n)	相邻列项 (n+12n)	相减差值 (Cn)
2	2	1	$2 - 1 = 1$
4	6	4	$6 - 4 = 2$
6	20	15	$20 - 15 = 5$
8	70	56	$70 - 56 = 14$
10	252	210	$252 - 210 = 42$

括号匹配与矩阵乘

除树形枚举外，卡塔兰数还出现在以下问题中：

括号匹配问题： 合法安排 $n$ 对括号时，字符串必须满足开闭括号数量相等，且任意前缀的右括号数量不超过左括号数量。例如，()()()、(()())、()(()) 合法，而 )())(( 非法。当 $n=3$ 时，存在 $C_3 = 5$ 种合法序列。
矩阵链乘优化： 计算 $n$ 个矩阵乘积 $M_1 * M_2 * \dots * M_n$ 时，矩阵乘法满足结合律但不满足交换律，不同加括号方式会影响标量乘法总量。这等价于统计给定前序遍历序列 $1, 2, \dots, n$ 的二叉树能够产生多少种中序遍历排列。设 $b_n$ 为 $n$ 个矩阵乘积的不同加括号方式数量，则有：
- $n=3$ : $(M_1*M_2)*M_3$ 以及 $M_1*(M_2*M_3)$ ，共 $b_3 = 2$ 种。
- $n=4$ : 共 $b_4 = 5$ 种。通项满足卡塔兰卷积： $b_{n}=\sum_{i=1}^{n-1}b_{i}b_{n-i}$ （其中 $n>1$ ）。

卡塔兰数说明二叉树形态数量很大，其中包含高度为 $\mathcal{O}(n)$ 的退化结构，因此需要引入树平衡机制。

AVL 树与 B-树

AVL 树

AVL 树对平衡因子施加约束：任意节点的左右子树高度差绝对值不得超过 1。

对比 $n=88$ 时的树形可知，随机生成的 BST 可能出现较深的偏斜分支；AVL 树通过平衡约束保持接近平衡的层级结构，将高度限制在 $\mathcal{O}(\log n)$ 。

局部失衡调整

在 AVL 树中，插入或删除节点可能破坏高度平衡。按照失衡路径中节点的相对位置，传统重平衡分为四种情况：

Left Left Case (LL)：需要进行一次单次右旋。
Right Right Case (RR)：需要进行一次单次左旋。
Left Right Case (LR)：需要先做一次左旋，再做一次右旋。
Right Left Case (RL)：需要先做一次右旋，再做一次左旋。

这种按情况处理的方式有效，但实现中需要较多条件分支。

3+4 重构

为了简化传统旋转逻辑，可以引入 3+4 重构。该方法通过重新组织局部节点与子树完成平衡调整。

设 $g$ 为插入或删除后发现的最低失衡节点。考察失衡路径上的祖孙三代节点： $g$ （祖父）、 $p$ （父亲）、 $v$ （孙子）。由于三者属于同一棵二叉搜索树，它们具有确定的相对大小。按照中序遍历次序，将这三个节点重新命名为 $a, b, c$ ，使得 $a < b < c$ 。

这三个节点作为内部骨架，向外连接四棵互不相交且可能为空的子树。按照中序遍历次序，将四棵子树命名为 $T_0, T_1, T_2, T_3$ 。由于中序遍历保持单调递增，原始树满足：

$T_0 < a < T_1 < b < T_2 < c < T_3$

算法将原先以 $g$ 为根的子树 $S$ 替换为新子树 $S'$ ，构建规则如下：

将居中的 $b$ 提升为新子树根节点，即 $root(S') = b$ 。
将 $a$ 作为 $b$ 的左孩子（ $lc(b) = a$ ），将 $c$ 作为 $b$ 的右孩子（ $rc(b) = c$ ）。
按顺序挂接四棵子树： $a$ 的左子树为 $T_0$ （ $lT(a) = T_0$ ），右子树为 $T_1$ （ $rT(a) = T_1$ ）； $c$ 的左子树为 $T_2$ （ $lT(c) = T_2$ ），右子树为 $T_3$ （ $rT(c) = T_3$ ）。

通过一次 $\mathcal{O}(1)$ 的局部重组，失衡被消除，且新树的中序遍历仍为 $T_0 < a < T_1 < b < T_2 < c < T_3$ 。该过程覆盖传统的 LL、RR、LR、RL 四种情形。

3+4 重构不是在改变这几个关键码的大小关系，而是在保持中序序列完全不变的前提下重新安排局部高度。读这类图时可以先忽略指针方向，只看排序骨架：三个节点必然能排成 $a<b<c$ ，四棵子树必然能嵌入五个间隔中。只要重构后仍满足 $T_0<a<T_1<b<T_2<c<T_3$ ，二叉搜索树的不变量就没有被破坏。

B-树及其变体

当搜索树规模大到需要存储在磁盘等外存设备中时，二叉树的层级结构会导致过多页面 I/O。B 树通过允许节点拥有多个分支来降低树高。

阶数为 $m$ 的 B 树允许节点拥有至多 $m$ 个分支。低阶特例如下：

$m=3$ 时，即为 2-3-树。各内部节点的分支数只能是 2 或 3，含有的 key 数量为 1 或 2。
$m=4$ 时，为 2-3-4-树。分支数可能为 2、3 或 4，key 数量为 1、2 或 3。红黑树可以视为一棵等价 2-3-4 树的二叉实现，其中红色节点表示与其父节点在 B 树中处于同一个逻辑节点内，而颜色翻转机制对应 B 树中的节点分裂。

伸展树

AVL 树和红黑树提供了 $\mathcal{O}(\log n)$ 最坏情况边界，但需要维护额外状态位（平衡因子或颜色），并承担重平衡开销。另一方面，严格平衡结构不直接利用数据访问局部性：刚被访问过的数据及其附近数据，通常更可能再次被访问。

对传统 AVL 树进行连续 $m$ 次相关查找（ $m \gg n$ ），总时间仍为 $\mathcal{O}(m \log n)$ 。伸展树利用局部性进行自适应调整：它不维护显式平衡约束，而规定节点一旦被访问，就将其调整到树根。

逐层单旋

“将目标节点推至根”的具体方式会影响分摊复杂度。早期直观方法是逐层伸展：当节点 $v$ 被访问后，反复对其与父节点 $p$ 执行单旋。若 $v$ 是左孩子，执行 zig(p)；若是右孩子，执行 zag(p)，直到 $v$ 到达根。

逐层调整在某些情况下效率较低。考虑一个最坏情况：初始结构是一条向左倾斜的单链（例如插入顺序为 $5, 4, 3, 2, 1$ ）。此时顺序执行 search(1), search(2), search(3), search(4), search(5)：

当 search(1) 时，1 通过逐层 zig 被推到树根，但其余节点仍保留较长路径。
连续从深层节点查找会产生 $\Omega(n^2)$ 次旋转，每一周期的分摊时间可达 $\Omega(n)$ 。因此，需要引入新的伸展策略。

双层伸展

为改进逐层伸展，规则改为：每次向上处理两层。设 $v$ 为当前访问节点， $p = \text{parent}(v)$ ， $g = \text{parent}(p)$ 。根据三者拓扑关系，算法执行成对旋转，使 $v$ 上升两层并成为局部子树根。

情况 1：zig-zag / zag-zig。 如果 $v$ 是左孩子的右孩子（zig-zag），或者右孩子的左孩子（zag-zig），则 $v$ 在中序遍历次序中居中。

此时算法执行一次底层旋转（例如对 $v$ 和 $p$ ），紧接着再对 $v$ 和 $g$ 执行一次旋转。
这种调整与连续两次逐层调整效果相同，将 $v$ 推到祖父位置，并重新分布局部子树。
这种情况的调整相当于做了一次 3+4 重构。

情况 2：zig-zig / zag-zag。 这是伸展策略改进逐层单旋最坏行为的关键。如果 $v$ 是左孩子的左孩子，或者右孩子的右孩子：

传统逐层调整会先转 $v$ 和 $p$ 。而在伸展树中，必须先转 $p$ 和 $g$ ，然后再转 $v$ 和 $p$ 。
即先执行 zig(g)，再执行 zig(p)（或全为 zag）。
折叠效应： 按这种顺序旋转后，原本位于同一侧的长链结构会被压缩。由于优先旋转上层祖父节点，访问路径长度会缩短。当对单链底部节点执行 search(1) 后，双层调整会重新分布退化链条。访问路径持续被压缩，是伸展操作分摊时间达到 $\mathcal{O}(\log n)$ 的直观原因。

zig-zig 的旋转顺序是伸展树最容易读错的地方。它不是单纯为了把 $v$ 提高两层，而是顺手把访问路径上的一段长链压短；如果仍按逐层单旋的顺序操作，目标节点虽然也能到根，但其余节点不会获得足够的折叠收益，后续访问仍可能反复走长路径。

情况 3：zig / zag。 如果 $v$ 上升到最后只剩父节点 $p$ ，且没有祖父 $g$ （即 $p$ 已是整棵树根），则只需一次单旋 zig(r) 或 zag(r) 将 $v$ 推到根部。该情况在每次伸展中至多出现一次。

(还有一种名为半伸展（Semi-splaying）的变体。在 zig-zig 情况下，旋转一次后 $v$ 并不继续上升，而是让焦点转移到其父节点，仅把 $v$ 推进一半深度。这减少了重构的操作量且保持了渐进效率，但实际实现复杂度的增加以及合并分离操作的困难，使得全伸展依然是主流方案 )。

算法实现

为复用二叉搜索树逻辑，伸展树 Splay<T> 由标准二叉搜索树模板 BST<T> 派生：

// Splay 复用 BST 的基本节点与查找框架，但会重写会改变拓扑的操作。
template <typename T> class Splay: public BST<T> {
protected:
    // 将节点 v 通过 zig-zig、zig-zag 或单旋提升到当前子树根。
    BinNodePosi<T> splay(BinNodePosi<T> v);
public:
    // 查找会把命中节点或最后访问节点伸展到根。
    BinNodePosi<T> & search(const T & e);
    // 插入围绕伸展后的根执行分裂与接入。
    BinNodePosi<T> insert(const T & e);
    // 删除围绕伸展后的根执行左右子树合并。
    bool remove(const T & e);
};

`splay` 实现

splay 方法以 while 循环实现。只要当前节点仍有祖父节点，就反复自下而上执行双层伸展。

template <typename T>
BinNodePosi<T> Splay<T>::splay(BinNodePosi<T> v) {
    // 空节点无法伸展，直接返回。
    if (!v) return NULL;
    // p 指向父节点，g 指向祖父节点。
    BinNodePosi<T> p, g;

    // 只要 v 同时存在父节点和祖父节点，就执行一次双层伸展。
    while ((p = v->parent) && (g = p->parent)) {
        // gg 是原局部子树的父节点，旋转后需要把新根重新接回 gg。
        BinNodePosi<T> gg = g->parent;

        if (IsLChild(*v)) {
            // v 是左孩子，继续判断 p 与 g 的相对方向。
            if (IsLChild(*p)) {
                // zig-zig：v、p 都在左侧，先调整 g 与 p，再调整 p 与 v。
                attachAsLC(p->rc, g); attachAsLC(v->rc, p);
                attachAsRC(p, g); attachAsRC(v, p);
            } else {
                // zig-zag：v 在左侧，p 在右侧，需执行双旋并保持中序关系。
                /* zig-zag 逻辑 */
            }
        } else {
            // v 是右孩子，处理右侧对称情形。
            if (IsRChild(*p)) {
                // zag-zag：v、p 都在右侧，对称于 zig-zig。
                /* zag-zag: 右孩子的右孩子逻辑 */
            } else {
                // zag-zig：v 在右侧，p 在左侧，对称于 zig-zag。
                /* zag-zig 逻辑 */
            }
        }

        // 若原局部子树没有曾祖父，则 v 已成为整棵树根。
        if (!gg) v->parent = NULL;
        // 否则按 g 原来相对 gg 的方向，把伸展后的局部根 v 接回去。
        else (g == gg->lc) ? attachAsLC(v, gg) : attachAsRC(v, gg);

        // 指针关系改变后，自下而上更新局部节点高度。
        updateHeight(g); updateHeight(p); updateHeight(v);
    }

    // 若循环结束时只剩父节点 p，则通过一次单旋把 v 提升到根。
    if ((p = v->parent)) {
        /* 若最后p果真是根，只需额外执行一次 zig 或 zag 的单旋 */
    }
    // 根节点没有父节点。
    v->parent = NULL;
    // 返回伸展后的根节点。
    return v;
}

在 zig-zig 分支中，代码先将 $p$ 的右子树接到 $g$ 左侧，将 $v$ 的右子树接到 $p$ 左侧，再让 $g$ 成为 $p$ 的右孩子， $p$ 成为 $v$ 的右孩子，从而完成同向路径上的双层旋转。

接口重写与 hot 机制

伸展树的查找 search 不是只读操作，它会修改树结构。在 search 内部，先调用基类的 BST::search(e) 定位节点。无论查找成功还是失败，BST 中记录最后访问位置的 _hot 都会用于后续调整。

template <typename T>
BinNodePosi<T> & Splay<T>::search(const T & e) {
    // 先调用 BST 搜索；成功时 p 指向命中节点，失败时 _hot 记录最后访问节点。
    BinNodePosi<T> p = BST<T>::search(e);
    // 搜索成功则伸展 p；搜索失败则伸展 _hot，使后续插入或删除可围绕根处理。
    _root = splay(p? p : _hot);
    // 返回根引用，外部可按 BST 接口继续判断命中结果。
    return _root;
}

由于每次搜索都会将相关节点移至根，伸展树的插入与删除不必沿用 BST 的叶端操作，而是利用根部的树分裂与树合并。

伸展树里的 search 不是普通意义上的只读查询。成功时，它把命中的节点放到根；失败时，它把最后接近目标值的 _hot 节点放到根。这样一来，插入和删除都可以围绕根节点完成，避免“先一路走到底，再一路修回来”的双重路径成本。

插入重构（Split）： 传统插入需要查找到叶子后创建节点。由于 Splay::search() 已集成 splay()，若查找失败，_hot 节点（待插入位置的前驱或后继）已被提升至根部，此时可以在根附近接入新节点。以新节点 $v$ 为新根，将原树按大小关系从根部分裂为左子树 $L$ 和右子树 $R$ ，再将 $L$ 与 $R$ 分别作为 $v$ 的左右子树。

删除重构（Join）： 当 search(e) 命中时，目标节点被上浮到根。释放该节点后，原树分裂为左右两棵子树 $L$ 和 $R'$ 。随后执行合并：在 $L$ 中寻找最大值元素 $m$ ，该查找同样触发伸展，使 $m$ 成为 $L$ 的新根。由于 $m$ 是 $L$ 中最大者，它没有右子树，因此可直接将 $R'$ 挂接为 $m$ 的右孩子。

Split/Join 的安全性仍然来自二叉搜索树的大小边界。插入时，新节点左边的整棵树都小于它，右边的整棵树都大于它；删除时，左树最大节点 $m$ 被伸展为左树根后没有右孩子，因此把原右树挂到 $m$ 的右侧不会破坏中序顺序。

复杂度分析

为进行分摊分析，给树中每个节点 $x$ 赋予权重 $w(x)$ （通常为 1），并定义：

大小函数 $s(x)$ ：表示以 $x$ 为根的整棵子树中所有节点权重的总和。
秩函数 $r(x)$ ：定义为大小的对数，即 $r(x) = \log_2(s(x))$ 。
系统总势能 $\Phi$ ：全树所有节点秩的总和 $\Phi = \sum_{x \in T} r(x)$ 。

势能 $\Phi$ 是分摊分析中的辅助函数。对于高度不平衡的退化树，向下移动时 $s(x)$ 下降较慢，总势能较高；对于平衡树，各节点的 $s(x)$ 下降较快，总势能较低。一次树操作的分摊成本 $a_i$ 定义为实际时间开销 $t$ 加上势能变化量 $\Delta\Phi$ 。若旋转使树更平衡，势能下降可以抵消部分实际开销；反之则增加分摊成本。

设单次旋转的实际时间为 1。分析每一次 splay step（令旋转后的秩为 $r'$ ）：

对于 zig 步骤，由于仅 $p$ 和 $x$ 的秩改变，其分摊成本被放缩并绑定为 $a_i \le 3(r'(x) - r(x)) + 1$ 。
对于 zig-zig 步骤，涉及到 $g, p, x$ 三者的变化，通过放缩推导（利用 $x$ 和 $g$ 秩的置换以及对数函数的凸性），其分摊成本可绑定为： $a_i \le 3(r'(x) - r(x))$ （注意这里去掉了 $+1$ ）。

将一次完整伸展操作中的所有步骤相加时，中间节点的 $r(x)$ 项相互抵消，得到：

$Cost_{splay} \le 3(r'(root) - r_{initial}(x)) + 1$

由于叶子节点秩至少为 0，整棵树根的秩为 $\log_2(n)$ ，单次伸展操作的分摊耗时不超过 $3 \log_2 n + 1$ ，因此伸展树具有 $\mathcal{O}(\log n)$ 分摊时间复杂度。