搜索树增强定理与方法

局部公式让我们知道下一层摘要怎样重算；整段摘要是否保持不变，决定更新能否就此停止。子树元素数不随旋转改变，所以两节点修复足够；子树高度虽然也由孩子常数合并，却可能在旋转后改变，必须继续向祖先传播。依赖祖先上下文的绝对深度则更麻烦，子树内部许多节点都可能改变。

真例与反例 ​

维护 $size(x)=1+size(L)+size(R)$ 后，顺序统计树理路顺序统计树order-statistic tree · dynamic order statistics在平衡搜索树中维护子树大小，动态支持按秩选择与键的秩查询。的第 $k$ 小查询比较 $k$ 与左子树大小，沿根叶路径完成。区间树理路区间树Interval tree · Centered interval tree按中心点递归分配区间，用两套端点次序实现静态点刺与交叠报告，并区分固定坐标骨架的动态成本。维护子树最大高端点，可剪枝寻找重叠区间。

例如子树 $2\to 4\to 6$ 是一条右链，高度为 $2$；在 $2$ 左旋后，以 $4$ 为根、孩子为 $2,6$，高度降到 $1$。若这棵子树挂在键 $8$ 的左侧，而 $8$ 的右孩子为叶 $10$，祖先 $8$ 的高度也从 $3$ 降到 $2$。这直接反驳“任意常数合并摘要都只需重算旋转两点”。

节点深度不是这种子树摘要：一次根旋转改变整棵子树内许多节点的深度，更新常数节点无法恢复。依赖全局中序编号的字段也须改写为相对可组合量。

正确性清单 ​

须分别验证空孩子的单位元、重复键约定、插入路径、每种旋转、删除替换与查询循环不变量。查询公式正确不代表维护过程正确，旋转次数和报告型查询的输出量也要计入总成本。

可执行检查可在每次修改后递归重算一份慢摘要，与节点缓存值逐项比较；它适合测试维护代码，但生产算法的复杂度仍来自局部更新证明。

插入、旋转与删除的维护次序 ​

插入叶 $z$ 后，从 $z$ 向根重算摘要。对不随旋转改变整段值的中序聚合，平衡修复每次旋转只补算局部两点；对高度等形状摘要，要将变化沿祖先路径传播。要证明整个更新仍为 $O(h)$，还须核对平衡算法的修复次序，避免每次旋转后都重复完整回溯。左旋旧根 $x$、右孩子 $y$ 时，$x$ 先接收 $y$ 的左子树，所以先重算 $a(x)$；$y$ 再以新 $x$ 为左子，后重算 $a(y)$。这一依赖顺序是实现不变量的一部分。

删除有两种身份：逻辑上删除键 $z$，物理上可能移除其后继 $y$。若把 $y$ 的键复制到 $z$，键相关摘要从 $z$ 起也需更新；物理路径则从 $y$ 的旧父亲向上缩减。只沿搜索 $z$ 的路径减 size 会在有两个孩子时产生错误计数。

顺序统计实例全程 ​

树中序键为 $(2,4,5,8,10,12,15)$，根 8 的左 size=3。Select$(5)$ 跳过左侧三项与根，进入右子树找第 1 小，得到 10。Rank$(12)$ 从根累计左 size+1=4，向右；在 12 处再加其左 size+1=2，得到秩 6。两个过程都只走树高。

插入 6 后，路径 $8\to 4\to 5$ 的 size 依次增加；若平衡树旋转 4、5，按局部公式重算后根的总 size 仍为 8。这提供可执行测试，而不只是查询公式。

可增强与不可增强的判据 ​

子树和、最大值和同时保存长度与幂因子的定长滚动哈希可以作中序聚合，符合上述旋转不变条件；普通结构哈希会随树形变化，应继续更新祖先。绝对深度、全树中节点的全局排名依祖先上下文，一次旋转可改变线性多个值。可以改存相对偏移或使用 lazy tag，但那是新不变量，不能说原字段天然局部。