搜索树增强定理与方法

局部条件

若每个节点满足

a(x)=F(key(x),a(left(x)),a(right(x))),

且 $F$ 可在 $O(1)$ 计算，一次 BST 旋转只改变常数个节点的子树组成，按自底向上重算即可恢复不变量；插删沿搜索路径更新，额外成本与树高同阶。

摘要若位于幺半群 $(M,\circ,e)$ ，可取 $a(x)=a(L)\circ value(x)\circ a(R)$ ，统一处理计数、和、最值。可结合不提供逆元；删除仍靠重新合并孩子摘要。

维护 $size(x)=1+size(L)+size(R)$ 后，第 $k$ 小查询比较 $k$ 与左子树大小，沿根叶路径完成。区间树维护子树最大高端点，可剪枝寻找重叠区间。

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

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

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

插入叶 $z$ 后，从 $z$ 向根重算摘要；平衡修复若旋转，再只重算旋转涉及节点。左旋旧根 $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\to4\to5$ 的 size 依次增加；若平衡树旋转 4、5，按局部公式重算后根的总 size 仍为 8。这提供可执行测试，而不只是查询公式。

子树和、最大值、哈希摘要由孩子常数合并，符合定理；绝对深度、全树中节点的全局排名依祖先上下文，一次旋转可改变线性多个值。可以改存相对偏移或使用 lazy tag，但那是新不变量，不能说原字段天然局部。

参考资料