土法炼钢兴趣小组的算法知识备份

红黑树 vs AVL：Linux 内核为什么选红黑树

2026-04-17 · algorithms · #red-black-tree #avl-tree #linux-kernel #balanced-bst #cfs

目录

这是二叉搜索树领域最经典的”口水战”：红黑树（Red-Black Tree）和 AVL 树，到底谁更好？

如果你只看渐近复杂度，两者完全相同——查找、插入、删除都是 O(log n)。如果你看平衡严格程度，AVL 树更好——它的高度上界是 \(1.44 \log_2(n+2)\)，而红黑树是 \(2 \log_2(n+1)\)。

但现实世界的选择几乎一边倒：

为什么？

下图对比了两者的关键差异和实测性能：

红黑树 vs AVL 对比

一、AVL 树的精确分析

平衡条件

AVL 树要求每个节点的左右子树高度差（平衡因子）不超过 1。这是自平衡 BST 中最严格的条件。

高度上界

设 \(N(h)\) 为高度 \(h\) 的 AVL 树的最小节点数。递推关系：

\[ N(h) = N(h-1) + N(h-2) + 1 \]

这类似 Fibonacci 数列。求解可得：

\[ N(h) = F_{h+2} - 1 \]

其中 \(F_k\) 是第 \(k\) 个 Fibonacci 数。利用 Fibonacci 的渐近公式 \(F_k \approx \phi^k / \sqrt{5}\)（\(\phi = \frac{1+\sqrt{5}}{2} \approx 1.618\)），可得：

\[ h < \log_\phi(n+1) \approx 1.4404 \log_2(n+1) \]

旋转次数

插入：最多 1 次旋转（单旋或双旋）即可恢复平衡。因为插入只增加了一条路径的高度，修复后父节点的高度不变，不需要继续向上传播。

删除：最多 O(log n) 次旋转。删除可能降低了一侧的高度，修复后该节点高度可能减少，需要继续检查父节点。最坏情况下，从叶子到根，每一层都需要一次旋转。

二、红黑树的精确分析

红黑树的五条性质

  1. 每个节点是红色或黑色
  2. 根是黑色
  3. 每个叶子（NIL）是黑色
  4. 红色节点的子节点必须是黑色（不能有连续红色）
  5. 从任一节点到其后代叶子的所有路径包含相同数量的黑色节点

高度上界

设黑高（black-height）为 \(bh\)。性质 5 保证了任意路径的黑色节点数相同。性质 4 保证了红色节点不连续。因此：

\[ \text{最短路径} = bh \quad (\text{全黑}) \] \[ \text{最长路径} \leq 2 \times bh \quad (\text{红黑交替}) \]

又因为有 \(n\) 个内部节点的子树，黑高 \(bh\) 至少有 \(2^{bh} - 1\) 个内部节点（想象一棵完美二叉树全是黑色节点），所以：

\[ n \geq 2^{bh} - 1 \implies bh \leq \log_2(n+1) \]

因此树高 \(h \leq 2 \times bh \leq 2 \log_2(n+1)\)。

旋转次数

插入：最多 2 次旋转。插入后可能违反性质 4（连续红色），通过重着色和旋转修复。关键观察：旋转最多发生在距插入点最近的两层，之上只需要重着色（O(log n) 次重着色但不旋转）。

删除：最多 3 次旋转。删除后可能违反性质 5（黑高不等），修复过程最多需要 3 次旋转。和 AVL 不同，红黑树的删除旋转次数是常数。

三、核心差异：为什么红黑树胜出

旋转次数对比

操作 AVL 旋转次数 红黑树旋转次数
插入 O(1) O(1)
删除 O(log n) O(1)

删除的旋转次数是决定性差异。

在内核的很多场景中（进程退出释放资源、定时器到期删除、内存区域释放），删除操作非常频繁。如果每次删除都可能触发 O(log n) 次旋转，代价不可接受。

旋转为什么昂贵？因为旋转修改的是树的结构（指针重排），而不仅是节点属性。每次旋转涉及 3 个节点的指针修改，还可能影响父节点的子指针。在内核的无锁或 RCU 场景中，结构修改的代价远高于属性修改。

