3. 红黑树数据结构基础

红黑树（Red-Black Tree）是 CFS 调度器选择就绪队列的核心数据结构。它是一棵自平衡的二叉查找树，能够在 O(log n) 时间内完成插入、删除和查找操作。理解红黑树的 5 大性质、旋转操作和颜色规则，是掌握 CFS 调度器“按虚拟时间排序”机制的前提。

3.1 红黑树 5 大性质

红黑树通过以下 5 条性质保证树的高度不超过 2log₂(n+1)，从而确保 O(log n) 的时间复杂度：

3.2 左旋与右旋操作

旋转是红黑树维持平衡的基本操作，在不破坏二叉查找树性质的前提下，改变节点间的父子关系。CFS 调度器在插入新进程或更新进程虚拟时间后，通过旋转修复红黑树。

3.2.1 左旋（Left Rotation）

左旋将节点 x 的右子节点 y 提升为 x 的父节点，x 成为 y 的左子节点。适用于右子树过重的情况。

/* 左旋伪代码 */
LEFT-ROTATE(T, x)
    y = x.right                // 设置 y
    x.right = y.left           // y 的左子树变为 x 的右子树
    if y.left != T.nil
        y.left.parent = x
    y.parent = x.parent        // 连接 x 的父节点到 y
    if x.parent == T.nil
        T.root = y
    else if x == x.parent.left
        x.parent.left = y
    else
        x.parent.right = y
    y.left = x                 // 将 x 放在 y 的左边
    x.parent = y

3.2.2 右旋（Right Rotation）

右旋是左旋的对称操作，将节点 y 的左子节点 x 提升为 y 的父节点，y 成为 x 的右子节点。适用于左子树过重的情况。

/* 右旋伪代码 */
RIGHT-ROTATE(T, y)
    x = y.left                 // 设置 x
    y.left = x.right           // x 的右子树变为 y 的左子树
    if x.right != T.nil
        x.right.parent = y
    x.parent = y.parent        // 连接 y 的父节点到 x
    if y.parent == T.nil
        T.root = x
    else if y == y.parent.left
        y.parent.left = x
    else
        y.parent.right = x
    x.right = y                // 将 y 放在 x 的右边
    y.parent = x

3.3 节点颜色规则与修复流程

红黑树的颜色规则是平衡的核心机制。插入新节点时，默认将节点染为红色，然后通过修复流程消除红-红冲突。删除节点时，如果删除的是黑色节点，会破坏黑高，需要通过修复恢复性质 5。

3.3.1 插入修复的 3 种情况

3.3.2 删除修复的核心思想

删除黑色节点会导致经过该节点的路径黑高减 1。修复策略是：将“额外黑色”向上传递，直到遇到红色节点（将其染黑）或到达根节点。删除修复涉及 4 种情况，核心操作包括旋转和变色。

3.4 红黑树在 CFS 中的角色总结