红黑树原理理解 SortedSet 与 SortedDictionary 的有序骨架系列C# 与常用数据结构源码剖析 · 排序集合篇定位先掌握红黑树算法模型再研究指定 .NET 发行版的集合实现版本边界公共行为以目标 TFM 的 API 契约为准内部节点、修复流程须以对应dotnet/runtimetag 为准一、为什么需要“会自动扶正”的二叉搜索树二叉搜索树Binary Search TreeBST为每个节点保存一个键并维持顺序关系左子树中的键小于当前键右子树中的键大于当前键。这里的“小于”和“大于”不是只能针对数字而是由比较器定义。中序遍历依次访问左子树、节点、右子树因此能输出比较器意义下的有序序列。在树形状足够均衡时查找每比较一次就排除大约一半候选路径长度为 O(log n)。但普通 BST 没有形状约束。依次插入1, 2, 3, 4, 5可能形成只有右孩子的链1 \ 2 \ 3 \ 4 \ 5此时查找 5 要走过所有节点插入和删除也可能退化为 O(n)。“数据平时比较随机”不是可靠保证时间戳、递增 ID、排序导入和分区后的数据都很容易产生有序输入。红黑树是在 BST 顺序之上增加少量颜色状态和局部变换的平衡搜索树。它不追求每个节点左右高度完全接近而是保证任何根到叶子的路径不会比其他路径长得失控。结果是查找、插入和删除在最坏情况下均为 O(log n)。这正是SortedSetT和SortedDictionaryTKey,TValue这类需要持续维护顺序的集合所需的成本边界。本文讨论的是经典红黑树模型。现代 .NET 某个版本可能采用自顶向下修复、不同颜色编码、无父指针节点或共享内部辅助结构这些属于具体源码。不能把下文伪代码冒充逐字源码也不能从 main 分支推断旧 .NET Framework 或 Unity 实现。二、红黑不变式与 NIL 叶子经典定义把每个缺失的孩子视作一个黑色哨兵叶子 NIL并要求每个内部节点非红即黑根为黑色所有 NIL 叶子为黑色红节点的两个孩子均为黑色即不存在连续红节点从任一节点到其所有后代 NIL 的每条路径黑节点数量相同。工程实现通常用null表示 NIL不一定真的为每个空孩子分配对象。推理时仍必须把 null 当黑色叶子否则删除修复和黑高计算会失去统一定义。2.1 黑高是什么节点 x 的黑高可以定义为从 x 出发但不计 x自其任一向下路径到 NIL 所包含的黑节点数。也有教材把起点计入定义两种约定都可以只要整篇证明一致。不变式 5 保证“任一路径”不会产生歧义。例如8B / \ 4R 12B / \ / \ 2B 6B NIL 14R / \ / \ / \ N N N N N N这个图并不是合法红黑树从12B到左侧 NIL 的路径包含该 NIL 一个黑节点而经14R到 NIL 也仍只包含 NIL一个黑节点局部看似成立但从根经左侧会遇到2B/6B NIL经右侧只遇到12B NIL。若采用不计起点的定义根两侧黑节点数量需逐路核算不能凭颜色外观判断。手推时标出每条路径的黑节点是发现错误最稳妥的方法。2.2 为什么高度是 O(log n)先看只计黑节点的“骨架”。黑高为 b 的子树至少包含2^b - 1个内部节点当 b 为零时下方可以没有内部节点每增加一层黑高左右两棵子树都至少具有前一黑高。由归纳可得n 2^b - 1所以b log2(n 1)。再看真实路径。红节点不能连续因此任一路径上的红节点数不超过黑节点数从根到最深 NIL 的边数 h 至多约为黑高的两倍于是h 2 * log2(n 1)常数和是否计 NIL 会随高度定义略有差异但渐进结论不变。这个证明的边界非常重要它依赖所有红黑不变式和严格的树结构若比较器不一致、指针成环、修复漏了一例复杂度保证也随之失效。O(log n) 还只限制比较次数的数量级不保证一次比较本身是 O(1)。若比较字符串需要逐字符扫描总成本还要乘上比较代价。三、旋转改变形状但保持中序顺序左旋以节点 x 及其右孩子 y 为中心x y / \ / \ A y 左旋 x x C / \ ---- / \ B C A B旋转前的顺序为A x B y C旋转后仍相同。右旋是镜像y x / \ / \ x C 右旋 y A y / \ ---- / \ A B B C旋转只重连常数个节点因此本身为 O(1)。实际实现还必须正确更新父节点到子树根的连接若节点保存 Parent还要同步父指针若不保存 Parent就要由遍历上下文保留祖先。根部旋转还需更新整棵树的 root。颜色变换与旋转承担不同职责旋转修正结构方向变色重新分配路径上的黑色贡献。仅旋转不一定恢复黑高仅变色也不一定消除所有连续红节点。四、插入为什么新节点先着红色先按普通 BST 找到插入位置。新内部节点的两个孩子都是 NIL。若把新节点直接设为黑色经过它的路径会无条件增加一个黑节点立即破坏祖先的黑高设为红色则不改变黑高只可能在父节点也为红时形成“红红冲突”。后者更容易通过局部修复解决。如果父为黑插入结束。如果父为红祖父一定存在且为黑因为旧树不允许连续红节点。以父是祖父左孩子为例观察叔节点4.1 叔节点为红颜色上移10B 10R / \ / \ 5R 15R - 5B 15B / 2R把父和叔染黑祖父染红。祖父子树经过左右两侧的黑节点数都增加一若不计祖父自身向外呈现的黑高不变但祖父可能与它的红父亲产生新冲突所以把检查点上移。若祖父成为根最后将根染黑。4.2 叔节点为黑折线转直线再旋转祖父左—右折线先对父左旋10B 10B / / 5R - 7R \ / 7R 5R它转化为左—左直线。随后父此时为 7染黑祖父 10 染红对祖父右旋10B 7B / / \ 7R - 5R 10R / 5R父在右侧的情况完全镜像。经典算法中插入修复可能多次变色上移但旋转集中发生在终止冲突的局部。不要把某教材的“case 编号”当公共契约不同实现会合并镜像分支、采用自顶向下分裂四节点或用不同旋转组合表达同一不变式恢复。4.3 一次完整手推插入 10、5、1、7、6依次插入 10、5 时根黑、5 红无冲突10B / 5R插入 1 后形成左—左变色并右旋5B / \ 1R 10R插入 7 时父 10 与叔 1 都红于是 1、10 变黑5 暂变红最后根重新染黑5B / \ 1B 10B / 7R插入 6 后父 7 红、叔为黑 NIL形成相对祖父 10 的左—左右旋并变色5B / \ 1B 7B / \ 6R 10R现在中序结果为1,5,6,7,10根黑红节点 6、10 的孩子都是黑 NIL从每个节点到 NIL 的黑高相同。手推不能只看“树似乎挺平衡”必须逐条验证这三项。五、删除先处理 BST再偿还丢失的黑色BST 删除分三种表面情况没有孩子直接移除只有一个非空孩子用孩子替代有两个孩子用中序前驱或后继的键值替换目标再删除那个至多只有一个非空孩子的节点。红黑修复关心的是物理被移除节点的原颜色而不只是调用者请求删除的节点颜色。删除红节点通常不改变任一路径黑高。删除黑节点时替代位置所在路径少一个黑色。教材常把替代节点描述成“额外带一层黑”即 double black。双黑不是节点字段中的第三种永久颜色而是“这条路径欠一个黑色贡献”的推理工具。如果黑节点只有一个非 NIL 孩子在合法红黑树中该孩子必须为红用它替代并染黑即可补回黑高。最复杂的是黑叶或替代孩子为黑 NIL。设双黑位置 x 是父 p 的左孩子兄弟 s 在右侧右孩子情形镜像。5.1 兄弟为红先转换成黑兄弟场景父必为黑兄弟的孩子必为黑。将兄弟染黑、父染红并对父左旋。x 的欠账还在但新兄弟变为黑色从而进入后续情形。这个步骤是结构转换不是单独结束修复。5.2 黑兄弟的两个孩子均黑向上转移欠账把兄弟染红相当于从兄弟一侧减少一个黑色使左右局部黑高重新相等。如果父原为红把父染黑即可吸收欠账如果父为黑则把父视为新的双黑位置继续向上。到根时可以直接消除额外黑因为所有根到叶路径同时少同一层不会破坏相等性。5.3 黑兄弟近侄红、远侄黑先转成终止形态对当前 x 在左侧而言兄弟的左孩子是近侄、右孩子是远侄。将近侄染黑、兄弟染红对兄弟右旋。新的兄弟拥有红色远侄转入下一情形。“近”和“远”必须相对 x 定义镜像分支方向相反。5.4 黑兄弟的远侄为红旋转并结束让兄弟继承父颜色父染黑远侄染黑再对父左旋。这次旋转把一层黑色分配到 x 一侧同时保持另一侧黑高双黑消失。抽象终止形态x 在左N 表示欠一个黑的子树 p(?) s(?) / \ / \ N s(B) 左旋 p p(B) f(B) / \ -------- / \ n(?) f(R) N n(?)图中的?不是任意涂色而表示颜色会按规则继承或保持N、n 子树自身也必须拥有匹配黑高。删除图示很容易因省略 NIL 和子树黑高而画错因此应配合不变式验证而不能靠记住四张图编码实现。经典 CLRS 是自底向上的删除修复某些库实现会在向下搜索待删键时提前变换 2-node使即将进入的子树具备可删除条件。两者的 case 形态与变量命名不同但目标相同保持 BST 次序、根黑、无连续红和黑高一致。研究SortedSetT.Remove时应读固定 tag 的真实控制流不能把上面的经典伪过程声称为该版本逐行源码。六、比较器定义的不是“排序外观”而是键身份SortedSetT和SortedDictionaryTKey,TValue依赖IComparerT。比较器返回负数、零或正数分别表示 x 位于 y 之前、属于同一排序等价类、位于 y 之后。树需要它形成稳定的全序或足以用于集合的全序关系自反Compare(x, x) 0反对称符号x y 时 y x传递x y 且 y z则 x z等价关系传递x 与 y 比较为零、y 与 z 为零则 x 与 z 也应为零同一批键在集合生命周期内比较结果稳定。比较结果为零就是树所认定的重复键。它不必等于object.Equals的结果。例如忽略大小写比较器会让player与PLAYER占同一个排序位置SortedSet 第二次 Add 返回 falseSortedDictionary 第二次 Add 同等键会按其契约拒绝而索引器赋值可能更新该等价键对应的值。调用方必须选择与领域身份一致的 comparer。var names new SortedSetstring(StringComparer.OrdinalIgnoreCase); Console.WriteLine(names.Add(Mage)); // true Console.WriteLine(names.Add(MAGE)); // false比较器判定为同一元素减法不是安全的整数比较器return x.Id - y.Id可能溢出并破坏顺序。应使用x.Id.CompareTo(y.Id)再逐字段打破平局sealed class ScoreComparer : IComparerPlayerScore { public int Compare(PlayerScore? x, PlayerScore? y) { if (ReferenceEquals(x, y)) return 0; if (x is null) return -1; if (y is null) return 1; int byScore y.Score.CompareTo(x.Score); // 高分在前 return byScore ! 0 ? byScore : x.PlayerId.CompareTo(y.PlayerId); } }最后的稳定 ID 很关键。若只比较 Score同分玩家会被判作重复。更危险的是插入后修改 Score节点仍留在旧位置而后续查找会按新值选择另一条路径导致Contains、Remove 和枚举语义异常。树无法自动察觉可变键。可靠做法是让参与比较的字段不可变或先 Remove 旧值、修改后重新 Add。SortedDictionary 的 key 同样不得在入树后改变比较意义。比较器也不应依赖当前文化、随机数、系统时间或会变化的外部配置。文化相关排序若确属业务需要应固定规则并设计升级/重建策略因为比较规则变化后必须重新建树。七、SortedSet 与 SortedDictionary 如何映射到树在抽象层面SortedSetT的每个树节点保存一个 T比较器决定节点位置和重复身份。它适用于唯一有序元素、范围查询、最小/最大值和集合运算。SortedDictionaryTKey,TValue的每个逻辑节点保存键值关联树只按 key 比较value 不参与定位。更新 value 不应改变树形修改 key 则不是原位操作而应删除旧键并插入新键。不同 .NET 版本可能通过内部集合、键值节点或共享辅助类型实现这一映射不应在未固定 tag 时断言具体字段布局。两者的典型公共成本边界如下操作SortedSetSortedDictionary典型最坏时间查找Contains(item)ContainsKey/TryGetValueO(log n) 次比较插入Add(item)Add(key, value)O(log n)删除Remove(item)Remove(key)O(log n)最小/最大Min/Max通过有序枚举或相应 API依契约与实现核验全量枚举比较器顺序按 key 的比较器顺序O(n)范围视图GetViewBetween等按目标 API 选择定位通常 O(log n)输出另加 O(k)O(log n) 计算的是树路径长度复杂比较器要另计成本枚举 n 项至少是 O(n)。范围输出 k 项的成本不可能小于 O(k)。枚举期间结构修改通常会使枚举器失效但准确异常与视图行为以目标版本 API 契约为准。如果只需要相等查找而不需要顺序HashSet/Dictionary 平均 O(1) 通常更合适需要紧凑顺序遍历且数据批量构建后少修改可以考虑 List/数组排序后二分需要频繁得到最小优先项但不需要按键查找可评估 PriorityQueue。红黑树的价值是动态更新、唯一身份、有序枚举和对数级定位的组合不是在所有指标上胜出。八、树结构与缓存局部性数组元素连续顺序遍历能很好利用缓存行和硬件预取。节点式红黑树通常让每个节点成为独立托管对象左右孩子通过引用连接一次查找会沿不可预测的分支跳转可能产生更多缓存未命中和分支预测失败。节点还包含颜色和引用字段并承担对象头、对齐与 GC 跟踪成本。因此O(log n) 的树查找不保证在中小数据上比排序数组二分快。二分虽然也是 O(log n)但随机跨数组访问仍在一块连续区域全量遍历的差距可能更明显。反过来排序数组中间插入要移动 O(n) 个元素而树只沿 O(log n) 路径定位并做常数级局部结构调整。不要写固定的“每节点多少字节”或“树比哈希慢几倍”而没有环境。对象大小受进程位数、引用压缩、T 的形态、运行时布局和具体实现影响。可信比较应固定目标运行时、CPU、数据规模、比较器、增删比例和枚举比例并同时记录吞吐、分配、驻留内存与尾延迟。Unity 还需在目标 Player、Mono 或 IL2CPP 后端与真实设备上测量。九、如何测试红黑树实现与 BCL 使用方如果自己实现红黑树不能只验证输出有序。每次随机插入和删除后都应递归检查// 教学伪代码null 作为黑色 NIL返回子树黑高。 static int ValidateT(NodeT? node, IComparerT comparer, T? lower, bool hasLower, T? upper, bool hasUpper) { if (node is null) return 1; // NIL 计作一个黑节点 if (hasLower comparer.Compare(node.Item, lower!) 0) throw new InvalidOperationException(BST lower bound violated); if (hasUpper comparer.Compare(node.Item, upper!) 0) throw new InvalidOperationException(BST upper bound violated); if (node.IsRed (IsRed(node.Left) || IsRed(node.Right))) throw new InvalidOperationException(consecutive red nodes); int left Validate(node.Left, comparer, lower, hasLower, node.Item, true); int right Validate(node.Right, comparer, node.Item, true, upper, hasUpper); if (left ! right) throw new InvalidOperationException(black-height mismatch); return left (node.IsRed ? 0 : 1); }入口还要单独断言 root 为黑、节点计数与 Count 一致、没有环和节点复用。泛型边界参数用 nullable 表达时容易混淆“没有边界”和“边界值本身为 null”所以上例显式携带hasLower/hasUpper生产测试可用专门的 Optional 类型。建议用性质测试生成操作序列并以简单模型交叉验证随机生成 Add、Remove、Contains逐步与排序后的唯一 List 对照覆盖升序、降序、相同键、锯齿序列而不只用随机输入每一步检查红黑不变式、中序严格递增和 Count删除根、红叶、黑叶、仅有一个孩子和有两个孩子的节点反复删除不存在的键并删除到空再重新插入用故意错误的 comparer 验证测试确实能捕获反对称或传递性破坏对数值键覆盖最小值和最大值防止减法比较器溢出。测试 BCL 的 SortedSet/SortedDictionary 时不应反射私有颜色字段因为这会绑定内部实现。应从公共契约验证Add/Remove 返回值、重复判定、Contains/TryGetValue、枚举顺序、范围边界、自定义 comparer、空集合以及枚举失效。若要研究某版内部算法则把源码 tag、commit、测试项目 TFM 和运行时版本一起记录并在独立的源码研究测试中完成。十、审查清单与结论引入排序集合前可以逐项确认是否同时需要动态增删、唯一键、有序枚举或范围能力comparer 是否稳定、自反、反对称、传递并与领域“重复”定义一致所有参与比较的字段在入树后是否不可变是否错误依赖 value 参与 SortedDictionary 的位置热路径主要是点查、更新、范围扫描还是全量枚举节点分配与缓存局部性是否已在目标平台测量并发访问是否有外部同步方案普通排序集合并非并发写容器持久化是否保存逻辑键值而非私有树形、颜色和字段关于特定 .NET 版本的实现说法是否有发行 tag 与测试佐证。红黑树的核心不是背诵“左左、左右、四个删除 case”而是理解两份契约同时成立中序顺序由比较器维护路径高度由颜色不变式约束。旋转保持顺序变色和局部重构恢复黑高与红节点规则二者共同给出最坏 O(log n) 的搜索路径。SortedSetT将比较为零视作同一元素SortedDictionaryTKey,TValue将比较为零视作同一键。于是比较器实际上定义了集合身份而不只是显示顺序。可变键和不传递比较器会从根上破坏树的语义。最后要保持算法与实现的边界本文的经典修复过程用于建立推理模型不代表每个 .NET 版本逐行采用同一种控制流。阅读真实集合时固定 TFM、发行 tag 和源码文件评价性能时固定负载与平台不编造字节数或倍数。掌握这些边界后后续剖析具体 SortedSet 源码才不会把偶然实现细节误当成红黑树本身。下一篇SortedSet红黑树实现、不变式与版本边界 
长河君 · 2026/8/31 6:19:05 · 阅读 1.2k 06-01-排序集合-红黑树原理-SortedSet与SortedDictionary背后的数据结构
红黑树原理理解 SortedSet 与 SortedDictionary 的有序骨架系列C# 与常用数据结构源码剖析 · 排序集合篇定位先掌握红黑树算法模型再研究指定 .NET 发行版的集合实现版本边界公共行为以目标 TFM 的 API 契约为准内部节点、修复流程须以对应dotnet/runtimetag 为准一、为什么需要“会自动扶正”的二叉搜索树二叉搜索树Binary Search TreeBST为每个节点保存一个键并维持顺序关系左子树中的键小于当前键右子树中的键大于当前键。这里的“小于”和“大于”不是只能针对数字而是由比较器定义。中序遍历依次访问左子树、节点、右子树因此能输出比较器意义下的有序序列。在树形状足够均衡时查找每比较一次就排除大约一半候选路径长度为 O(log n)。但普通 BST 没有形状约束。依次插入1, 2, 3, 4, 5可能形成只有右孩子的链1 \ 2 \ 3 \ 4 \ 5此时查找 5 要走过所有节点插入和删除也可能退化为 O(n)。“数据平时比较随机”不是可靠保证时间戳、递增 ID、排序导入和分区后的数据都很容易产生有序输入。红黑树是在 BST 顺序之上增加少量颜色状态和局部变换的平衡搜索树。它不追求每个节点左右高度完全接近而是保证任何根到叶子的路径不会比其他路径长得失控。结果是查找、插入和删除在最坏情况下均为 O(log n)。这正是SortedSetT和SortedDictionaryTKey,TValue这类需要持续维护顺序的集合所需的成本边界。本文讨论的是经典红黑树模型。现代 .NET 某个版本可能采用自顶向下修复、不同颜色编码、无父指针节点或共享内部辅助结构这些属于具体源码。不能把下文伪代码冒充逐字源码也不能从 main 分支推断旧 .NET Framework 或 Unity 实现。二、红黑不变式与 NIL 叶子经典定义把每个缺失的孩子视作一个黑色哨兵叶子 NIL并要求每个内部节点非红即黑根为黑色所有 NIL 叶子为黑色红节点的两个孩子均为黑色即不存在连续红节点从任一节点到其所有后代 NIL 的每条路径黑节点数量相同。工程实现通常用null表示 NIL不一定真的为每个空孩子分配对象。推理时仍必须把 null 当黑色叶子否则删除修复和黑高计算会失去统一定义。2.1 黑高是什么节点 x 的黑高可以定义为从 x 出发但不计 x自其任一向下路径到 NIL 所包含的黑节点数。也有教材把起点计入定义两种约定都可以只要整篇证明一致。不变式 5 保证“任一路径”不会产生歧义。例如8B / \ 4R 12B / \ / \ 2B 6B NIL 14R / \ / \ / \ N N N N N N这个图并不是合法红黑树从12B到左侧 NIL 的路径包含该 NIL 一个黑节点而经14R到 NIL 也仍只包含 NIL一个黑节点局部看似成立但从根经左侧会遇到2B/6B NIL经右侧只遇到12B NIL。若采用不计起点的定义根两侧黑节点数量需逐路核算不能凭颜色外观判断。手推时标出每条路径的黑节点是发现错误最稳妥的方法。2.2 为什么高度是 O(log n)先看只计黑节点的“骨架”。黑高为 b 的子树至少包含2^b - 1个内部节点当 b 为零时下方可以没有内部节点每增加一层黑高左右两棵子树都至少具有前一黑高。由归纳可得n 2^b - 1所以b log2(n 1)。再看真实路径。红节点不能连续因此任一路径上的红节点数不超过黑节点数从根到最深 NIL 的边数 h 至多约为黑高的两倍于是h 2 * log2(n 1)常数和是否计 NIL 会随高度定义略有差异但渐进结论不变。这个证明的边界非常重要它依赖所有红黑不变式和严格的树结构若比较器不一致、指针成环、修复漏了一例复杂度保证也随之失效。O(log n) 还只限制比较次数的数量级不保证一次比较本身是 O(1)。若比较字符串需要逐字符扫描总成本还要乘上比较代价。三、旋转改变形状但保持中序顺序左旋以节点 x 及其右孩子 y 为中心x y / \ / \ A y 左旋 x x C / \ ---- / \ B C A B旋转前的顺序为A x B y C旋转后仍相同。右旋是镜像y x / \ / \ x C 右旋 y A y / \ ---- / \ A B B C旋转只重连常数个节点因此本身为 O(1)。实际实现还必须正确更新父节点到子树根的连接若节点保存 Parent还要同步父指针若不保存 Parent就要由遍历上下文保留祖先。根部旋转还需更新整棵树的 root。颜色变换与旋转承担不同职责旋转修正结构方向变色重新分配路径上的黑色贡献。仅旋转不一定恢复黑高仅变色也不一定消除所有连续红节点。四、插入为什么新节点先着红色先按普通 BST 找到插入位置。新内部节点的两个孩子都是 NIL。若把新节点直接设为黑色经过它的路径会无条件增加一个黑节点立即破坏祖先的黑高设为红色则不改变黑高只可能在父节点也为红时形成“红红冲突”。后者更容易通过局部修复解决。如果父为黑插入结束。如果父为红祖父一定存在且为黑因为旧树不允许连续红节点。以父是祖父左孩子为例观察叔节点4.1 叔节点为红颜色上移10B 10R / \ / \ 5R 15R - 5B 15B / 2R把父和叔染黑祖父染红。祖父子树经过左右两侧的黑节点数都增加一若不计祖父自身向外呈现的黑高不变但祖父可能与它的红父亲产生新冲突所以把检查点上移。若祖父成为根最后将根染黑。4.2 叔节点为黑折线转直线再旋转祖父左—右折线先对父左旋10B 10B / / 5R - 7R \ / 7R 5R它转化为左—左直线。随后父此时为 7染黑祖父 10 染红对祖父右旋10B 7B / / \ 7R - 5R 10R / 5R父在右侧的情况完全镜像。经典算法中插入修复可能多次变色上移但旋转集中发生在终止冲突的局部。不要把某教材的“case 编号”当公共契约不同实现会合并镜像分支、采用自顶向下分裂四节点或用不同旋转组合表达同一不变式恢复。4.3 一次完整手推插入 10、5、1、7、6依次插入 10、5 时根黑、5 红无冲突10B / 5R插入 1 后形成左—左变色并右旋5B / \ 1R 10R插入 7 时父 10 与叔 1 都红于是 1、10 变黑5 暂变红最后根重新染黑5B / \ 1B 10B / 7R插入 6 后父 7 红、叔为黑 NIL形成相对祖父 10 的左—左右旋并变色5B / \ 1B 7B / \ 6R 10R现在中序结果为1,5,6,7,10根黑红节点 6、10 的孩子都是黑 NIL从每个节点到 NIL 的黑高相同。手推不能只看“树似乎挺平衡”必须逐条验证这三项。五、删除先处理 BST再偿还丢失的黑色BST 删除分三种表面情况没有孩子直接移除只有一个非空孩子用孩子替代有两个孩子用中序前驱或后继的键值替换目标再删除那个至多只有一个非空孩子的节点。红黑修复关心的是物理被移除节点的原颜色而不只是调用者请求删除的节点颜色。删除红节点通常不改变任一路径黑高。删除黑节点时替代位置所在路径少一个黑色。教材常把替代节点描述成“额外带一层黑”即 double black。双黑不是节点字段中的第三种永久颜色而是“这条路径欠一个黑色贡献”的推理工具。如果黑节点只有一个非 NIL 孩子在合法红黑树中该孩子必须为红用它替代并染黑即可补回黑高。最复杂的是黑叶或替代孩子为黑 NIL。设双黑位置 x 是父 p 的左孩子兄弟 s 在右侧右孩子情形镜像。5.1 兄弟为红先转换成黑兄弟场景父必为黑兄弟的孩子必为黑。将兄弟染黑、父染红并对父左旋。x 的欠账还在但新兄弟变为黑色从而进入后续情形。这个步骤是结构转换不是单独结束修复。5.2 黑兄弟的两个孩子均黑向上转移欠账把兄弟染红相当于从兄弟一侧减少一个黑色使左右局部黑高重新相等。如果父原为红把父染黑即可吸收欠账如果父为黑则把父视为新的双黑位置继续向上。到根时可以直接消除额外黑因为所有根到叶路径同时少同一层不会破坏相等性。5.3 黑兄弟近侄红、远侄黑先转成终止形态对当前 x 在左侧而言兄弟的左孩子是近侄、右孩子是远侄。将近侄染黑、兄弟染红对兄弟右旋。新的兄弟拥有红色远侄转入下一情形。“近”和“远”必须相对 x 定义镜像分支方向相反。5.4 黑兄弟的远侄为红旋转并结束让兄弟继承父颜色父染黑远侄染黑再对父左旋。这次旋转把一层黑色分配到 x 一侧同时保持另一侧黑高双黑消失。抽象终止形态x 在左N 表示欠一个黑的子树 p(?) s(?) / \ / \ N s(B) 左旋 p p(B) f(B) / \ -------- / \ n(?) f(R) N n(?)图中的?不是任意涂色而表示颜色会按规则继承或保持N、n 子树自身也必须拥有匹配黑高。删除图示很容易因省略 NIL 和子树黑高而画错因此应配合不变式验证而不能靠记住四张图编码实现。经典 CLRS 是自底向上的删除修复某些库实现会在向下搜索待删键时提前变换 2-node使即将进入的子树具备可删除条件。两者的 case 形态与变量命名不同但目标相同保持 BST 次序、根黑、无连续红和黑高一致。研究SortedSetT.Remove时应读固定 tag 的真实控制流不能把上面的经典伪过程声称为该版本逐行源码。六、比较器定义的不是“排序外观”而是键身份SortedSetT和SortedDictionaryTKey,TValue依赖IComparerT。比较器返回负数、零或正数分别表示 x 位于 y 之前、属于同一排序等价类、位于 y 之后。树需要它形成稳定的全序或足以用于集合的全序关系自反Compare(x, x) 0反对称符号x y 时 y x传递x y 且 y z则 x z等价关系传递x 与 y 比较为零、y 与 z 为零则 x 与 z 也应为零同一批键在集合生命周期内比较结果稳定。比较结果为零就是树所认定的重复键。它不必等于object.Equals的结果。例如忽略大小写比较器会让player与PLAYER占同一个排序位置SortedSet 第二次 Add 返回 falseSortedDictionary 第二次 Add 同等键会按其契约拒绝而索引器赋值可能更新该等价键对应的值。调用方必须选择与领域身份一致的 comparer。var names new SortedSetstring(StringComparer.OrdinalIgnoreCase); Console.WriteLine(names.Add(Mage)); // true Console.WriteLine(names.Add(MAGE)); // false比较器判定为同一元素减法不是安全的整数比较器return x.Id - y.Id可能溢出并破坏顺序。应使用x.Id.CompareTo(y.Id)再逐字段打破平局sealed class ScoreComparer : IComparerPlayerScore { public int Compare(PlayerScore? x, PlayerScore? y) { if (ReferenceEquals(x, y)) return 0; if (x is null) return -1; if (y is null) return 1; int byScore y.Score.CompareTo(x.Score); // 高分在前 return byScore ! 0 ? byScore : x.PlayerId.CompareTo(y.PlayerId); } }最后的稳定 ID 很关键。若只比较 Score同分玩家会被判作重复。更危险的是插入后修改 Score节点仍留在旧位置而后续查找会按新值选择另一条路径导致Contains、Remove 和枚举语义异常。树无法自动察觉可变键。可靠做法是让参与比较的字段不可变或先 Remove 旧值、修改后重新 Add。SortedDictionary 的 key 同样不得在入树后改变比较意义。比较器也不应依赖当前文化、随机数、系统时间或会变化的外部配置。文化相关排序若确属业务需要应固定规则并设计升级/重建策略因为比较规则变化后必须重新建树。七、SortedSet 与 SortedDictionary 如何映射到树在抽象层面SortedSetT的每个树节点保存一个 T比较器决定节点位置和重复身份。它适用于唯一有序元素、范围查询、最小/最大值和集合运算。SortedDictionaryTKey,TValue的每个逻辑节点保存键值关联树只按 key 比较value 不参与定位。更新 value 不应改变树形修改 key 则不是原位操作而应删除旧键并插入新键。不同 .NET 版本可能通过内部集合、键值节点或共享辅助类型实现这一映射不应在未固定 tag 时断言具体字段布局。两者的典型公共成本边界如下操作SortedSetSortedDictionary典型最坏时间查找Contains(item)ContainsKey/TryGetValueO(log n) 次比较插入Add(item)Add(key, value)O(log n)删除Remove(item)Remove(key)O(log n)最小/最大Min/Max通过有序枚举或相应 API依契约与实现核验全量枚举比较器顺序按 key 的比较器顺序O(n)范围视图GetViewBetween等按目标 API 选择定位通常 O(log n)输出另加 O(k)O(log n) 计算的是树路径长度复杂比较器要另计成本枚举 n 项至少是 O(n)。范围输出 k 项的成本不可能小于 O(k)。枚举期间结构修改通常会使枚举器失效但准确异常与视图行为以目标版本 API 契约为准。如果只需要相等查找而不需要顺序HashSet/Dictionary 平均 O(1) 通常更合适需要紧凑顺序遍历且数据批量构建后少修改可以考虑 List/数组排序后二分需要频繁得到最小优先项但不需要按键查找可评估 PriorityQueue。红黑树的价值是动态更新、唯一身份、有序枚举和对数级定位的组合不是在所有指标上胜出。八、树结构与缓存局部性数组元素连续顺序遍历能很好利用缓存行和硬件预取。节点式红黑树通常让每个节点成为独立托管对象左右孩子通过引用连接一次查找会沿不可预测的分支跳转可能产生更多缓存未命中和分支预测失败。节点还包含颜色和引用字段并承担对象头、对齐与 GC 跟踪成本。因此O(log n) 的树查找不保证在中小数据上比排序数组二分快。二分虽然也是 O(log n)但随机跨数组访问仍在一块连续区域全量遍历的差距可能更明显。反过来排序数组中间插入要移动 O(n) 个元素而树只沿 O(log n) 路径定位并做常数级局部结构调整。不要写固定的“每节点多少字节”或“树比哈希慢几倍”而没有环境。对象大小受进程位数、引用压缩、T 的形态、运行时布局和具体实现影响。可信比较应固定目标运行时、CPU、数据规模、比较器、增删比例和枚举比例并同时记录吞吐、分配、驻留内存与尾延迟。Unity 还需在目标 Player、Mono 或 IL2CPP 后端与真实设备上测量。九、如何测试红黑树实现与 BCL 使用方如果自己实现红黑树不能只验证输出有序。每次随机插入和删除后都应递归检查// 教学伪代码null 作为黑色 NIL返回子树黑高。 static int ValidateT(NodeT? node, IComparerT comparer, T? lower, bool hasLower, T? upper, bool hasUpper) { if (node is null) return 1; // NIL 计作一个黑节点 if (hasLower comparer.Compare(node.Item, lower!) 0) throw new InvalidOperationException(BST lower bound violated); if (hasUpper comparer.Compare(node.Item, upper!) 0) throw new InvalidOperationException(BST upper bound violated); if (node.IsRed (IsRed(node.Left) || IsRed(node.Right))) throw new InvalidOperationException(consecutive red nodes); int left Validate(node.Left, comparer, lower, hasLower, node.Item, true); int right Validate(node.Right, comparer, node.Item, true, upper, hasUpper); if (left ! right) throw new InvalidOperationException(black-height mismatch); return left (node.IsRed ? 0 : 1); }入口还要单独断言 root 为黑、节点计数与 Count 一致、没有环和节点复用。泛型边界参数用 nullable 表达时容易混淆“没有边界”和“边界值本身为 null”所以上例显式携带hasLower/hasUpper生产测试可用专门的 Optional 类型。建议用性质测试生成操作序列并以简单模型交叉验证随机生成 Add、Remove、Contains逐步与排序后的唯一 List 对照覆盖升序、降序、相同键、锯齿序列而不只用随机输入每一步检查红黑不变式、中序严格递增和 Count删除根、红叶、黑叶、仅有一个孩子和有两个孩子的节点反复删除不存在的键并删除到空再重新插入用故意错误的 comparer 验证测试确实能捕获反对称或传递性破坏对数值键覆盖最小值和最大值防止减法比较器溢出。测试 BCL 的 SortedSet/SortedDictionary 时不应反射私有颜色字段因为这会绑定内部实现。应从公共契约验证Add/Remove 返回值、重复判定、Contains/TryGetValue、枚举顺序、范围边界、自定义 comparer、空集合以及枚举失效。若要研究某版内部算法则把源码 tag、commit、测试项目 TFM 和运行时版本一起记录并在独立的源码研究测试中完成。十、审查清单与结论引入排序集合前可以逐项确认是否同时需要动态增删、唯一键、有序枚举或范围能力comparer 是否稳定、自反、反对称、传递并与领域“重复”定义一致所有参与比较的字段在入树后是否不可变是否错误依赖 value 参与 SortedDictionary 的位置热路径主要是点查、更新、范围扫描还是全量枚举节点分配与缓存局部性是否已在目标平台测量并发访问是否有外部同步方案普通排序集合并非并发写容器持久化是否保存逻辑键值而非私有树形、颜色和字段关于特定 .NET 版本的实现说法是否有发行 tag 与测试佐证。红黑树的核心不是背诵“左左、左右、四个删除 case”而是理解两份契约同时成立中序顺序由比较器维护路径高度由颜色不变式约束。旋转保持顺序变色和局部重构恢复黑高与红节点规则二者共同给出最坏 O(log n) 的搜索路径。SortedSetT将比较为零视作同一元素SortedDictionaryTKey,TValue将比较为零视作同一键。于是比较器实际上定义了集合身份而不只是显示顺序。可变键和不传递比较器会从根上破坏树的语义。最后要保持算法与实现的边界本文的经典修复过程用于建立推理模型不代表每个 .NET 版本逐行采用同一种控制流。阅读真实集合时固定 TFM、发行 tag 和源码文件评价性能时固定负载与平台不编造字节数或倍数。掌握这些边界后后续剖析具体 SortedSet 源码才不会把偶然实现细节误当成红黑树本身。下一篇SortedSet红黑树实现、不变式与版本边界