4. 红黑树基础：性质、旋转与内核实现

红黑树（Red-Black Tree）是 Linux 内核进程调度器 runqueue 中管理 CFS（完全公平调度器）就绪队列的核心数据结构。CFS 使用红黑树按进程的虚拟运行时间（vruntime）排序，实现 O(log n) 的插入、删除和查找操作。本章深入剖析红黑树的数学性质、旋转操作、插入与删除算法，并解读内核源码树中 rbtree.h 的实现细节。

4.1 红黑树的 5 条核心性质

红黑树是一棵自平衡的二叉搜索树，每个节点额外存储一个颜色位（红色或黑色）。它通过以下 5 条不变量保证树的高度不超过 2log₂(n+1)，从而确保最坏情况下的操作效率。

性质 4 和性质 5 是红黑树平衡性的核心保证。性质 4 限制了红色节点不能相邻，性质 5 强制所有路径的黑色节点数相等，两者共同约束树的高度。

4.2 旋转操作：左旋与右旋

旋转是红黑树维持平衡的基本操作，它改变节点之间的父子关系，但不破坏二叉搜索树的中序有序性。旋转分为左旋（Left Rotate）和右旋（Right Rotate），两者互为逆操作。

4.2.1 左旋（Left Rotate）

左旋以节点 x 为轴心，将 x 的右子节点 y 提升为父节点，x 下降为 y 的左子节点。y 原来的左子树变为 x 的右子树。

4.2.2 右旋（Right Rotate）

右旋以节点 y 为轴心，将 y 的左子节点 x 提升为父节点，y 下降为 x 的右子节点。x 原来的右子树变为 y 的左子树。

4.3 插入算法与修复流程

红黑树的插入分为两步：首先按照二叉搜索树的规则插入新节点（初始颜色为红色），然后通过修复操作恢复红黑树性质。插入可能违反性质 2（根为黑色）或性质 4（无连续红色），修复流程根据叔节点（uncle）的颜色分为三种情况。

4.3.1 插入步骤

1. BST 插入：从根开始，比较键值，找到插入位置，将新节点作为红色叶子插入。
2. 检查父节点颜色：如果父节点是黑色，插入完成（性质 4 未违反）。
3. 修复循环：当父节点是红色时，进入修复流程。

4.3.2 修复的三种情况

4.4 删除算法与修复流程

红黑树的删除比插入更复杂。删除节点后，如果被删除节点是黑色，则会破坏性质 5（黑高相等），需要调用修复函数 __rb_erase_color 来恢复平衡。删除修复根据兄弟节点（sibling）的颜色和子节点情况分为四种情况。

4.4.1 删除步骤

1. BST 删除：找到要删除的节点。如果节点有两个子节点，用后继节点（右子树最小节点）替换值，然后删除后继节点。
2. 记录颜色：记录实际被删除节点（或替换节点）的原始颜色。
3. 修复条件：如果被删除节点是黑色，则调用修复函数。

4.4.2 删除修复的四种情况

4.5 内核中的红黑树实现：rbtree.h

Linux 内核的红黑树实现位于 include/linux/rbtree.h 和 lib/rbtree.c。内核版本（如 6.x）对经典实现进行了优化，使用 rb_node 结构体和 rb_root 根节点结构。

4.5.1 核心数据结构

// include/linux/rbtree.h
struct rb_node {
    unsigned long  __rb_parent_color;  // 父节点指针与颜色位（最低位）
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

struct rb_root {
    struct rb_node *rb_node;  // 指向根节点，空树时为 NULL
};

内核将父节点指针和颜色位压缩在一个 unsigned long 字段中：最低位（bit 0）存储颜色（0 表示红色，1 表示黑色），高位存储父节点地址。这种技巧节省了内存，并利用对齐特性保证指针地址的最低位始终为 0。

4.5.2 关键宏与内联函数