顺序统计树

概述

顺序统计树（Order-Statistic Tree）是在 红黑树 上添加 size 属性的扩张数据结构，支持 $O(\lg n)$ 时间的 OS-SELECT（按秩查找元素）和 OS-RANK（求元素秩）操作。它解决了在动态集合中高效查找”第 $i$ 小元素”以及”某元素是第几小”的问题，是 数据结构扩张 最经典的应用之一。

定义

顺序统计树

顺序统计树是一棵红黑树，其中每个节点 $x$ 除红黑树的标准属性外，还额外维护一个域 $x.\text{size}$，定义为： $x.\text{size}=\text{以 }x\text{ 为根的子树中的节点总数（含 }x\text{ 本身）}$

递归地： $x.\text{size}=x.\text{left}.\text{size}+x.\text{right}.\text{size}+1$

其中，哨兵节点 $\text{nil}[T]$ 的 $\text{size}$ 为 $0$。

size 属性的直观理解

对于一棵顺序统计树中的任意节点 $x$：

• $x.\text{size}=1$：$x$ 是叶子节点（左右子树为空）
• $x.\text{size}=x.\text{left}.\text{size}+1$：$x$ 只有左子树
• $x.\text{size}=x.\text{right}.\text{size}+1$：$x$ 只有右子树

生活化类比

想象一排按身高从矮到高站好的学生（这就是红黑树的中序遍历）。每个学生手里举着一块牌子，上面写着”以我为组长的小组一共有多少人”——这个人数就是 size。组长左边的人数就是左子树的 size，右边的人数就是右子树的 size。

如果你想知道”第5矮的学生是谁”，不需要从头数到第5个——你只需要看中间（根节点）组长的牌子：

• 如果组长左边有4个人，那组长就是第5矮的
• 如果组长左边有6个人，那第5矮的在左边那组里
• 如果组长左边只有3个人，那第5矮的在右边那组里，而且要找的是右组的”第1矮”（5 - 3 - 1 = 1）

核心性质

性质1：size 的维护开销为 O(1)

在红黑树的旋转操作中，只有两个节点的 size 需要更新，且每个更新仅需 $O(1)$ 时间。在插入和删除操作中，size 的维护被吸收到原有的 $O(\lg n)$ 复杂度中。

性质2：OS-SELECT 的时间复杂度为 O(lg n)

OS-SELECT 从根节点出发，每层仅访问一个节点，因此最多访问 $\lg n$ 个节点，时间复杂度为 $O(\lg n)$。

性质3：OS-RANK 的时间复杂度为 O(lg n)

OS-RANK 从目标节点出发，沿根的路径向上遍历，每层仅做 $O(1)$ 计算，因此时间复杂度为 $O(\lg n)$。

性质4：保持红黑树的所有性质

顺序统计树仍然是合法的红黑树，所有红黑树的基本操作（SEARCH、INSERT、DELETE、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR）的时间复杂度不变。

OS-SELECT 操作

OS-SELECT$(x,i)$：在以 $x$ 为根的子树中，找到第 $i$ 小的元素（即中序遍历中的第 $i$ 个元素）。

OS-SELECT(x, i)
1  r = x.left.size + 1          // x 的秩（以 x 为根的子树中）
2  if i == r
3      return x                  // x 就是第 i 小的元素
4  elseif i < r
5      return OS-SELECT(x.left, i)   // 在左子树中找第 i 小
6  else
7      return OS-SELECT(x.right, i - r)  // 在右子树中找第 (i-r) 小

执行逻辑详解

1. 计算当前节点的秩：$r=x.\text{left}.\text{size}+1$，表示在以 $x$ 为根的子树中，$x$ 是第 $r$ 小的元素。
2. 比较与递归：
   • 若 $i=r$，则 $x$ 就是答案，直接返回。
   • 若 $i<r$，则第 $i$ 小的元素在左子树中，递归到左子树继续查找第 $i$ 小。
   • 若 $i>r$，则第 $i$ 小的元素在右子树中。由于左子树和 $x$ 本身共占 $r$ 个位置，所以在右子树中需要找的是第 $i-r$ 小的元素。

