红黑树 (Red-Black Tree) — 5W1H故事与需求定义

Who（谁）

设计者：Rudolf Bayer（1972年提出"对称二叉B树"），由 Leonidas Guibas 和 Robert Sedgewick 于1978年命名为"红黑树"，并由 Thomas H. Cormen 等人在《算法导论》中系统化。
引用者：Donald E. Knuth 在 TAOCP 第3卷第6.2.3节中深入分析了自平衡二叉搜索树的理论基础。
使用者：操作系统（Linux内核CFS调度器、epoll事件管理）、C++ STL std::map/std::set、Java TreeMap/TreeSet，凡需要动态有序集合且要求最坏情况对数时间复杂度的场景均适用。

---

What（什么）

红黑树是一种自平衡二叉搜索树，每个节点标记为红色或黑色，通过旋转（左旋/右旋）和变色保持以下不变量：

1. 根黑：根节点始终为黑色。
2. 红节点子黑：红色节点的子节点必须是黑色（不存在连续红节点）。
3. 黑高一致：从任意节点到所有后代叶节点（NIL哨兵）的路径上，黑色节点数目相同。

上述约束保证树的高度 h ≤ 2·log₂(n+1)，从而所有基本操作（搜索、插入、删除）均在 O(log n) 时间内完成。

---

When（何时）

• 需要动态维护有序集合，且同时要求插入、删除、搜索的**最坏情况O(log n)**时间保证时。
• 需要在高并发环境（操作系统内核、数据库索引）中使用确定性性能的数据结构时。
• 对比AVL树：红黑树插入/删除旋转次数更少（均摊更快），适合写多读少场景。

---

Where（何处）

• 操作系统：Linux内核用红黑树管理进程调度（CFS）、内存映射区域（mm_struct）、文件系统节点。
• 标准库：C++ STL（std::map、std::set、std::multimap）；Java（TreeMap、TreeSet）。
• 数据库：部分数据库引擎的内存索引结构。
• 网络：epoll 事件管理使用红黑树追踪文件描述符。

---

Why（为何）

• BST退化问题：普通BST在顺序插入时退化为链表，操作退化为O(n)。
• AVL过于严格：AVL树要求左右子树高度差不超过1，插入/删除需更多旋转。
• 红黑树平衡了代价：以"宽松平衡"换取更少的旋转次数，在频繁修改的场景下性能更优。
• 最坏情况保证：不同于哈希表，红黑树在任意输入分布下均提供O(log n)保证，无哈希碰撞退化风险。

---

How（如何）

核心操作

操作	时间复杂度	说明
搜索	O(log n)	标准BST搜索，无需修复
插入	O(log n)	BST插入 → 着红色 → RB-INSERT-FIXUP
删除	O(log n)	BST删除 → RB-DELETE-FIXUP

插入修复三情形（以父节点是祖父左孩子为例）

情形	叔节点颜色	处理方式
情形1	红	父、叔变黑；祖父变红；z上移至祖父
情形2	黑，z是右孩子	左旋父节点，转为情形3
情形3	黑，z是左孩子	父变黑；祖父变红；右旋祖父

哨兵NIL节点

使用单一哨兵节点 t->nil 代替所有NULL叶节点，颜色为黑色，简化边界判断，避免大量空指针检查。

---

需求定义

功能需求

ID	需求描述
F1	rb_insert(t, key)：将整数 key 插入红黑树，忽略重复键
F2	rb_search(t, key)：搜索 key，找到返回节点指针，否则返回 NULL
F3	rb_delete(t, key)：删除 key 对应节点（若存在）
F4	rb_inorder(t, &size)：中序遍历，返回有序整数数组（调用者释放）
F5	rb_height(t)：返回树的高度
F6	rb_create() / rb_destroy(t)：创建和释放整棵树

性质约束

ID	约束描述
P1	根节点始终为黑色
P2	无两个连续的红色节点
P3	任意路径上黑色节点数相同（黑高一致）
P4	树高度 h ≤ 2·log₂(n+1)

非功能需求

• 所有操作时间复杂度为 O(log n)（最坏情况）
• 内存无泄漏：rb_destroy 释放所有节点和哨兵
• 使用 C99 标准，通过 gcc -std=c99 -Wall 无警告编译

---

验收标准

测试编号	测试描述	预期结果
TC1	插入键 1-10，搜索所有 10 个键	全部返回非 NULL 节点
TC2	搜索不存在的键（0, 11, 100）	全部返回 NULL
TC3	以乱序插入 1-10，执行中序遍历	得到有序序列 1,2,3,...,10
TC4	每次插入后检查根节点颜色	根始终为黑色（color == BLACK）
TC5	插入 10 个键后测量树高度	h ≤ 2·log₂(11) ≈ 6.92，即 h ≤ 6
TC6	删除偶数键（2,4,6,8,10）后搜索	奇数键可找到，偶数键返回 NULL