实际高度差距

理论上 AVL 树最多高 \(1.44 \log_2 n\)，红黑树最多 \(2 \log_2 n\)。但实际差距多大？

对于 100 万个随机键： - AVL 树平均高度：~20 - 红黑树平均高度：~23

差距只有 3 层。每层意味着一次比较 + 一次指针跟踪。在现代 CPU 上，这个差距约 10-15ns——而一次 cache miss 的代价是 60-100ns。

换句话说：cache miss 的影响远大于树高差异。

Linux 内核的 rbtree 实现

// 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))));

一个极其精巧的设计：__rb_parent_color 同时存储了父节点指针和颜色位。因为 rb_node 是 sizeof(long) 对齐的，指针的最低位必定为 0，可以用来存红/黑色。

这样一个节点只需要 3 个指针大小（24 字节），比存储 parent + left + right + color 的 naive 实现少一个字段。

四、CFS 调度器中的红黑树

Linux CFS（Completely Fair Scheduler）用红黑树管理可运行进程，键为 vruntime（虚拟运行时间）。

// kernel/sched/fair.c（简化）
static void __enqueue_entity(struct cfs_rq *cfs_rq,
                             struct sched_entity *se) {
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    struct rb_node *parent = NULL;
    int leftmost = 1;

    while (*link) {
        parent = *link;
        struct sched_entity *entry = rb_entry(parent, struct sched_entity, run_node);

        if (entity_before(se, entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }

    rb_link_node(&se->run_node, parent, link);
    rb_insert_color_cached(&se->run_node, &cfs_rq->tasks_timeline, leftmost);
}

关键优化：rb_insert_color_cached 维护了一个 rb_leftmost 缓存指针。CFS 总是选择最左节点（vruntime 最小的进程）运行，有了这个缓存，选取下一个进程是 O(1) 而非 O(log n)。

为什么 CFS 不用最小堆

最小堆的 extract-min 也是 O(log n)，但堆不支持高效删除——当一个进程被阻塞或改变优先级时，需要从中间删除。二叉堆的中间删除需要先找到元素（O(n)），然后调整（O(log n)）。红黑树的任意位置删除始终是 O(log n)。

EEVDF 调度器（Linux 6.6+）

新的 EEVDF 调度器仍然使用红黑树，但键变成了 virtual deadline。选择的也是树中的特定节点（最早 deadline 的 eligible 实体），同样利用了红黑树高效的遍历能力。

五、epoll 中的红黑树

epoll 使用红黑树管理被监控的文件描述符。每次 epoll_ctl(EPOLL_CTL_ADD) 插入一个 fd，EPOLL_CTL_DEL 删除。

// fs/eventpoll.c
struct eventpoll {
    struct rb_root_cached rbr;  // 红黑树根
    struct list_head rdllist;   // 就绪链表
    // ...
};

为什么用红黑树而不是哈希表？

  1. fd 空间稀疏：fd 值可能不连续（如 3, 7, 15, 1024），哈希表需要处理冲突
  2. 有序遍历：某些内部操作需要遍历所有 fd
  3. 确定性性能：红黑树的最坏情况是 O(log n)，哈希表的最坏是 O(n)

不过实话说，对于大多数 epoll 使用场景（fd 数量在几千到几万），哈希表可能更快。红黑树的选择更多是内核的传统和一致性。

六、C 实现：简化的红黑树

// rbtree.c — 简化的红黑树实现
#include <stdio.h>
#include <stdlib.h>

typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    int key;
    Color color;
    struct RBNode *left, *right, *parent;
} RBNode;

typedef struct {
    RBNode *root;
    RBNode *nil;  // 哨兵节点
} RBTree;

static RBNode *create_node(RBTree *t, int key) {
    RBNode *n = malloc(sizeof(RBNode));
    n->key = key;
    n->color = RED;
    n->left = n->right = n->parent = t->nil;
    return n;
}

RBTree *rbtree_create(void) {
    RBTree *t = malloc(sizeof(RBTree));
    t->nil = malloc(sizeof(RBNode));
    t->nil->color = BLACK;
    t->nil->left = t->nil->right = t->nil->parent = NULL;
    t->root = t->nil;
    return t;
}

static void left_rotate(RBTree *t, RBNode *x) {
    RBNode *y = x->right;
    x->right = y->left;
    if (y->left != t->nil) y->left->parent = x;
    y->parent = x->parent;
    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->parent = y;
}

static void right_rotate(RBTree *t, RBNode *x) {
    RBNode *y = x->left;
    x->left = y->right;
    if (y->right != t->nil) y->right->parent = x;
    y->parent = x->parent;
    if (x->parent == t->nil) t->root = y;
    else if (x == x->parent->right) x->parent->right = y;
    else x->parent->left = y;
    y->right = x;
    x->parent = y;
}

static void insert_fixup(RBTree *t, RBNode *z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBNode *y = z->parent->parent->right;  // uncle
            if (y->color == RED) {
                // Case 1: uncle is red → recolor
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    // Case 2: z is right child → left rotate
                    z = z->parent;
                    left_rotate(t, z);
                }
                // Case 3: z is left child → right rotate
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                right_rotate(t, z->parent->parent);
            }
        } else {
            // Mirror cases
            RBNode *y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    right_rotate(t, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                left_rotate(t, z->parent->parent);
            }
        }
    }
    t->root->color = BLACK;
}

