06-02-排序集合-SortedSet-T-红黑树实现与不变式

SortedSetT红黑树实现、不变式与版本边界系列C# 与常用数据结构源码剖析 · 排序集合篇阅读时间约 75 分钟源码基线.NET 8.0.0dotnet/runtime的System.Private.CoreLib/src/System/Collections/Generic/SortedSet.cs前置知识06-01红黑树性质与旋转阅读约定字段与行为按上述 tag 讨论本文代码是结构化节选或教学伪代码不冒充逐字源码。内部命名和优化路径可能随版本变化。一、SortedSet 解决的不是“自动排序”这么简单SortedSetT同时维护两个契约集合中不存在由比较器判定为相等的重复项枚举结果始终按同一个比较器排序。它的典型实现是红黑树因此查找、插入、删除和边界定位在最坏情况下都是 O(log n)不会像未经平衡的二叉搜索树那样因有序输入退化为链表。这里的“相等”不是固定调用Equals。设比较器为C若C.Compare(x, y) 0集合就把 x 与 y 视作同一个等价类即使x.Equals(y)返回 false。这个事实贯穿 Add、Contains、Remove、集合运算和范围视图也是生产事故最常见来源之一。红黑树通过颜色和旋转限制树高。可以把它理解为 2-3-4 树的一种二叉编码黑节点与相邻红孩子共同表示多关键字节点。.NET 8的插入和删除实现大量使用“2-node”“4-node”这套视角在向下搜索时预先拆分或合并节点。它不是旧稿描述的“把整条路径压入StackNode插完再统一向上修复”。二、对象字段、Node 与内存模型基线实现的核心状态可以结构化为// 结构化节选省略接口、序列化兼容和辅助成员。 private Node? _root; private IComparerT _comparer; private int _count; private int _version; internal sealed class Node { internal T Item; internal Node? Left; internal Node? Right; internal NodeColor Color; }节点不保存 Parent。插入的下降过程用parent、grandParent、greatGrandParent等局部引用维持旋转所需上下文删除同样在下降时保存有限祖先。枚举器则需要自己的节点栈以便不修改树就按中序遍历。不能由“Node 无 Parent”推导“所有操作都用StackNode”。不应给 Node 写死“28 字节”或“每项比 HashSet 多 12 字节”。对象头、引用大小、字段重排与对齐取决于运行时、架构和配置T若为值类型还会内联进节点大小也不固定。可以确定的是每个元素通常对应一个独立 Node 对象节点含两个子引用和颜色相比数组式条目这会增加对象数量、指针追踪和间接访问。_comparer在构造后定义整棵树的秩序不能中途替换。未传入比较器时使用ComparerT.Default这要求 T 有可用的默认比较关系否则比较发生时会失败。比较器还必须对集合生命周期内的元素表现为稳定、确定的全序关系至少满足反对称、传递和一致的零等价关系。三、必须始终成立的三层不变量3.1 二叉搜索树不变量对任意节点 n左子树中每个元素都严格小于n.Item右子树中每个元素都严格大于n.Item大小关系由_comparer定义。由于比较为 0 的第二个元素不会插入所以不存在同一比较等价类的两个节点。3.2 红黑不变量用空孩子作为黑色叶哨兵理解时每个实体节点为红或黑。根最终为黑。红节点的实体孩子不能为红。从任一节点到其所有空叶路径经过的黑节点数相同。这些性质把根到叶的最长路径限制在最短路径的大约两倍内从而保证树高为 O(log n)。操作过程中可以暂时产生颜色冲突但公开方法返回时必须恢复不变量。3.3 容器状态不变量_count必须等于从根可达的节点数空集合应满足_root null与_count 0_version用于发现枚举期间的结构变化。颜色正确但计数错误或顺序正确但版本遗漏都不是正确的集合实现。自研红黑树测试时不要只测排序输出。树可能在普通输入下有序却已破坏黑高随后在某次删除中才崩溃。应递归验证 BST 上下界、红红冲突、根颜色、每条路径黑高和节点计数。四、Contains、Min、Max 与 TryGetValueContains(item)从根开始比较小于当前节点走左边大于走右边等于返回 true遇到空引用返回 false。树高受限因此最坏 O(log n)且不修改树和版本。// 教学伪代码表达搜索方向不是逐字源码。 Node? FindNode(T item) { Node? current _root; while (current is not null) { int order _comparer.Compare(item, current.Item); if (order 0) return current; current order 0 ? current.Left : current.Right; } return null; }Min一路取 LeftMax一路取 Right也是 O(log n) 上界空集合返回default所对应的 API 结果因此对引用类型或可空值类型不能只凭结果为 null 判断集合是否为空应结合Count。具体可空注解随目标框架查看 reference assembly。TryGetValue(equalValue, out actualValue)很适合“用临时键找到集合中规范对象”的场景。只要比较器认为二者相等它就返回节点内实际保存的元素而不是传入的探针。这再次说明 SortedSet 的身份边界由比较器定义。比较器调用可能是整个操作的主成本。例如文化相关字符串比较、动态读取外部状态或逐字段扫描的大键都不能仅用 O(log n) 隐去。复杂度更准确的表达是 O(log n × CompareCost)。五、Add下降途中拆分 4-node5.1 为什么采用 top-down 修复基线插入从根下降寻找空孩子。若途中遇到左右孩子都为红的黑节点即红黑树编码中的 4-node就把孩子变黑、当前节点变红相当于先拆分 4-node。拆分后若当前节点与父节点形成红红冲突立即通过单旋或双旋恢复。这个 top-down 策略让算法只需维护少量祖先引用不依赖 Node.Parent也无需在插入后保存整条路径回溯。其结构可概括为若树为空创建黑根count/version 更新成功 否则从根下降 比较 item 与 current.Item 相等恢复根为黑返回 false current 是 4-node分裂颜色 分裂导致父子皆红围绕祖父执行插入平衡 保存有限祖先并走向左或右孩子 到达空位置挂接红色新节点 若新节点与父节点皆红执行插入平衡 根染黑count 增加返回 true这里是算法骨架不是可复制的完整实现。旋转后必须正确重接祖父与曾祖父左右镜像情况也必须覆盖自行实现时应基于目标 tag 阅读InsertionBalance、单旋和双旋辅助函数。5.2 比较相等与版本的细节Add返回 false 表示集合中已有比较等价元素原节点 Item 不会被新对象替换。若业务希望更新内容应显式 Remove 再 Add或改用以稳定键索引的字典。值得注意的是.NET 8基线会在非空插入搜索开始时推进_version。原因是搜索途中可能已经拆分 4-node即使后来发现重复项树的形状或颜色也可能改变。因此失败的 Add 也可能使既有枚举器失效。用户代码不应假设“Count 没变所以枚举器必然继续有效”。版本行为属于具体实现依赖它做业务同步是不合理的。5.3 复杂度与分配成功 Add 搜索和修复 O(log n)通常分配一个 Node旋转只是重接引用不复制全部元素。失败 Add 不分配节点但会比较并可能重排颜色/结构。树高保证是最坏界不等于每次比较次数完全相同。六、Remove先避免下降进 2-node删除比插入难因为移除黑节点可能破坏路径黑高。.NET 8基线采用 top-down 思路当即将下降到 2-node黑节点且两个孩子也视为黑时先从兄弟借一个红节点或与父、兄弟进行颜色合并使下降路径具备可删除余量。高层流程如下空树返回 false 从根下降并记录有限祖先 若 current 是 2-node 若兄弟为红先旋转把黑兄弟调整到可处理位置 若父的两个孩子都是 2-node合并成 4-node 否则根据兄弟红孩子方向执行一次或两次旋转并重新着色 尚未命中时比较待删元素等于则记住 match 继续向中序后继方向下降 找到 match 后用后继位置完成替换并摘除一个至多单孩子节点 更新根、计数若根存在则恢复为黑真实实现会区分当前节点、父、祖父、已匹配节点及其父节点并处理左右镜像。上面的描述用于建立不变量不能代替源文件逐行核对。当待删节点有两个孩子时常见技巧是找到右子树最左节点即中序后继把后继的 Item 放到匹配节点再摘除后继节点。对外可观察的是值集合少了一个元素Node 身份是内部实现不是 API 契约。与 Add 类似删除搜索途中可能为了维持 top-down 条件而旋转或重新着色所以.NET 8基线在非空 Remove 中即使最终没找到元素也可能改变版本和内部形状。成功删除将_count减一。Remove 是 O(log n)不会为标准节点路径分配新 Node脱离树的节点若没有其他内部临时引用随后可由 GC 回收。Clear则直接断开根并把计数归零整棵节点图在没有枚举器或外部运行时引用时变为可回收。Node 是内部类型普通调用者不能持有节点但正在使用的枚举器可能暂时保存路径节点。Clear 不需要逐节点把 Item 设为 default 才能释放整树断开根即可破坏集合到节点图的强引用路径。七、GetViewBetween有边界的实时视图GetViewBetween(lowerValue, upperValue)返回包含闭区间[lowerValue, upperValue]的视图边界顺序同样由集合比较器解释。若比较器认为 lower 大于 upper应抛参数异常。视图不是数组拷贝它与底层集合共享树在范围内通过视图添加或删除会反映到原集合原集合的修改也会反映到视图的后续查询。var set new SortedSetint { 1, 2, 3, 4, 5, 6, 7, 8 }; SortedSetint view set.GetViewBetween(3, 6); view.Remove(4); // set 也不再包含 4 view.Add(5); // 返回 false5 已存在 // view.Add(100); // 越过视图上界抛 ArgumentOutOfRangeException旧稿称view.Add(100)会把 100 放进原集合这是错误的。视图必须守住自己的上下界否则它就不再是可靠的范围集合。基线内部以子集类型保存底层树和上下界并在需要时与底层版本同步。范围查找可利用树边界定位而不是先完整复制。枚举视图只产生范围内元素Min、Max和 Count 也以范围为准。因为它是实时视图长期缓存视图前应确认底层集合的生命周期和修改协议。多层视图或集合操作仍应验证边界语义。比较器若是降序“lower”和“upper”指比较器顺序不一定是数值上较小和较大调用者必须按该比较器构造合法区间。八、枚举与版本中序栈不是修改栈普通枚举按比较器升序中序遍历逻辑为“左子树—节点—右子树”。由于 Node 没有 Parent枚举器使用一个栈保存尚待返回的祖先。Reverse()提供反向枚举视图其遍历方向镜像但不会重建一棵树。// 教学伪代码省略版本检查和反向模式。 PushLeftSpine(_root); while (stack.Count 0) { Node node stack.Pop(); yield return node.Item; PushLeftSpine(node.Right); }枚举总时间 O(n)辅助栈 O(log n)因为红黑树高度受限。它不是把全部元素复制到 O(n) 临时列表。枚举器捕获版本。Add、Remove、Clear、集合运算等结构操作可能使版本变化后续MoveNext或相关访问将抛InvalidOperationException。如前所述某些失败修改也可能改变版本“操作返回 false”并不构成枚举安全承诺。要边枚举边修改可以先ToArray()制作快照并承担 O(n) 时间与内存或先收集待修改键枚举结束后批量处理。不要捕获异常后继续使用同一个枚举器其状态已不再受保证。九、集合运算语义先于优化路径SortedSetT实现并集、交集、差集、对称差集以及子集、超集、集合相等等查询。它们全部以当前集合的比较器等价关系解释“同一元素”。操作结果语义UnionWith(other)保留任一集合出现的等价类IntersectWith(other)只保留双方都有的等价类ExceptWith(other)删除 other 中出现的等价类SymmetricExceptWith(other)只保留恰好一侧出现的等价类IsSubsetOf/IsSupersetOf检查包含关系不改变集合SetEquals忽略输入枚举顺序比较等价类集合在特定条件下例如另一个对象也是使用等价比较器的 SortedSet基线实现可以利用两边已有顺序进行归并或范围跳转否则可能逐项 Add、Remove或建立辅助结构。准确复杂度取决于具体操作、输入类型、大小关系和版本不能统一宣称全部是 O(nm)。公开语义不依赖是否命中快速路径。输入与自身为同一对象时也有特殊语义与自身求并集或交集不改变内容与自身求差集或对称差集应清空。实现和测试都应覆盖别名情况。传入延迟枚举且其背后又依赖当前集合时先物化输入往往更清晰避免修改过程中枚举源失效。两个比较器实例即使类型相同也不一定表示相同顺序文化、大小写和构造参数都可能不同。集合运算结果以目标 SortedSet 的比较器为准不要用源集合的 Count 推断等价类数量。十、可变元素与比较器等价类最危险的正确性边界假设集合按玩家 Score 排序元素入树后直接把 Score 从 100 改成 900。Node 并不会自动移动树的搜索不变量立刻失效枚举可能不再有序Contains 可能找不到这个对象Remove 也可能沿错误方向走。sealed class MutablePlayer { public int Id { get; init; } public int Score { get; set; } }只要比较器读取Score此类型就不应在入集合后原地改变 Score。正确做法是先按旧键 Remove创建或修改后再 Add更稳妥的是使用不可变排序键并用字典保存 ID 到当前条目的映射。比较器还定义唯一性。若排行榜只比较 Score两个同分玩家中第二个 Add 会返回 false。应增加稳定、唯一的 tie-breaker例如 PlayerIdpublic readonly record struct RankEntry(int Score, int PlayerId); sealed class RankComparer : IComparerRankEntry { public int Compare(RankEntry x, RankEntry y) { int byScore y.Score.CompareTo(x.Score); // 高分排前 return byScore ! 0 ? byScore : x.PlayerId.CompareTo(y.PlayerId); } }避免用return x.Score - y.Score极端值可能整数溢出并破坏顺序。也不要让比较器读取当前时间、随机数、可变全局配置或不稳定的文化状态。若比较结果在两次调用间变化任何红黑树都无法维护正确结构。与哈希集合不同SortedSet 不要求GetHashCode与比较器一致但若同一领域对象同时进入 HashSet、Dictionary 和 SortedSet三种身份语义不一致会造成难以理解的业务差异。设计时应明确“对象身份”和“排序键”究竟是什么。十一、Unity 案例排行榜与范围查询11.1 可更新排行榜可以用SortedSetRankEntry维护顺序再用Dictionaryint, RankEntry找到玩家旧记录。更新必须先移除旧条目再加入新条目void UpdateScore( int playerId, int score, SortedSetRankEntry ranking, Dictionaryint, RankEntry byPlayer) { if (byPlayer.TryGetValue(playerId, out RankEntry oldEntry)) ranking.Remove(oldEntry); var next new RankEntry(score, playerId); if (!ranking.Add(next)) throw new InvalidOperationException(Ranking comparer lost uniqueness.); byPlayer[playerId] next; }取前 K 名可枚举前 K 个元素时间包含 O(K)。标准 SortedSet 节点不维护子树大小所以“直接取得第 k 名”不是 O(log n) 的公开能力频繁随机名次查询可能更适合带子树计数的顺序统计树、分桶结构或批量排序后的快照。Unity 中还要考虑托管分配。每次新增不同排名条目会产生树节点频繁移除再添加会让旧节点待回收。是否造成帧问题必须在目标 Unity 版本、脚本后端和设备上测量。可把更新集中到固定阶段、批量生成展示快照但不要为了池化而反射修改 SortedSet 内部 Node。11.2 范围查询例如以不可变时间戳和唯一事件 ID 排序public readonly record struct TimedEvent(long Tick, long EventId); var events new SortedSetTimedEvent( ComparerTimedEvent.Create((a, b) { int byTick a.Tick.CompareTo(b.Tick); return byTick ! 0 ? byTick : a.EventId.CompareTo(b.EventId); }));要取得某时间窗可构造该比较器意义下的最小、最大哨兵再调用GetViewBetween。哨兵的 EventId 边界必须覆盖同 Tick 的所有合法 ID。若无法定义安全哨兵直接从适当视图/枚举位置过滤或重新设计组合键会更可靠。视图是实时的不能在枚举视图时从原集合移除过期事件。常用模式是先把待删除键收集到临时列表结束枚举后删除或者循环读取 Min 并逐个 Remove前提是删除条件形成有序前缀。每帧清理仍需预算避免一次处理整个积压区间。十二、复杂度、GC 与线程安全操作时间复杂度分配与备注Contains/TryGetValueO(log n)通常不分配 NodeAddO(log n)成功时通常分配一个 NodeRemoveO(log n)摘除的 Node 等待 GCMin/MaxO(log n)沿单侧路径空集结果需结合 CountGetViewBetween创建视图本身不复制全部元素后续操作受范围与底层树版本影响枚举O(n)枚举器使用 O(log n) 路径栈Clear容器断根为常量级状态更新节点图随后由 GC 回收回收工作并非免费所有 O(log n) 还乘以比较器成本。树节点分散在托管堆上缓存局部性通常不如连续数组但它避免排序数组中间插入的 O(n) 搬移。集合规模、更新/查询比例、是否需要范围操作共同决定选择不能单凭大 O 或某个无环境倍数判断。SortedSetT不保证多线程写安全也不保证写入与枚举并发安全。多个只读线程只有在集合不再被任何线程修改、且对象内部比较键也保持不变时才有合理前提。需要并发更新时应以外部锁保护完整复合操作Contains后Add是两步协议即使单个方法分别加锁也可能不够。SyncRoot等遗留接口表面不等于自动同步。Unity 主线程与后台任务交换排行榜数据时可以在后台构造不可变快照再在主线程交换引用或用明确锁保护 SortedSet 与伴随字典的一致更新。两套索引必须处于同一事务边界。十三、差分测试与属性测试13.1 公共行为差分建立一个简单参考模型用 List 保存元素每次操作后按同一IComparerT排序并去除比较为 0 的等价项。随机生成 Add、Remove、Contains、Clear 和集合运算把 SortedSet 的返回值、Count、正序、反序、Min、Max 与参考模型逐项比较。差分输入必须包括升序、降序、全重复、锯齿序列、极端整数、同主键不同 tie-breaker、大量删除不存在项以及交替删除根、最小值和最大值。范围视图测试边界本身、空区间、单元素区间、全集区间、越界 Add 和底层修改后的同步结果。13.2 比较器属性对随机 x、y、z 检查sign(C(x, y)) -sign(C(y, x)) C(x, y) 0 且 C(y, z) 0 C(x, z) 0 C(x, y) 0 应形成稳定等价类 同一对象状态不变时多次比较结果一致这不能数学证明任意比较器正确却能捕获减法溢出、遗漏 tie-breaker、随机结果和可变外部状态等常见缺陷。13.3 内部红黑属性若是在学习项目中复刻源码可给自己的 Node 暴露测试入口递归返回节点数与黑高空节点黑高一致红节点没有红孩子左右子树黑高相同每个 Item 位于祖先传下来的开区间根为黑统计节点数等于 Count。不建议生产测试通过反射绑定框架私有字段名因为运行时升级可能仅重命名字段就让测试失效。验证系统SortedSetT时以公开行为做差分验证自研红黑树时再检查内部结构。13.4 枚举和生命周期验证正常枚举严格递增即相邻元素比较结果小于 0结构修改后旧枚举器失效Reverse 与正序完全相反。用弱引用检查回收时要避免测试局部变量、JIT 生存期或枚举器自身继续持有节点造成假结论并在目标运行时中把 GC 测试与功能测试分开。性能测试必须报告 .NET/Unity 版本、运行时后端、CPU、构建配置、比较器、输入分布、预热和集合规模。至少同时记录操作吞吐、分配量与尾延迟不要把随机输入的结果推广到有序输入也不要编造固定性能倍数。十四、源码阅读路线与审查清单固定.NET 8.0.0tag 后可以按以下顺序阅读SortedSet.cs先看字段、Node、NodeColor 与构造函数确认比较器和状态来源。从FindNode理解比较方向再读 Min、Max 与 TryGetValue。阅读AddIfNotPresent标出 current、parent、grandParent、greatGrandParent 的每次推进。对照Is2Node、Is4Node、Split4Node、旋转与InsertionBalance画出左右镜像。阅读 Remove 的下降修复和ReplaceNode逐个验证无孩子、单孩子、双孩子。阅读 Enumerator 的栈初始化、正反方向和版本检查。最后阅读 TreeSubSet 与集合运算因为它们建立在前述边界搜索和版本机制之上。审查业务代码时则问比较器是否稳定且传递比较为 0 是否真代表业务唯一性元素入树后排序字段会不会变化范围上下界是否按比较器方向给出排行榜是否需要 O(log n) 的第 k 名枚举期间是否修改SortedSet 与辅助字典是否原子更新目标运行时上的分配和延迟是否经过真实测量十五、总结红黑树维护的是比较器定义的世界.NET 8的SortedSetT以无 Parent 的 Node 组成红黑树。Contains、Min、Max 沿树搜索Add 和 Remove 采用 top-down 平衡在下降过程中拆分 4-node 或避免进入 2-node并用有限祖先引用完成旋转。枚举器才使用 O(log n) 栈按逻辑中序遍历。GetViewBetween 返回受闭区间约束的实时视图越界 Add 会抛异常不会偷偷污染原集合。集合运算、唯一性与查找全部服从_comparer的零等价类可变排序字段、缺失 tie-breaker 和不稳定比较器足以破坏整棵树的逻辑。这种结构用独立节点和较弱局部性换取最坏 O(log n) 更新与自然范围顺序。它适合动态有序集合却不是排名随机访问、并发队列或重复值多重集合。真正的源码级理解应能说明版本边界、证明红黑与 BST 不变量并用差分和属性测试覆盖旋转、删除、视图、比较器和枚举生命周期。下一篇SortedDictionary 与 SortedList排序的键值对集合