红黑树
红黑树在 BST 节点上增加红、黑两种状态。颜色不参与键排序，而是限制树的失衡程度，让有序输入下的搜索和插入仍保持 O(log n)。
可以把每条向下路径看成有相同黑节点配额。新节点先设红色，不增加黑节点数。若父节点也红，就根据叔节点颜色修复；不是看到树偏斜就旋转。
本课涵盖插入与搜索。删除有额外的双黑修复过程，不在本课范围内。
红黑树的不变量
合法红黑树满足五项规则：
- 每个节点为红或黑。
- 根为黑。
- 缺失孩子称为 NIL 叶子，视为黑色。
- 红节点不能有红孩子。
- 从任意节点到其下方 NIL 叶子的所有路径，黑节点数相同。
工作台将最后一项称为黑高 BH：不计当前节点，计入末端 NIL。教材对起点是否计入有不同约定，只要全程一致即可。
禁止连续红节点，加上各路黑节点数相等，使最长根到叶路径不超过最短路径的两倍。含 n 个内部节点的树高不超过 2 log2(n + 1)。
Sorted stress 依次插入 10, 20, 30, 40, 50, 60, 70。红黑树边高度 3，普通 BST 高度 6。搜索 70 分别需要四次和七次探测。
插入修复如何工作
先执行普通 BST 插入：小值向左、大值向右，重复键不修改。新叶子设为红色。
新节点若是黑色，会只增加插入路径的黑节点数，破坏相等黑高。红色不改变黑节点计数，但可能与父节点形成红红相邻。首个节点例外：没有已有路径会失衡，无论红黑，它的两个 NIL 孩子都使黑高为 1；它仍按同一代码先红，最后按根规则染黑。
父节点为黑时，无红红冲突，停止修复。父为红时，检查叔节点：
- 叔为红：父、叔染黑，祖父染红，修复游标移到祖父。
- 叔为黑，包括 NIL：判断局部为直线还是折线，按情况旋转和改色。
红叔改色不改变局部黑高：原先经过黑祖父和红孩子，计一个黑节点；改色后经过红祖父与黑父或黑叔，仍计一个。指针无需移动，可能存在的红红冲突向上传播。
黑叔有四种形状：
| 情况 | 局部路径 | 修复 |
|---|---|---|
| LL | 左、左 | 改色，对祖父右旋 |
| RR | 右、右 | 改色，对祖父左旋 |
| LR | 左、右 | 先对父左旋，再改色并对祖父右旋 |
| RL | 右、左 | 先对父右旋，再改色并对祖父左旋 |
LL、RR 是外侧直线，一次祖父旋转完成结构修复。LR、RL 是内折三角，先转直，再做外侧修复。因此一次插入最多两次旋转；改色可继续向上，但不在每个祖先重复结构旋转。
三角预设包含错误路径对照：跳过第一次父旋转，会让旧祖父与新节点仍红红相邻。黑高可能看起来正常，因此不能只检查一条不变量。
旋转保持中序键序列。中间子树 T2 转移到仍满足大小关系的位置。修复结束时再次确保根为黑。
逐步演示
默认执行 insert 10, insert 20, insert 30, insert 15, insert 12, search 15。
- 插入 10：根位置为 NIL，先接红色 10；无父节点，不会形成红红边，两个 NIL 孩子使黑高为 1；最后按根规则染黑。
- 插入 20：从 10 向右，接红色 20。父 10 为黑，不检查叔，也不旋转。
- 插入 30：路径从 10 向右到 20，再向右。20、30 都红，叔为黑 NIL，属于 RR。20 染黑、10 染红，再对 10 左旋。黑根 20，红孩子 10、30。
- 插入 15：路径 20、左到 10、再右。父 10 红，叔 30 也红。把 10、30 染黑，祖父 20 染红，游标移到 20；它是根，最后再染黑。没有指针移动。
- 插入 12：路径 20、10、15、再左。父 15 红，叔为黑 NIL。相对祖父 10 是 RL：先对 15 右旋，把三角转直；再把 12 染黑、10 染红，对 10 左旋。
- 搜索 15：与 20 比较走左，与 12 比较走右，第三次探测命中 15。
最终根 20 为黑，左孩子 12 为黑，12 的孩子 10、15 为红，右孩子 30 为黑。所有红节点的孩子为黑，各条到 NIL 的路径黑高相同。
工作台用 z 表示修复游标，p 表示父，u 表示叔，g 表示祖父。节点填色始终表示持续的红黑状态；当前动作使用环和角色标签，红色不兼作错误提示。
何时使用红黑树
Java TreeMap 说明其使用红黑树。GNU libstdc++ 的 map、set、multimap、multiset 使用内部 _Rb_tree；C++ 标准要求相应的有序与对数性能，不要求所有实现都采用红黑树。Linux rbtree API 也用于高精度定时器等有序结构。
需要排序遍历、前驱后继、范围扫描，以及频繁更新的最坏 O(log n) 界时，可以选择红黑树。只按精确键查询时，哈希表通常更简单；磁盘索引或强调块、缓存行利用率时，宽分支的 B 树族常更合适。
AVL 的高度约束更紧，读多时可能有更短搜索路径。红黑树允许多一些高度，每次插入最多两次旋转，改色可向上传播。AVL 插入也只在一处做单旋或双旋，不能只用“旋转更少”作结论。选择还取决于删除、更新频率和需要的查找路径长度。
时间与空间复杂度
| 操作 | 时间 | 本实现额外空间 |
|---|---|---|
| 搜索 | O(log n) | 迭代 O(1) |
| 插入 | O(log n) | 用父指针迭代，O(1) |
| 单次旋转 | O(1) | O(1) |
BST 查找只走一条路径。红叔修复沿同一路径上移，黑叔最多两次旋转后结束。高度界保证总成本 O(log n)，树本身存储为 O(n)。
边界情况
- 空树：搜索零次节点探测到 NIL；首次插入最终成为黑根。
- 重复键：在相等处停止，形状、颜色、节点数和对照 BST 都不变。
- NIL 叔：按黑叔进入直线或三角判断。
- 修复中根变红：红叔改色可能临时使根红，最终根赋值恢复黑色。
- 空转移子树：
T2为 NIL 时旋转仍有效，没有非空孩子要搬移。 - 显示上限：最多 13 个节点，只保护标签和边的可读性。
常见错误
- 把 NIL 当无颜色。 缺失的叔也是黑叔，修复依赖这个定义。
- 新节点直接设黑。 会单独改变一条路径的黑高，先红更合适。
- 看到树高就旋转。 分支条件先看父、叔颜色，只有黑叔才判断形状。
- LR、RL 只做一次旋转。 先把三角转直，再对祖父修复。
- 随意同时改全部亲属颜色。 每次赋值有明确对象与顺序，动画分步展示中间状态。
- 丢失
T2。 它要移到降级支点旁合适的位置，不能丢键或破坏排序。 - 只检查黑高。 黑高相等仍可能有红红边，必须同时检查根色、红父规则与黑高。