顺序统计树 | Codeboy's Blog

形式陈述

顺序统计树通常以平衡搜索树为骨架，再在每个节点维护子树大小。平衡保证高度，大小字段把按键查找扩展为 select 与 rank。

增强不变量

每个节点 $x$ 保存

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

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

Select 与 Rank

本节先用每个节点保存一个互异键的约定。Select $(x,k)$ 要求 $1\le k\le\operatorname{size}(x)$ ，空树或越界秩按接口报告失败。令 $r=\operatorname{size}(x.left)+1$ ； $k=r$ 时返回 $x$ ， $k<r$ 时向左，否则以 $k-r$ 向右。Rank $(x)$ 先把累计值置为 $\operatorname{size}(x.left)+1$ ，再从节点向根走：每当从某父的右子树上升，就加上父左子树大小与父本身。平衡树高度为 $O(\log n)$ ，所以查询与更新均为 $O(\log n)$ 最坏时间、空间 $O(n)$ 。

直觉

子树大小把搜索树的分叉同时变成秩空间的分叉：左子树贡献多少个更小元素，便决定当前节点的一基秩。Select 按目标秩向下扣除整棵子树，Rank 则沿祖先链把从右侧越过的左子树整批累加。

例子与边界

动态中位数例子

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

语义边界

静态选择问题可在无序数组上线性求第 $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., MIT Press, 2022, Augmenting Data Structures.
Robert Tarjan, Data Structures and Network Algorithms, SIAM, 1983.

形式陈述 ​

增强不变量 ​

Select 与 Rank ​

动态中位数例子 ​

语义边界 ​

删除与旋转核对 ​

更新路径的核对方法 ​