2. 红黑树基础回顾：红黑树的5条性质、节点颜色与平衡条件
红黑树（Red-Black Tree）是一种自平衡的二叉查找树，由 Rudolf Bayer 于 1972 年发明。Linux 内核进程调度器中的 CFS（完全公平调度器）使用红黑树来组织就绪队列中的进程节点，以实现高效的插入、删除和查找操作。理解红黑树的 5 条核心性质是掌握内核调度算法的基础。
2.1 红黑树的 5 条性质
红黑树通过为每个节点赋予红色或黑色，并约束从根到叶子的路径中颜色的分布，来保证树的大致平衡。以下 5 条性质是红黑树的定义性规则：
| 编号 | 性质描述 | 违反后果 |
|---|---|---|
| 性质 1 | 每个节点要么是红色，要么是黑色。 | 颜色属性不合法，树结构无法定义。 |
| 性质 2 | 根节点必须是黑色。 | 可能导致路径间黑色节点数不一致。 |
| 性质 3 | 每个叶子节点（NIL 空节点）都是黑色。 | 简化边界条件失效，插入/删除修复复杂化。 |
| 性质 4 | 如果一个节点是红色，则它的两个子节点都是黑色（即红色节点不能相邻）。 | 产生连续红色节点，破坏平衡约束。 |
| 性质 5 | 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（黑色高度相等）。 | 树严重失衡，查找性能退化。 |
struct sched_entity）。性质 5 保证了从根到任意叶子节点的路径长度差异不超过 2 倍，从而确保进程查找的时间复杂度稳定在 O(log n)。
2.2 节点颜色与平衡条件
红黑树的平衡不是严格的左右子树高度相等（如 AVL 树），而是通过颜色约束实现一种“近似平衡”。平衡条件由性质 4 和性质 5 共同保证：
- 红色节点约束： 红色节点不能连续出现，这意味着红色节点必须被黑色节点隔开。红色节点只作为“填充”存在，不增加路径的黑色高度。
- 黑色高度相等： 从根到任意叶子路径上的黑色节点数相同，这个数值称为该树的黑高（black-height）。黑高决定了树的最大深度上限。
由性质 4 和性质 5 可以推导出红黑树的一个重要平衡保证：一棵有 n 个内部节点的红黑树，其高度最多为 2log₂(n+1)。这意味着查找、插入、删除的最坏时间复杂度均为 O(log n)。
2.3 红黑树节点结构（内核视角）
在 Linux 内核中，红黑树的节点由 struct rb_node 表示，不直接存储颜色，而是通过指针的低位编码来标记颜色，以节省内存。以下是内核中红黑树节点的简化定义：
struct rb_node {
unsigned long __rb_parent_color; // 父节点指针 + 颜色位（最低位）
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
// 颜色通过宏操作：
#define RB_RED 0
#define RB_BLACK 1
#define rb_color(r) ((r)->__rb_parent_color & 1)
#define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0)
#define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0)rb_node 必须按 long 对齐（通常 4 或 8 字节），否则颜色位无法正常工作。在用户态实现红黑树时，通常直接使用单独的 int color 字段。
2.4 红黑树平衡条件示意图
下图展示了一棵合法的红黑树，标注了节点颜色、NIL 叶子节点以及黑色高度。注意红色节点（如 8 和 17）的子节点均为黑色，且从根到每个 NIL 叶子的黑色节点数均为 2。
2.5 红黑树与 AVL 树的对比
红黑树与 AVL 树都是自平衡二叉查找树，但平衡策略不同，导致应用场景有所差异。下表总结了关键区别：
| 对比维度 | 红黑树 | AVL 树 |
|---|---|---|
| 平衡条件 | 颜色约束 + 黑色高度相等 | 左右子树高度差 ≤ 1 |
| 平衡严格程度 | 较宽松（近似平衡） | 严格平衡 |
| 查找时间复杂度 | O(log n) | O(log n) |
| 插入/删除旋转次数 | 最多 2 次旋转（插入）/ 3 次旋转（删除） | 最多 O(log n) 次旋转 |
| 内存开销 | 每个节点 1 bit 颜色（内核中嵌入指针） | 每个节点存储高度（通常 int） |
| 典型应用 | Linux 内核 CFS 调度器、Java TreeMap、C++ std::map | 数据库索引、需要频繁查找的场景 |
2.6 红黑树平衡的直观理解
红黑树的平衡可以理解为一种“红黑交替”的约束：红色节点必须被黑色节点隔开，且所有路径的黑色节点数相同。这种约束保证了树的高度不会超过 2log₂(n+1)，即最坏情况下查找路径长度是理想情况（完全平衡树）的 2 倍。对于内核调度器来说，这种近似平衡已经足够优秀，因为 O(log n) 的查找时间在进程数量达到数万时仍然非常快。