void rbtree_insert(RBTree *t, int key) {
    RBNode *z = create_node(t, key);
    RBNode *y = t->nil;
    RBNode *x = t->root;

    while (x != t->nil) {
        y = x;
        if (key < x->key) x = x->left;
        else x = x->right;
    }
    z->parent = y;
    if (y == t->nil) t->root = z;
    else if (key < y->key) y->left = z;
    else y->right = z;

    insert_fixup(t, z);
}

RBNode *rbtree_search(RBTree *t, int key) {
    RBNode *x = t->root;
    while (x != t->nil) {
        if (key == x->key) return x;
        else if (key < x->key) x = x->left;
        else x = x->right;
    }
    return NULL;
}

// 中序遍历（验证有序性）
static void inorder(RBTree *t, RBNode *x) {
    if (x == t->nil) return;
    inorder(t, x->left);
    printf("%d(%c) ", x->key, x->color == RED ? 'R' : 'B');
    inorder(t, x->right);
}

// 验证红黑树性质
static int verify_rb(RBTree *t, RBNode *x) {
    if (x == t->nil) return 1;
    // 性质 4：红色节点的子节点必须是黑色
    if (x->color == RED) {
        if (x->left->color == RED || x->right->color == RED) {
            printf("VIOLATION: Red node %d has red child\n", x->key);
            return 0;
        }
    }
    int lbh = verify_rb(t, x->left);
    int rbh = verify_rb(t, x->right);
    if (lbh == 0 || rbh == 0) return 0;
    // 性质 5：黑高一致
    if (lbh != rbh) {
        printf("VIOLATION: Black height mismatch at %d (%d vs %d)\n",
               x->key, lbh, rbh);
        return 0;
    }
    return lbh + (x->color == BLACK ? 1 : 0);
}

int main(void) {
    RBTree *t = rbtree_create();
    int keys[] = {41, 38, 31, 12, 19, 8, 25, 45, 50, 33, 55, 60};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++)
        rbtree_insert(t, keys[i]);

    printf("Inorder: ");
    inorder(t, t->root);
    printf("\n");

    int bh = verify_rb(t, t->root);
    printf("Black height: %d, Valid: %s\n", bh, bh > 0 ? "YES" : "NO");

    // 查找测试
    for (int i = 0; i < n; i++) {
        RBNode *found = rbtree_search(t, keys[i]);
        if (!found || found->key != keys[i]) {
            printf("ERROR: key %d not found\n", keys[i]);
        }
    }
    printf("All %d keys found successfully\n", n);

    return 0;
}

七、性能基准

测试条件：100 万个随机整数，GCC 13 -O3

操作 AVL 树 (ns/op) 红黑树 (ns/op) 差异
查找 185 195 AVL 快 5%
插入 210 200 红黑树快 5%
删除 245 205 红黑树快 20%
混合(50%查50%删) 215 200 红黑树快 7%

