顺序统计树

增强不变量 ​

每个节点 $x$ 保存

$$\mathrm{size}(x)=\mathrm{size}(x.left)+\mathrm{size}(x.right)+1,$$

空子树大小为零。插入、删除沿祖先链更新；一次旋转只改变常数个节点的孩子关系，先更新下沉节点、再更新上升节点即可恢复不变量。

Select 与 Rank ​

令 $r=\mathrm{size}(x.left)+1$。Select$(x,k)$ 在 $k=r$ 时返回 $x$，$k<r$ 向左，否则以 $k-r$ 向右。Rank$(x)$ 从节点向根走：每当从某父的右子树上升，就加上父左子树大小与父本身。平衡树高度为 $O(\log n)$，所以查询与更新均为 $O(\log n)$ 最坏时间、空间 $O(n)$。

动态中位数例子 ​

持续插入订单价格后，中位数是 Select$(root,\lceil n/2\rceil )$；删除撤单后字段沿路径修复，无需重新排序全部价格。若相同价格出现多次，可在节点保存 multiplicity，并让 size 统计总出现次数；若需要区分订单身份，则用 $(price,id)$ 作为稳定键。

语义边界 ​

静态选择问题公理库顺序统计量Order statistic有限有序样本排序后第 k 个位置的元素。可在无序数组上线性求第 $k$ 小，本结构付出树空间来支持动态序列。rank 必须说明是小于键的元素数、节点的一基秩还是多重集秩。若把 size 换成权重和，就得到按累计权重选择，但查询条件和旋转更新也要同步改写。

删除与旋转核对 ​

BST 删除若用后继键替换目标，再物理删除后继节点，size 应沿真正被移除节点到根的路径递减；只沿最初搜索路径更新会在后继较深时留下错误字段。红黑树修复中的每次旋转都要先保存旧子树关系，再按孩子重算两个受影响节点。

可用局部断言审计实现：每个节点随时满足 size 方程，根 size 等于集合总 multiplicity；Select$(root,Rank(x))$ 应返回同一稳定节点。它们比只测试最终中位数更容易定位更新错误。

更新路径的核对方法 ​

插入键 13 后，先沿搜索路径把祖先 size 各加一，再执行平衡修复。若一次左旋以 $x$ 为轴、$y=x.right$，旋转后先令 $x.size$ 由新左右孩子计算，再令 $y.size$ 由 $x$ 与原右子树计算；顺序反过来会读取尚未更新的 $x.size$。

删除含两个孩子的节点时，若实现把后继记录搬到目标节点而实际删除后继位置，应该只在后继到根的结构路径上减计数；若交换整节点，则两条路径和旋转都要核对。重复键可以“每次出现一节点”，也可以在节点内存 multiplicity；后一种定义下

$$size(v)=size(v.left)+count(v)+size(v.right),$$

Rank 与 Select 的跨根偏移也必须使用 count(v) 而不是 1。

参考资料

• Cormen et al., Introduction to Algorithms, 4th ed., Augmenting Data Structures.
• Robert Tarjan, Data Structures and Network Algorithms, SIAM, 1983.