在 Linux 内核源码中搜索 rb_node，你能找到上千处引用。CFS 进程调度、高精度定时器（hrtimer）、虚拟内存区域管理（VMA）、ext4 文件系统的 extent 管理——这些核心模块无一例外地选择了红黑树。
很多嵌入式工程师对红黑树的印象停留在“数据结构课上最难的那一章”，觉得它是面试题专用。但事实上，只要你的项目涉及有序数据的频繁插入、删除和查找，红黑树几乎都是最优解。在 云栈社区 的算法与数据结构板块，关于高效数据结构的讨论一直是热点。
这篇文章从原理入手，讲清楚红黑树为什么快、怎么保持平衡，然后结合嵌入式的真实场景，说说它到底怎么用。
先搞明白：为什么普通二叉搜索树不够用
二叉搜索树（BST）的规则很简单——左子节点比父节点小，右子节点比父节点大。查找、插入、删除的平均时间复杂度都是 O(log n)，看起来挺完美。
但“平均”这两个字藏着坑。
如果插入的数据本身就是有序的——比如按时间递增插入定时器到期时间——BST 就会退化成一条链表，所有操作的时间复杂度退化到 O(n)。
在嵌入式系统中，这种退化是致命的。定时器管理、任务调度这些模块对时间敏感，一旦数据结构的性能不稳定，系统的实时性就没法保证。
所以我们需要一种 自平衡 的二叉搜索树，在任何插入顺序下都能保持树的高度在 O(log n) 范围内。红黑树就是解决这个问题最工程化的方案。
红黑树的五条铁律
红黑树本质上还是一棵二叉搜索树，只不过每个节点多了一个“颜色”属性（红或黑），并通过以下五条性质来约束树的形状：
性质 4 和性质 5 是核心。它们共同保证了一件事：树中最长路径不超过最短路径的 2 倍。
为什么？最短路径是全黑节点，最长路径是红黑交替。由于黑高一致，最长路径上的黑节点数等于最短路径，而红节点最多和黑节点一样多（因为不能连续红），所以最长路径 ≤ 2 × 最短路径。
这种约束带来的好处是：对于 n 个节点的红黑树，高度最多为 2log₂(n+1)。查找、插入、删除的最坏时间复杂度都是 O(log n)，性能有保底。
插入时如何保持平衡：变色与旋转
新插入的节点默认是 红色。为什么不是黑色？因为插入黑色节点必然破坏性质 5（黑高一致），而插入红色节点只 可能 破坏性质 4（连续红节点）。修复一个性质比修复另一个简单得多。
插入后，如果父节点是黑色，万事大吉，不需要任何调整。问题出在父节点也是红色的时候——违反了“不能连续红”的规则。这时需要通过 变色 和 旋转 来修复。
旋转操作图解
旋转是红黑树维持平衡的核心手段，分为左旋和右旋：
插入修复的三种情况
关键点在于：每次修复最多涉及 2 次旋转和 O(log n) 次变色，整体插入操作的时间复杂度仍然是 O(log n)。
红黑树 vs AVL树：为什么内核选了红黑树
既然都是自平衡 BST，为什么 Linux 内核选红黑树而不是 AVL 树？
差距出在 删除操作 上。AVL 树删除后可能需要从删除点一路旋转到根节点，而红黑树最多 3 次旋转就能搞定。
在嵌入式系统中，定时器到期要删除、任务结束要移除、内存区域要释放——删除操作非常频繁。红黑树在删除时的稳定表现，使它更适合这类场景。
一句话总结：读多写少用 AVL，读写均衡用红黑树。嵌入式内核场景大多属于后者。
嵌入式中红黑树的四大应用场景
场景一：定时器管理
这是红黑树最经典的嵌入式应用。Linux 内核的高精度定时器（hrtimer）就用红黑树来组织所有待触发的定时器。
思路很直接：以到期时间作为 key，每个定时器作为一个节点插入红黑树。需要触发时，取最左节点（到期时间最小）就行，O(log n) 插入，O(1) 取最小值。
对比用有序链表管理定时器，插入是 O(n)。当系统中同时存在几百个定时器时，红黑树的优势就非常明显了。
场景二：进程/任务调度
Linux 的 CFS（完全公平调度器）用红黑树管理所有可运行的进程。每个进程的虚拟运行时间（vruntime）作为 key，vruntime 最小的进程（最左节点）获得 CPU 时间。
在 RTOS 中也可以借鉴这个思路。如果你的调度策略不是简单的固定优先级，而是需要动态权重或公平调度，红黑树是比优先级队列更灵活的选择。
场景三：内存管理
嵌入式系统中，如果需要管理大量不定长的内存块，红黑树可以用来维护空闲块列表。以内存块的起始地址或大小作为 key，分配和释放时快速找到最合适的块。
Linux 内核用红黑树管理进程的虚拟内存区域（VMA），每个 vm_area_struct 按地址范围组织在红黑树中。当发生缺页中断时，能在 O(log n) 时间内定位到对应的 VMA。
场景四：设备资源索引
当系统中有大量设备或资源需要按 ID 快速检索时，红黑树比哈希表更可控。哈希表在最坏情况下会退化到 O(n)，而且需要预估容量、处理扩容，在内存受限的嵌入式环境中不太友好。红黑树的内存开销可预测（每个节点固定 3 个指针 + 1 个颜色位），性能有保底。
实战：用红黑树实现一个定时器管理器
光讲原理不写代码等于白说。下面用 Linux 内核风格的红黑树接口，实现一个嵌入式定时器管理器。
节点定义
Linux 内核的红黑树采用 侵入式设计 —— 把 rb_node 嵌入到你自己的数据结构中，而不是把数据塞进红黑树的通用节点里。这样做的好处是零额外内存分配，对嵌入式很友好。
#include "rbtree.h" /* Linux内核风格的红黑树头文件 */
/* 定时器节点 */
struct timer_node {
struct rb_node rb; /* 红黑树节点，嵌入到结构体中 */
uint32_t expire_ms; /* 到期时间（ms） */
void (*callback)(void *arg); /* 回调函数 */
void *arg; /* 回调参数 */
};
/* 定时器管理器 */
struct timer_manager {
struct rb_root root; /* 红黑树根节点 */
uint32_t count; /* 定时器数量 */
};
/* 初始化 */
void timer_manager_init(struct timer_manager *mgr)
{
mgr->root = RB_ROOT; /* 宏展开为 { NULL } */
mgr->count = 0;
}
插入操作
插入的核心逻辑就两步：先按 BST 规则找到插入位置，再调用 rb_insert_color 完成红黑树的平衡修复。
int timer_add(struct timer_manager *mgr, struct timer_node *timer)
{
struct rb_node **link = &mgr->root.rb_node;
struct rb_node *parent = NULL;
uint32_t expire = timer->expire_ms;
/* 第一步：BST查找插入位置 */
while (*link) {
struct timer_node *entry;
parent = *link;
entry = rb_entry(parent, struct timer_node, rb);
if (expire < entry->expire_ms)
link = &parent->rb_left;
else
link = &parent->rb_right;
}
/* 第二步：插入节点并修复红黑树性质 */
rb_link_node(&timer->rb, parent, link);
rb_insert_color(&timer->rb, &mgr->root);
mgr->count++;
return 0;
}
取最近到期的定时器
沿左子树一路走到底，就是到期时间最小的节点：
struct timer_node *timer_nearest(struct timer_manager *mgr)
{
struct rb_node *node = mgr->root.rb_node;
if (!node)
return NULL;
while (node->rb_left)
node = node->rb_left;
return rb_entry(node, struct timer_node, rb);
}
删除操作
定时器到期后，从红黑树中删除：
void timer_remove(struct timer_manager *mgr, struct timer_node *timer)
{
rb_erase(&timer->rb, &mgr->root);
mgr->count--;
}
定时器tick处理
在系统 tick 中断或主循环中调用：
void timer_tick(struct timer_manager *mgr, uint32_t now_ms)
{
struct timer_node *timer;
while ((timer = timer_nearest(mgr)) != NULL) {
if (timer->expire_ms > now_ms)
break; /* 最近的都没到期，后面的更不用看了 */
timer_remove(mgr, timer);
timer->callback(timer->arg); /* 执行回调 */
}
}
这个实现不到 100 行代码，但已经具备了生产级定时器管理器的核心能力。红黑树的插入和删除帮你把性能锁定在 O(log n)，不管定时器数量怎么增长，tick 处理的延迟都可控。
什么时候该用红黑树，什么时候不该
红黑树不是万能的。在决定是否引入之前，先问自己三个问题：
1. 数据量有多大？
如果节点数长期不超过二三十个，有序链表的 O(n) 插入在绝对时间上也就几微秒，没必要上红黑树。红黑树的优势在数据量上百之后才真正体现。
2. 需要有序遍历吗？
如果只需要按 key 查找，哈希表的 O(1) 平均查找比红黑树的 O(log n) 更快。但如果你需要“找最小值”“范围查询”“按序遍历”这类有序操作，哈希表做不到，红黑树才是正确选择。
3. 能承受多少内存开销？
每个红黑树节点需要 3 个指针（左、右、父）加 1 个颜色位。在 32 位系统上大约 13 字节，64 位系统上约 25 字节。如果你的 MCU 只有几 KB RAM，要慎重评估。
写在最后
红黑树看起来复杂，但拆开来看，核心就是那五条性质加上旋转变色两个操作。理解了“为什么这么设计”，实际使用反而很简单——Linux 内核已经把旋转和变色的逻辑封装好了，你只需要写 BST 的查找逻辑和定义自己的数据结构。
回过头来看这篇文章涉及的内容：侵入式数据结构、回调函数封装、管理器模式——这些其实都是 设计模式 在嵌入式 C 中的具体体现。红黑树的侵入式节点设计体现了“组合优于继承”的思想，定时器管理器的封装体现了“单一职责”原则，回调机制则是观察者模式的雏形。
如果你觉得这些概念似曾相识但又说不清楚，建议系统地学习一下设计模式。不是 Java 那套 23 种经典模式的全文背诵，而是搞清楚这些模式在嵌入式 C 中怎么落地、怎么用。掌握了 设计模式，你看内核代码、写模块架构时会顺畅很多，很多以前觉得“这代码怎么写得这么绕”的地方，突然就能看懂它为什么这么设计了。
发表于 4 天前
|
查看: 23|
回复: 0
