06-01-排序集合-红黑树原理-SortedSet与SortedDictionary背后的数据结构

红黑树原理：理解 SortedSet 与 SortedDictionary 的有序骨架

系列：C# 与常用数据结构源码剖析 · 排序集合篇
定位：先掌握红黑树算法模型，再研究指定 .NET 发行版的集合实现
版本边界：公共行为以目标 TFM 的 API 契约为准；内部节点、修复流程须以对应dotnet/runtimetag 为准

一、为什么需要“会自动扶正”的二叉搜索树

二叉搜索树（Binary Search Tree，BST）为每个节点保存一个键，并维持顺序关系：左子树中的键小于当前键，右子树中的键大于当前键。这里的“小于”和“大于”不是只能针对数字，而是由比较器定义。中序遍历依次访问左子树、节点、右子树，因此能输出比较器意义下的有序序列。

在树形状足够均衡时，查找每比较一次就排除大约一半候选，路径长度为 O(log n)。但普通 BST 没有形状约束。依次插入1, 2, 3, 4, 5，可能形成只有右孩子的链：

1 \ 2 \ 3 \ 4 \ 5

此时查找 5 要走过所有节点，插入和删除也可能退化为 O(n)。“数据平时比较随机”不是可靠保证：时间戳、递增 ID、排序导入和分区后的数据都很容易产生有序输入。

红黑树是在 BST 顺序之上增加少量颜色状态和局部变换的平衡搜索树。它不追求每个节点左右高度完全接近，而是保证任何根到叶子的路径不会比其他路径长得失控。结果是查找、插入和删除在最坏情况下均为 O(log n)。这正是SortedSet<T>和SortedDictionary<TKey,TValue>这类需要持续维护顺序的集合所需的成本边界。

本文讨论的是经典红黑树模型。现代 .NET 某个版本可能采用自顶向下修复、不同颜色编码、无父指针节点或共享内部辅助结构；这些属于具体源码。不能把下文伪代码冒充逐字源码，也不能从 main 分支推断旧 .NET Framework 或 Unity 实现。

二、红黑不变式与 NIL 叶子

经典定义把每个缺失的孩子视作一个黑色哨兵叶子 NIL，并要求：

1. 每个内部节点非红即黑；
2. 根为黑色；
3. 所有 NIL 叶子为黑色；
4. 红节点的两个孩子均为黑色，即不存在连续红节点；
5. 从任一节点到其所有后代 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 次序、根黑、无连续红和黑高一致。研究SortedSet<T>.Remove时应读固定 tag 的真实控制流，不能把上面的经典伪过程声称为该版本逐行源码。

六、比较器定义的不是“排序外观”，而是键身份

SortedSet<T>和SortedDictionary<TKey,TValue>依赖IComparer<T>。比较器返回负数、零或正数，分别表示 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 返回 false；SortedDictionary 第二次 Add 同等键会按其契约拒绝，而索引器赋值可能更新该等价键对应的值。调用方必须选择与领域身份一致的 comparer。

var names = new SortedSet<string>(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 : IComparer<PlayerScore> { 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 如何映射到树

在抽象层面，SortedSet<T>的每个树节点保存一个 T，比较器决定节点位置和重复身份。它适用于唯一有序元素、范围查询、最小/最大值和集合运算。

SortedDictionary<TKey,TValue>的每个逻辑节点保存键值关联，树只按 key 比较，value 不参与定位。更新 value 不应改变树形；修改 key 则不是原位操作，而应删除旧键并插入新键。不同 .NET 版本可能通过内部集合、键值节点或共享辅助类型实现这一映射，不应在未固定 tag 时断言具体字段布局。

两者的典型公共成本边界如下：

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 Validate<T>(Node<T>? node, IComparer<T> 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 类型。

建议用性质测试生成操作序列，并以简单模型交叉验证：

1. 随机生成 Add、Remove、Contains，逐步与排序后的唯一 List 对照；
2. 覆盖升序、降序、相同键、锯齿序列，而不只用随机输入；
3. 每一步检查红黑不变式、中序严格递增和 Count；
4. 删除根、红叶、黑叶、仅有一个孩子和有两个孩子的节点；
5. 反复删除不存在的键，并删除到空再重新插入；
6. 用故意错误的 comparer 验证测试确实能捕获反对称或传递性破坏；
7. 对数值键覆盖最小值和最大值，防止减法比较器溢出。

测试 BCL 的 SortedSet/SortedDictionary 时不应反射私有颜色字段，因为这会绑定内部实现。应从公共契约验证：Add/Remove 返回值、重复判定、Contains/TryGetValue、枚举顺序、范围边界、自定义 comparer、空集合以及枚举失效。若要研究某版内部算法，则把源码 tag、commit、测试项目 TFM 和运行时版本一起记录，并在独立的源码研究测试中完成。

十、审查清单与结论

引入排序集合前可以逐项确认：

• 是否同时需要动态增删、唯一键、有序枚举或范围能力；
• comparer 是否稳定、自反、反对称、传递，并与领域“重复”定义一致；
• 所有参与比较的字段在入树后是否不可变；
• 是否错误依赖 value 参与 SortedDictionary 的位置；
• 热路径主要是点查、更新、范围扫描还是全量枚举；
• 节点分配与缓存局部性是否已在目标平台测量；
• 并发访问是否有外部同步方案；普通排序集合并非并发写容器；
• 持久化是否保存逻辑键值而非私有树形、颜色和字段；
• 关于特定 .NET 版本的实现说法是否有发行 tag 与测试佐证。

红黑树的核心不是背诵“左左、左右、四个删除 case”，而是理解两份契约同时成立：中序顺序由比较器维护，路径高度由颜色不变式约束。旋转保持顺序，变色和局部重构恢复黑高与红节点规则；二者共同给出最坏 O(log n) 的搜索路径。

SortedSet<T>将比较为零视作同一元素，SortedDictionary<TKey,TValue>将比较为零视作同一键。于是比较器实际上定义了集合身份，而不只是显示顺序。可变键和不传递比较器会从根上破坏树的语义。

最后要保持算法与实现的边界：本文的经典修复过程用于建立推理模型，不代表每个 .NET 版本逐行采用同一种控制流。阅读真实集合时固定 TFM、发行 tag 和源码文件；评价性能时固定负载与平台，不编造字节数或倍数。掌握这些边界后，后续剖析具体 SortedSet 源码才不会把偶然实现细节误当成红黑树本身。

下一篇：SortedSet：红黑树实现、不变式与版本边界