红黑树Red-black tree

通过颜色约束和局部调整保持搜索树高度受控。

核心约束: 路径黑高相同，红节点不能有红孩子。
适用问题: 动态有序索引、范围查询与定时事件管理。
边界与取舍: 节点指针与旋转维护有成本；增强字段需随修改更新。

有效红黑树示意：浅红为红节点，其余为黑节点；省略 NIL 叶子。

常见操作#

n 为节点数，k 为范围查询输出数。

操作	时间复杂度	条件与说明
查找 / 插入 / 删除	$O(\log n)$	最坏界；需要维护红黑不变量，比较成本按 $O(1)$ 计算。
最小 / 最大 / 前驱 / 后继	$O(\log n)$	从根定位；Linux rb_root_cached 的最左节点读取可为 $O(1)$ 。
有序遍历	$O(n)$	完整迭代所有节点；单步后继的最坏成本与整段遍历的摊还成本不同。
范围枚举	$O(\log n+k)$	先找范围起点，再输出 k 个节点。

时间与空间#

时间复杂度: 查找 / 更新最坏 $O(\log n)$
存储空间: $O(n)$

增广字段需在链接和旋转后更新；维护成本取决于增广函数。

工程中的应用#

5 个案例 · 附源码

Linux Kernel·公平调度器v6.12

从有资格的任务中挑选最早截止时间

Linux 公平调度将 EEVDF 的资格条件与虚拟截止时间结合，用增强红黑树搜索候选任务。

EEVDF 红黑树

附源码片段 · 调度与资源分配

Linux Kernel·高精度定时器v6.12

按精确到期时间组织高精度定时器

hrtimer 通过 timerqueue 的红黑树维护到期顺序，并缓存最早到期节点。

附源码片段 · 调度与资源分配

nginx·事件循环release-1.26.3

找出事件循环的下一次超时

nginx 事件定时器以到期时间为键放入红黑树，事件循环读取最小键确定等待上限。

附源码片段 · 调度与资源分配

nginx·HTTP 限流模块release-1.26.3

用漏桶状态约束请求速率

limit_req 把漏桶计算、红黑树查状态与队列回收组合起来，按配置的 key 管理请求速率。

漏桶红黑树链表

附源码片段 · 通信与流量

Linux Kernel·公平调度器（Linux v6.5）v6.5

CFS：以加权虚拟运行时间组织公平调度

Linux v6.5 的 CFS 将可运行实体按 vruntime 放入红黑树，用加权运行时间作为公平性的基准。

CFS 公平调度红黑树

附源码片段 · 调度与资源分配

基础原理参考资料

Princeton · RedBlackBST有序操作和范围迭代的成本。

Linux 6.12 · Red-black Trees内核的侵入式红黑树、缓存最左节点和增广回调。