示例演示

考虑以下顺序统计树（节点格式为 key[size]）：

        15[7]
       /      \
    6[3]      18[3]
    / \       / \
  3[1] 7[1] 17[1] 20[1]

查找第 4 小的元素：OS-SELECT(root, 4)

步骤	当前节点 $x$	$r=x.\text{left}.\text{size}+1$	比较	动作
1	15[7]	$3+1=4$	$i=4=r$	返回 15

查找第 2 小的元素：OS-SELECT(root, 2)

步骤	当前节点 $x$	$r$	比较	动作
1	15[7]	4	$2<4$	递归到左子树，$i=2$
2	6[3]	2	$2=2$	返回 6

查找第 6 小的元素：OS-SELECT(root, 6)

步骤	当前节点 $x$	$r$	比较	动作
1	15[7]	4	$6>4$	递归到右子树，$i=6-4=2$
2	18[3]	2	$2=2$	返回 18

OS-RANK 操作

OS-RANK$(T,x)$：求节点 $x$ 在整棵树 $T$ 的中序遍历中的秩（即 $x$ 是第几小的元素）。

OS-RANK(T, x)
1  r = x.left.size + 1          // x 在以 x 为根的子树中的秩
2  y = x                         // 从 x 开始，沿路径向上遍历
3  while y != T.root
4      if y == y.p.right         // 如果 y 是右孩子
5          r = r + y.p.left.size + 1  // 加上父节点及其左子树的大小
6      y = y.p                   // 继续向上
7  return r

执行逻辑详解

1. 初始化：$r=x.\text{left}.\text{size}+1$，这是 $x$ 在以 $x$ 为根的子树中的秩。
2. 向上遍历：从 $x$ 出发，沿着到根的路径向上走。每经过一个节点 $y$：
   • 如果 $y$ 是其父节点的右孩子，说明父节点及其整个左子树中的所有元素都排在 $x$ 前面，因此需要将 $y.p.\text{left}.\text{size}+1$ 加到 $r$ 上。
   • 如果 $y$ 是其父节点的左孩子，则不需要额外操作（父节点及右子树的元素都排在 $x$ 后面）。
3. 返回结果：遍历到根节点后，$r$ 就是 $x$ 在整棵树中的秩。

示例演示

使用上面的同一棵树，求节点 18 的秩：OS-RANK$(T,18)$

步骤	当前 $y$	$y$ 是右孩子？	$r$ 的更新	$r$ 的值
初始	18	—	$r=0+1=1$	1
1	18	是（15的右孩子）	$r=1+3+1=5$	5
2	15	否（根节点，循环结束）	—	5

所以节点 18 是第 5 小的元素。验证：中序遍历为 3, 6, 7, 15, 17, 18, 20，18 确实排在第 5 位。

size 的维护

旋转操作中的维护

在左旋和右旋中，只有两个节点的 size 需要更新：

LEFT-ROTATE(T, x)
  ...
  // 标准左旋操作完成后，更新 size
  y.size = x.size
  x.size = x.left.size + x.right.size + 1

右旋类似，交换 $x$ 和 $y$ 的角色。

插入操作中的维护

在红黑树的插入过程中，从新插入的节点沿路径向上回溯，对路径上的每个节点执行：

$x.\text{size}=x.\text{left}.\text{size}+x.\text{right}.\text{size}+1$

由于路径长度为 $O(\lg n)$，每个更新为 $O(1)$，总开销为 $O(\lg n)$，被吸收到插入的 $O(\lg n)$ 复杂度中。

删除操作中的维护

在红黑树的删除过程中，从实际被删除节点的位置沿路径向上回溯，更新路径上每个节点的 size，同样为 $O(\lg n)$。

参见

• 红黑树 — 顺序统计树的基础数据结构
• 数据结构扩张 — 顺序统计树是数据结构扩张的典型案例
• 数据结构扩张四步法 — 系统化推导顺序统计树的四步方法论
• 红黑树扩张定理 — 保证 size 属性在旋转后可 $O(1)$ 维护的理论基础
• 区间树 — 红黑树扩张的另一经典案例