拓冰网站定制 
文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载导读本篇文章以《算法导论》第 14 章 14.1 节动态顺序统计为核心结合本仓库 C14-Augmenting-Data-Structures 下的习题解答与 C13-Red-Black-Trees/rbtree.cpp 的红黑树实现系统讲解如何在红黑树节点中增广size字段实现 O(lg n) 的按名次选择OS-SELECT、名次查询OS-RANK以及一系列衍生操作。读完本文你将掌握顺序统计树的基本原理、非递归与递归的伪代码实现、size/rank字段在插入删除旋转中的维护方式并能够把该数据结构直接用于逆序对计数、圆上弦相交计数等经典问题。一、动态顺序统计问题的背景在普通的二叉搜索树BST或红黑树中我们只能按键值进行查找无法回答集合中第 i 小的元素是谁这类问题。顺序统计树order-statistic tree的核心思想是在红黑树的每个节点上额外维护一个size字段表示以该节点为根的子树中节点的个数包含自身。只要保证size能在红黑树的插入、删除、旋转过程中以 O(lg n) 的时间增量维护就可以支持两个新操作OS-SELECT(x, i)返回以 x 为根的子树中第 i 小的元素O(lg n)OS-RANK(T, x)返回元素 x 在中序遍历线性序中的名次O(lg n)。这正是《算法导论》第 14 章增广数据结构Augmenting Data Structures的核心案例对应本仓库文档 C14-Augmenting-Data-Structures/14.1.md。红黑树本身的实现可参见 C13-Red-Black-Trees/rbtree.cpp模板类RedBlackTree包含left_rotate、right_rotate、rb_insert_fixup、rb_delete_fixup等完整操作增广字段正是在该基础上叠加的。二、OS-SELECT按名次选择元素2.1 递归版CLRS 原始版本OS-SELECT的输入是一个节点 x 和名次 i1 ≤ i ≤ x.size。它的思路是先计算节点 x 在其子树中的名次r size[left[x]] 1然后与目标名次 i 比较OS-SELECT(x, i) r size[left[x]] 1 if i r return x elseif i r return OS-SELECT(left[x], i) else return OS-SELECT(right[x], i - r)若i rx 本身就是第 i 小的元素若i r第 i 小的元素在左子树中名次不变若i r第 i 小的元素在右子树中需要把名次减去 r。由于每递归一层就下降一层而红黑树高度为 O(lg n)所以总时间为 O(lg n)。2.2 非递归版Exercises 14.1-314.1-3 要求写出非递归版本。用循环替代尾递归即可思路完全一致OS-SELECT(x, i) while x ! null r size[left[x]] 1 if i r return x elseif i r x left[x] else x right[x] i i - r这一版本避免了递归调用栈开销在嵌入式或高性能场景下更友好且对树的形状没有任何额外要求。2.3 在红黑树上的落地实现仓库中 C13-Red-Black-Trees/rbtree.cpp 提供了标准的红黑树模板类其中每个节点结构为template class T class RedBlackTreeNode { public: T key; RedBlackTreeNodeT* parent; RedBlackTreeNodeT* left; RedBlackTreeNodeT* right; int color; };实现 OS-SELECT 时只需在此基础上增加int size;字段并在left_rotate/right_rotate中同步更新。从源码结构看旋转操作只需更新受影响的局部节点旋转只涉及 x 和 y 两个节点的子树信息这正是《算法导论》定理 14.1 所保证的 O(lg n) 可维护性。三、OS-RANK查询元素名次OS-RANK(T, x)返回 x 在中序遍历序列中的名次。基本过程是从 x 出发向上回溯累加所有小于 x 的节点数OS-RANK(T, x) r size[left[x]] 1 y x while y ! root[T] if y right[parent[y]] r r size[left[parent[y]]] 1 y parent[y] return r初值size[left[x]] 1是 x 在其所在子树中的名次每当 y 是父节点的右孩子时说明父节点及其左子树整体都小于 x需要把size[left[parent[y]]] 1累加进 r。由于从 x 到根只有 O(lg n) 步总时间为 O(lg n)。3.1 按键值求名次OS-KEY-RANKExercises 14.1-4如果给定的是键值 k 而非节点 x且假设树中键互不相同可以用递归方式沿搜索路径下探同时累加名次OS-KEY-RANK(T, k) r size[left[T]] 1 if k key[T] return r elseif key[T] k return OS-KEY-RANK(left[T], k) else return r OS-KEY-RANK(right[T], k)注意向右子树递归时当前节点的名次 r 必须累加进结果因为右子树中的节点都排在当前节点之后。时间复杂度同样是 O(lg n)。四、利用 OS-SELECT 与 OS-RANK 实现衍生操作4.1 求第 i 个后继Exercises 14.1-5给定节点 x 和自然数 i要求 x 在线性序中的第 i 个后继。直接组合两个基本操作即可I-SUCCESSOR(x, i) y OS-RANK(T, x) // 先求 x 的名次 r OS-SELECT(T, y i) // 再选择名次为 yi 的节点 return r两步各为 O(lg n)合计 O(lg n)。当 i 1 时这就是普通的 SUCCESSOR 操作。该结论在 14.1.md 的 14.1-5 答案中给出后续 14.2-5 的RB-ENUMERATE也依赖连续调用 m 次后继总代价 O(m lg n)这一性质。4.2 用顺序统计树求逆序对Exercises 14.1-7问题 2-4 定义数组 A[1..n] 中若 i j 且 A[i] A[j]则 (i, j) 是一对逆序。用顺序统计树可以在 O(n lg n) 内计数。关键观察红黑树建树本身就需要 O(n lg n)因此必须边建树边统计。对每个元素 A[j]先执行OS-RANK(T, A[j])得到当前树中小于等于 A[j] 的元素个数已经插入的 j−1 个元素中大于 A[j] 的数量 (j − 1) − rank这些恰好是与 A[j] 构成逆序的对数累加后把 A[j] 插入树中。每次 INSERT 与 RANK 均为 O(lg n)n 个元素合计 O(n lg n)。相比 O(n²) 的朴素双重循环这是典型的数据结构增广收益。仓库 C02-Getting-Started/exercise_code/inversions.cpp 与 C02-Getting-Started/exercise_code/inversions.py 给出了基于归并排序的逆序对计数实现与顺序统计树方案互为印证两者都达到 O(n lg n)但前者属于分治思路后者则展示了边插入边 RANK的在线处理能力。4.3 圆上弦相交计数Exercises 14.1-8题目n 条弦的 2n 个端点在圆上任意两条弦不共享端点求圆内相交的弦对数要求 O(n lg n)。思路是事件点 顺序统计树的扫描法把 2n 个端点按角度逆时针排序O(n lg n)遍历端点遇到某条弦 X 的第一个端点起点把 X 以起点角度为 key 插入顺序统计树遇到第二个端点终点统计树中起点角度比 X 起点角度大的弦的数量——这些弦必然与 X 相交——然后删除 X。对顺序统计树而言统计起点角度大于某值只需一次 OS-RANK 变形O(lg n)插入与删除各 O(lg n)因此总复杂度 O(n lg n)。该算法的伪代码与解释完整保留在 14.1.md 的 14.1-8 答案中。五、size 与 rank 字段的维护Exercises 14.1-65.1 为什么 size 容易维护而 rank 困难观察 OS-SELECT 与 OS-RANKsize字段只用于计算节点在其子树中的名次。那么一个自然的想法是直接在每个节点中存储它在子树中的 rank省去运行时计算。14.1-6 的结论是维护 rank 字段代价高昂效率很低。插入时需要遍历所有节点根据节点值与插入值的大小把相关节点的 rank 分别加 1 或减 1代价是 O(n)删除时同样需要遍历所有节点更新 rank代价 O(n)唯一的好消息是旋转操作不改变 rank 的相对值因此旋转不影响 rank 字段。相比之下size字段只需在插入/删除路径上的 O(lg n) 个节点以及旋转涉及的局部节点上更新这就是增广数据结构选 size 而不选 rank 的根本原因。5.2 旋转时如何 O(1) 更新红黑树的左旋/右旋只涉及两个节点 x 和 y以及它们的子树。以左旋y 是 x 的右孩子为例LEFT-ROTATE(T, x) y right[x] right[x] left[y] left[y] x size[y] size[x] size[x] size[left[x]] size[right[x]] 1旋转后 y 取代 x 的位置所以size[y]直接继承原size[x]x 的左右孩子不变只需重新累加。整个更新是 O(1) 的这正是定理 14.1第 309 页所要求的条件红黑树上的插入、删除、旋转均可在 O(lg n) 总时间内维持增广字段。六、从 14.1 到 14.3增广数据结构的完整图景14.1 节建立的选择字段 → 在 O(lg n) 内维护 → 派生新操作方法论在本仓库的后续章节中一以贯之14.2.mdMINIMUM/MAXIMUM/SUCCESSOR/PREDECESSOR 的 O(1) 支持加指针字段、黑高度字段维护、结合算子 f 的 O(1) 旋转更新以及RB-ENUMERATE的 Θ(m lg n) 区间枚举14.3.md区间树interval tree——在红黑树上维护max字段子树中区间 high 的最大值实现INTERVAL-SEARCH、MIN-INTERVAL-SEARCH、INTERVAL-SEARCH-EXACTLY以及 MIN-GAP 等操作problem.md最大重叠点问题端点 1/−1 增广与约瑟夫排列问题。其中约瑟夫问题 (b) 明确给出基于顺序统计树的 O(n lg n) 算法先把 1..n 插入 OST每轮用j ← ((j m − 2) mod k) 1计算要移除的名次OS-SELECT选中后OS-DELETE。仓库配套实现 C14-Augmenting-Data-Structures/exercise_code/m-Josephus.cpp 给出了 m 为常数时用循环链表实现的 O(n) 版本问题 a两者恰好覆盖常数 m与非常数 m两种场景。这些内容共同构成《算法导论》第 14 章增广数据结构的完整方法论在红黑树等平衡树上附加可 O(1)/O(lg n) 维护的字段把经典集合操作第 13 章扩展为区间查询、顺序统计、几何扫描等高级能力。七、总结顺序统计树是增广数据结构最经典的入门案例本仓库 14.1.md 用 8 道习题覆盖了它的全部要点习题主题关键结论14.1-1 / 14.1-2OS-SELECT / OS-RANK 的跟踪执行沿路径下降/回溯O(lg n)14.1-3非递归 OS-SELECT循环替代尾递归14.1-4OS-KEY-RANK按键值递归求名次14.1-5第 i 个后继OS-RANK OS-SELECTO(lg n)14.1-6size 与 rank 的维护rank 需 O(n)size 只需 O(lg n)旋转不影响 rank14.1-7逆序对计数边插入边 RANKO(n lg n)14.1-8圆上弦相交计数事件点扫描 顺序统计树O(n lg n)掌握这些操作后你不仅能读懂红黑树源码rbtree.cpp并在其上叠加size字段还能把同一套增广方法论推广到区间树、最大重叠点等更复杂的数据结构设计中。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐终极对比指南红黑树与B树在CLRS中的实现与应用终极对比指南红黑树与B树在CLRS中的实现与应用 红黑树和B树都是算法导论CLRS中经典的 平衡搜索树 数据结构它们在数据库系统、文件系统和内存管理中发文档教程示例工程深入理解红黑树从基础到实践walkccc/CLRS项目解析深入理解红黑树从基础到实践walkccc/CLRS项目解析 引言为什么需要红黑树 在计算机科学领域数据结构的选择往往决定了算法的效率。二叉搜索树B文档教程教育Effect树结构红黑树与排序映射Effect树结构红黑树与排序映射 引言为什么需要有序数据结构 在现代软件开发中我们经常需要处理有序数据集合。无论是用户配置、缓存系统、实时排行榜还是后端异步编程依赖注入上一篇如何在Blender中无缝处理3D打印文件3MF插件完全指南下一篇Operit 断网中断 AI 输出保留修复重试失败消息收尾与尾部回滚渲染实战解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 CLRS 顺序统计树（Order-Statistic Tree）实战解析：OS-SELECT、OS-RANK 与增广红黑树
文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载导读本篇文章以《算法导论》第 14 章 14.1 节动态顺序统计为核心结合本仓库 C14-Augmenting-Data-Structures 下的习题解答与 C13-Red-Black-Trees/rbtree.cpp 的红黑树实现系统讲解如何在红黑树节点中增广size字段实现 O(lg n) 的按名次选择OS-SELECT、名次查询OS-RANK以及一系列衍生操作。读完本文你将掌握顺序统计树的基本原理、非递归与递归的伪代码实现、size/rank字段在插入删除旋转中的维护方式并能够把该数据结构直接用于逆序对计数、圆上弦相交计数等经典问题。一、动态顺序统计问题的背景在普通的二叉搜索树BST或红黑树中我们只能按键值进行查找无法回答集合中第 i 小的元素是谁这类问题。顺序统计树order-statistic tree的核心思想是在红黑树的每个节点上额外维护一个size字段表示以该节点为根的子树中节点的个数包含自身。只要保证size能在红黑树的插入、删除、旋转过程中以 O(lg n) 的时间增量维护就可以支持两个新操作OS-SELECT(x, i)返回以 x 为根的子树中第 i 小的元素O(lg n)OS-RANK(T, x)返回元素 x 在中序遍历线性序中的名次O(lg n)。这正是《算法导论》第 14 章增广数据结构Augmenting Data Structures的核心案例对应本仓库文档 C14-Augmenting-Data-Structures/14.1.md。红黑树本身的实现可参见 C13-Red-Black-Trees/rbtree.cpp模板类RedBlackTree包含left_rotate、right_rotate、rb_insert_fixup、rb_delete_fixup等完整操作增广字段正是在该基础上叠加的。二、OS-SELECT按名次选择元素2.1 递归版CLRS 原始版本OS-SELECT的输入是一个节点 x 和名次 i1 ≤ i ≤ x.size。它的思路是先计算节点 x 在其子树中的名次r size[left[x]] 1然后与目标名次 i 比较OS-SELECT(x, i) r size[left[x]] 1 if i r return x elseif i r return OS-SELECT(left[x], i) else return OS-SELECT(right[x], i - r)若i rx 本身就是第 i 小的元素若i r第 i 小的元素在左子树中名次不变若i r第 i 小的元素在右子树中需要把名次减去 r。由于每递归一层就下降一层而红黑树高度为 O(lg n)所以总时间为 O(lg n)。2.2 非递归版Exercises 14.1-314.1-3 要求写出非递归版本。用循环替代尾递归即可思路完全一致OS-SELECT(x, i) while x ! null r size[left[x]] 1 if i r return x elseif i r x left[x] else x right[x] i i - r这一版本避免了递归调用栈开销在嵌入式或高性能场景下更友好且对树的形状没有任何额外要求。2.3 在红黑树上的落地实现仓库中 C13-Red-Black-Trees/rbtree.cpp 提供了标准的红黑树模板类其中每个节点结构为template class T class RedBlackTreeNode { public: T key; RedBlackTreeNodeT* parent; RedBlackTreeNodeT* left; RedBlackTreeNodeT* right; int color; };实现 OS-SELECT 时只需在此基础上增加int size;字段并在left_rotate/right_rotate中同步更新。从源码结构看旋转操作只需更新受影响的局部节点旋转只涉及 x 和 y 两个节点的子树信息这正是《算法导论》定理 14.1 所保证的 O(lg n) 可维护性。三、OS-RANK查询元素名次OS-RANK(T, x)返回 x 在中序遍历序列中的名次。基本过程是从 x 出发向上回溯累加所有小于 x 的节点数OS-RANK(T, x) r size[left[x]] 1 y x while y ! root[T] if y right[parent[y]] r r size[left[parent[y]]] 1 y parent[y] return r初值size[left[x]] 1是 x 在其所在子树中的名次每当 y 是父节点的右孩子时说明父节点及其左子树整体都小于 x需要把size[left[parent[y]]] 1累加进 r。由于从 x 到根只有 O(lg n) 步总时间为 O(lg n)。3.1 按键值求名次OS-KEY-RANKExercises 14.1-4如果给定的是键值 k 而非节点 x且假设树中键互不相同可以用递归方式沿搜索路径下探同时累加名次OS-KEY-RANK(T, k) r size[left[T]] 1 if k key[T] return r elseif key[T] k return OS-KEY-RANK(left[T], k) else return r OS-KEY-RANK(right[T], k)注意向右子树递归时当前节点的名次 r 必须累加进结果因为右子树中的节点都排在当前节点之后。时间复杂度同样是 O(lg n)。四、利用 OS-SELECT 与 OS-RANK 实现衍生操作4.1 求第 i 个后继Exercises 14.1-5给定节点 x 和自然数 i要求 x 在线性序中的第 i 个后继。直接组合两个基本操作即可I-SUCCESSOR(x, i) y OS-RANK(T, x) // 先求 x 的名次 r OS-SELECT(T, y i) // 再选择名次为 yi 的节点 return r两步各为 O(lg n)合计 O(lg n)。当 i 1 时这就是普通的 SUCCESSOR 操作。该结论在 14.1.md 的 14.1-5 答案中给出后续 14.2-5 的RB-ENUMERATE也依赖连续调用 m 次后继总代价 O(m lg n)这一性质。4.2 用顺序统计树求逆序对Exercises 14.1-7问题 2-4 定义数组 A[1..n] 中若 i j 且 A[i] A[j]则 (i, j) 是一对逆序。用顺序统计树可以在 O(n lg n) 内计数。关键观察红黑树建树本身就需要 O(n lg n)因此必须边建树边统计。对每个元素 A[j]先执行OS-RANK(T, A[j])得到当前树中小于等于 A[j] 的元素个数已经插入的 j−1 个元素中大于 A[j] 的数量 (j − 1) − rank这些恰好是与 A[j] 构成逆序的对数累加后把 A[j] 插入树中。每次 INSERT 与 RANK 均为 O(lg n)n 个元素合计 O(n lg n)。相比 O(n²) 的朴素双重循环这是典型的数据结构增广收益。仓库 C02-Getting-Started/exercise_code/inversions.cpp 与 C02-Getting-Started/exercise_code/inversions.py 给出了基于归并排序的逆序对计数实现与顺序统计树方案互为印证两者都达到 O(n lg n)但前者属于分治思路后者则展示了边插入边 RANK的在线处理能力。4.3 圆上弦相交计数Exercises 14.1-8题目n 条弦的 2n 个端点在圆上任意两条弦不共享端点求圆内相交的弦对数要求 O(n lg n)。思路是事件点 顺序统计树的扫描法把 2n 个端点按角度逆时针排序O(n lg n)遍历端点遇到某条弦 X 的第一个端点起点把 X 以起点角度为 key 插入顺序统计树遇到第二个端点终点统计树中起点角度比 X 起点角度大的弦的数量——这些弦必然与 X 相交——然后删除 X。对顺序统计树而言统计起点角度大于某值只需一次 OS-RANK 变形O(lg n)插入与删除各 O(lg n)因此总复杂度 O(n lg n)。该算法的伪代码与解释完整保留在 14.1.md 的 14.1-8 答案中。五、size 与 rank 字段的维护Exercises 14.1-65.1 为什么 size 容易维护而 rank 困难观察 OS-SELECT 与 OS-RANKsize字段只用于计算节点在其子树中的名次。那么一个自然的想法是直接在每个节点中存储它在子树中的 rank省去运行时计算。14.1-6 的结论是维护 rank 字段代价高昂效率很低。插入时需要遍历所有节点根据节点值与插入值的大小把相关节点的 rank 分别加 1 或减 1代价是 O(n)删除时同样需要遍历所有节点更新 rank代价 O(n)唯一的好消息是旋转操作不改变 rank 的相对值因此旋转不影响 rank 字段。相比之下size字段只需在插入/删除路径上的 O(lg n) 个节点以及旋转涉及的局部节点上更新这就是增广数据结构选 size 而不选 rank 的根本原因。5.2 旋转时如何 O(1) 更新红黑树的左旋/右旋只涉及两个节点 x 和 y以及它们的子树。以左旋y 是 x 的右孩子为例LEFT-ROTATE(T, x) y right[x] right[x] left[y] left[y] x size[y] size[x] size[x] size[left[x]] size[right[x]] 1旋转后 y 取代 x 的位置所以size[y]直接继承原size[x]x 的左右孩子不变只需重新累加。整个更新是 O(1) 的这正是定理 14.1第 309 页所要求的条件红黑树上的插入、删除、旋转均可在 O(lg n) 总时间内维持增广字段。六、从 14.1 到 14.3增广数据结构的完整图景14.1 节建立的选择字段 → 在 O(lg n) 内维护 → 派生新操作方法论在本仓库的后续章节中一以贯之14.2.mdMINIMUM/MAXIMUM/SUCCESSOR/PREDECESSOR 的 O(1) 支持加指针字段、黑高度字段维护、结合算子 f 的 O(1) 旋转更新以及RB-ENUMERATE的 Θ(m lg n) 区间枚举14.3.md区间树interval tree——在红黑树上维护max字段子树中区间 high 的最大值实现INTERVAL-SEARCH、MIN-INTERVAL-SEARCH、INTERVAL-SEARCH-EXACTLY以及 MIN-GAP 等操作problem.md最大重叠点问题端点 1/−1 增广与约瑟夫排列问题。其中约瑟夫问题 (b) 明确给出基于顺序统计树的 O(n lg n) 算法先把 1..n 插入 OST每轮用j ← ((j m − 2) mod k) 1计算要移除的名次OS-SELECT选中后OS-DELETE。仓库配套实现 C14-Augmenting-Data-Structures/exercise_code/m-Josephus.cpp 给出了 m 为常数时用循环链表实现的 O(n) 版本问题 a两者恰好覆盖常数 m与非常数 m两种场景。这些内容共同构成《算法导论》第 14 章增广数据结构的完整方法论在红黑树等平衡树上附加可 O(1)/O(lg n) 维护的字段把经典集合操作第 13 章扩展为区间查询、顺序统计、几何扫描等高级能力。七、总结顺序统计树是增广数据结构最经典的入门案例本仓库 14.1.md 用 8 道习题覆盖了它的全部要点习题主题关键结论14.1-1 / 14.1-2OS-SELECT / OS-RANK 的跟踪执行沿路径下降/回溯O(lg n)14.1-3非递归 OS-SELECT循环替代尾递归14.1-4OS-KEY-RANK按键值递归求名次14.1-5第 i 个后继OS-RANK OS-SELECTO(lg n)14.1-6size 与 rank 的维护rank 需 O(n)size 只需 O(lg n)旋转不影响 rank14.1-7逆序对计数边插入边 RANKO(n lg n)14.1-8圆上弦相交计数事件点扫描 顺序统计树O(n lg n)掌握这些操作后你不仅能读懂红黑树源码rbtree.cpp并在其上叠加size字段还能把同一套增广方法论推广到区间树、最大重叠点等更复杂的数据结构设计中。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐终极对比指南红黑树与B树在CLRS中的实现与应用终极对比指南红黑树与B树在CLRS中的实现与应用 红黑树和B树都是算法导论CLRS中经典的 平衡搜索树 数据结构它们在数据库系统、文件系统和内存管理中发文档教程示例工程深入理解红黑树从基础到实践walkccc/CLRS项目解析深入理解红黑树从基础到实践walkccc/CLRS项目解析 引言为什么需要红黑树 在计算机科学领域数据结构的选择往往决定了算法的效率。二叉搜索树B文档教程教育Effect树结构红黑树与排序映射Effect树结构红黑树与排序映射 引言为什么需要有序数据结构 在现代软件开发中我们经常需要处理有序数据集合。无论是用户配置、缓存系统、实时排行榜还是后端异步编程依赖注入上一篇如何在Blender中无缝处理3D打印文件3MF插件完全指南下一篇Operit 断网中断 AI 输出保留修复重试失败消息收尾与尾部回滚渲染实战解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考