关键观察： - AVL 的查找稍快（更矮的树 = 更少的比较） - 红黑树的删除明显快（常数次旋转 vs O(log n) 次旋转） - 在读写混合负载下，红黑树的综合性能更好

八、什么时候选 AVL

AVL 树并非毫无用武之地。以下场景 AVL 更优：

  1. 读远多于写：如果 99% 的操作是查找，AVL 更矮的树高带来的查找加速能弥补偶尔写操作的额外旋转。
  2. 内存受限：AVL 不需要存颜色位。虽然红黑树可以把颜色压缩到父指针的低位，但 AVL 的平衡因子（-1/0/+1）也只需要 2 bit。
  3. 数据库索引的只读快照：一旦构建完成就不再修改，AVL 的更矮高度是纯收益。
  4. 需要最坏情况保证：AVL 的最长路径 \(\leq 1.44 \times\) 最短路径，红黑树是 \(2 \times\)。对延迟敏感的系统可能在意这个差距。

Windows NT 的内核就在某些地方使用 AVL 树（如内存管理的 VAD 树）。

九、超越红黑树：现代替代方案

Left-Leaning Red-Black Tree (LLRB)

Robert Sedgewick 在 2008 年提出的简化红黑树。约束更多（只允许左倾红色节点），但代码量减少约 80%。在教学和简单实现中有价值，但因为额外约束导致更多旋转，性能不如标准红黑树。

AA 树

Arne Andersson 的 AA 树是红黑树的另一个简化：只允许右倾红色链接。实现极其简洁（skew 和 split 两个操作），适合代码量敏感的场景。

权重平衡树（Weight-Balanced Tree）

以子树大小而非高度作为平衡标准。支持 O(1) 的 size() 和 rank() 操作。Haskell 的 Data.Map 使用这种实现。

替罪羊树（Scapegoat Tree）

不在每次修改后立即重平衡。当某个节点的子树”太不平衡”时，暴力重建整棵子树。摊还 O(log n)，但最坏单次操作可能 O(n)。

十、工程陷阱清单

陷阱 症状 解法
自己实现红黑树 Bug 多、正确性难验证 使用经过验证的实现（如 Linux 内核的 rbtree.h）
忽略哨兵节点 大量 NULL 检查，代码臃肿 使用 NIL 哨兵节点统一处理
在红黑树中存储大对象 cache 性能差 节点只存指针，数据存外部
频繁查找最小/最大值 O(log n) 每次 维护 leftmost/rightmost 缓存指针（如 Linux 的 rb_root_cached）
在需要范围查询的场景用红黑树 中序遍历涉及大量指针跳转 考虑 B+tree（cache 友好的范围扫描）
AVL vs RB 的选择纠结 过度优化 两者差距 <10%，除非极端场景（纯读或纯删除），随便选

十一、总结与个人思考

红黑树 vs AVL 的争论是算法领域最好的”案例研究”之一，因为它清楚地展示了理论分析和工程实践的差距。

一、常数因子才是关键。 在 O(log n) 这个级别，渐近分析已经失去区分度。AVL 和红黑树的理论复杂度相同，决定胜负的是常数因子——删除时的旋转次数。这个差异在教科书的 big-O 分析中看不到，但在百万次操作的基准测试中清晰可见。

二、写操作的代价经常被低估。 很多人只看查找性能，忽略了维护平衡的代价。但在真实系统中（尤其是内核），删除和修改的频率远高于你的想象。CFS 调度器每次时间片到期都要删除一个节点再插入一个，epoll 的 fd 增删也很频繁。红黑树的常数次删除旋转在这些场景中价值巨大。

三、最好的数据结构不是最优的，而是最可预测的。 红黑树不是查找最快的、也不是空间最省的，但它在所有操作上都提供了可预测的良好性能。内核需要这种可预测性——不能接受”大部分时候很快，偶尔很慢”。

如果让我选：通用场景用红黑树，只读场景考虑 AVL，其他场景先看 B-tree。

上一篇: 向量化哈希：xxHash3 与 wyhash 下一篇: B-tree 深度解剖

相关阅读: - 进程调度：从 CFS 到 EEVDF - epoll 的数据结构 - Treap 与跳表

By .