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

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

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

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

• Linux 内核：CFS 调度器、epoll、ext4 extent tree、内存管理——全用红黑树
• Java：TreeMap、TreeSet——红黑树
• C++ STL：std::map、std::set——大部分实现用红黑树
• Nginx：定时器管理——红黑树

为什么？答案不在 big-O 里，它藏在旋转次数的精确分析和系统编程的工程约束中。

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

一、平衡二叉搜索树的必要性

从 BST 退化到链表谈起

普通二叉搜索树（BST）的形态完全取决于插入顺序。如果我们按 1, 2, 3, 4, 5 的顺序插入，得到的是一条右偏链表——查找、插入、删除全部退化到 O(n)。

1
 \
  2
   \
    3
     \
      4
       \
        5

这不是极端情况。在真实场景中，数据往往带有某种有序性：时间戳递增的日志、自增主键的数据库记录、按字母排序的词典。这些都会让朴素 BST 严重退化。

随机插入也不够好

即使插入顺序是随机的，朴素 BST 的期望高度也是 \(O(\log n)\)——但这是期望，不是保证。在最坏情况下仍然是 O(n)。对于内核这种不能接受偶发性能灾难的系统，期望值毫无意义，必须有最坏情况保证。

自平衡的思路

解决方案是让树在每次修改后自动维护平衡。核心问题是：平衡的”严格程度”如何选择？

• 太严格（如完美平衡）：维护代价太高，每次插入可能需要重建半棵树
• 太松散：退化风险仍然存在
• 刚好的平衡：AVL 和红黑树给出了两种不同的回答

二、AVL 树：严格平衡的代价

平衡条件

AVL 树（以发明者 Adelson-Velsky 和 Landis 命名，1962 年）要求每个节点的左右子树高度差（平衡因子，balance factor）的绝对值不超过 1：

\[ |bf(v)| = |h(v.left) - h(v.right)| \leq 1 \]

这是自平衡 BST 中最严格的条件。任何违反此条件的节点都必须通过旋转立即修复。

高度上界的数学证明

设 \(N(h)\) 为高度 \(h\) 的 AVL 树的最少节点数。一棵高度为 \(h\) 的最小 AVL 树，其一侧子树高度为 \(h-1\)，另一侧为 \(h-2\)（恰好差 1，否则还能更矮）。递推关系：

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

初始条件：\(N(0) = 1\)，\(N(1) = 2\)。

这个递推关系和 Fibonacci 数列几乎相同。令 \(M(h) = N(h) + 1\)，则 \(M(h) = M(h-1) + M(h-2)\)，恰好是 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\)），对 \(n = N(h)\) 取逆可得：

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

这意味着一棵包含 100 万个节点的 AVL 树，高度不超过 \(1.44 \times 20 \approx 29\)。实际上，随机数据构建的 AVL 树高度通常接近 \(\log_2 n\)，远低于理论上界。

四种旋转操作

当插入或删除破坏了平衡条件时，AVL 树通过旋转恢复。根据失衡的方向，分为四种情况：

LL 型（左左）：节点的左子树的左子树过高。对失衡节点做一次右旋转。

    z                y
   / \             /   \
  y   T4          x     z
 / \       →     / \   / \
x   T3          T1 T2 T3 T4
/ \
T1 T2

RR 型（右右）：LL 的镜像。对失衡节点做一次左旋转。

z                    y
 \                 /   \
  y               z     x
 / \       →     / \   / \
T1  x           T1 T2 T3 T4
   / \
  T3 T4

LR 型（左右）：节点的左子树的右子树过高。先对左子节点做一次左旋转（转化为 LL），再对失衡节点做一次右旋转。

    z              z              x
   / \            / \           /   \
  y   T4         x   T4       y     z
 / \       →    / \       →  / \   / \
T1  x          y   T3       T1 T2 T3 T4
   / \        / \
  T2 T3      T1 T2

RL 型（右左）：LR 的镜像。先对右子节点做右旋转，再对失衡节点做左旋转。

旋转次数分析

插入：最多 1 次旋转（单旋）或 1 次双旋（等价于 2 次单旋）即可恢复平衡。关键原因：插入只增加了一条路径的高度。一旦在最低的失衡节点处完成旋转，该节点的高度恢复到插入前的值，上层节点不再失衡。

删除：最多 O(log n) 次旋转。删除可能降低了一侧的高度，旋转修复后该节点的高度可能比删除前还低——这意味着它的父节点可能新出现失衡，需要继续向上检查和旋转。最坏情况下，从删除点到根，每一层都需要一次旋转。

这就是 AVL 树的阿喀琉斯之踵：删除时旋转次数与树高成正比。

三、红黑树五条性质与 2-3-4 树视角

红黑树的五条性质

红黑树（Bayer 1972, Guibas & Sedgewick 1978）用颜色标记取代了严格的高度约束：

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

这五条性质看似随意，实则精心设计。它们共同保证了一个关键不等式：

\[ \text{最短路径（全黑）} \leq \text{任意路径} \leq 2 \times \text{最短路径（红黑交替）} \]

也就是说，红黑树中最长路径不超过最短路径的 2 倍。这比 AVL 的”高度差不超过 1”宽松得多，但已经足够保证 O(log n) 的操作复杂度。

高度上界推导

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

以某节点 \(x\) 为根的子树至少包含 \(2^{bh(x)} - 1\) 个内部节点（想象一棵全黑的完美二叉树）。因此：

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

又因为树高 \(h \leq 2 \times bh\)（最长路径上红黑交替），所以：

\[ h \leq 2 \log_2(n+1) \]

对比 AVL 的 \(1.44 \log_2(n+2)\)，红黑树在最坏情况下大约高 39%。

从 2-3-4 树视角理解红黑树

红黑树的五条性质初看之下难以记忆，但如果从 2-3-4 树的角度理解，一切就自然了。

2-3-4 树是一种 B 树的特例，每个节点可以包含 1、2 或 3 个键（对应 2、3、4 个子节点）。它天然是完美平衡的——所有叶子在同一层。

红黑树就是 2-3-4 树的二叉表示。映射规则如下：

• 2-node（1 个键）→ 一个黑色节点
• 3-node（2 个键）→ 一个黑色节点 + 一个红色子节点
• 4-node（3 个键）→ 一个黑色节点 + 两个红色子节点

通过这个映射，红黑树的性质变得直观：

• 黑高一致（性质 5）：因为 2-3-4 树所有叶子在同一层，而每个 2-3-4 节点恰好对应一个黑色节点
• 红不相邻（性质 4）：因为一个 2-3-4 节点最多包含 3 个键（一个 4-node），对应一黑两红，红色节点只在黑色节点的直接子节点位置
• 根是黑色（性质 2）：2-3-4 树的根总是一个独立的节点组

理解了这个映射，红黑树的插入和删除操作也变得可解释：它们本质上是在模拟 2-3-4 树的节点分裂和合并。

4-node 分裂与重着色

当红黑树中出现一个黑色节点带两个红色子节点（对应 2-3-4 树的 4-node），插入新键时需要”分裂”。在红黑树中，分裂操作对应重着色：将两个红色子节点变黑，父节点变红（将中间键”上推”到父 2-3-4 节点中）。这个操作不涉及任何指针修改，开销极低。

四、插入操作对比

AVL 树的插入

AVL 插入分两步：

1. 标准 BST 插入：沿着树向下找到合适位置，插入新节点
2. 回溯修复：从插入点向上回溯，更新每个祖先的平衡因子。遇到第一个失衡节点（|bf| > 1）时，执行一次旋转（或双旋）。旋转后该子树的高度恢复原值，上层不再受影响。

关键性质：插入后最多 1 次旋转（或 1 次双旋），总共最多 2 次单旋。但需要 O(log n) 的回溯来更新平衡因子。

红黑树的插入

红黑树插入也是两步：

1. 标准 BST 插入：新节点着红色
2. 修复红色约束：如果父节点也是红色，违反性质 4，需要修复

修复分三种情况（以新节点的父节点是祖父节点的左子节点为例，镜像情况对称）：

Case 1：叔节点为红色——这对应 2-3-4 树的 4-node 分裂。将父和叔变黑，祖父变红，然后将当前节点上移到祖父继续检查。这只是重着色，不涉及旋转。

Case 2：叔节点为黑色，当前节点是右子节点——先对父节点左旋，转化为 Case 3。

Case 3：叔节点为黑色，当前节点是左子节点——将父变黑，祖父变红，对祖父右旋。

最多执行 2 次旋转（Case 2 + Case 3 各一次），但可能执行 O(log n) 次重着色（Case 1 可能一路向上传播到根）。

插入对比小结

在插入操作上，两者几乎打平。AVL 可能只需 1 次旋转，红黑树最多 2 次，但差异很小。

五、删除操作对比——核心差异

AVL 树的删除

AVL 删除是性能问题的根源。步骤：

1. 标准 BST 删除：找到目标节点，用前驱或后继替代
2. 回溯修复：从删除点向上回溯，更新平衡因子。每个失衡节点都需要旋转

关键问题：删除一个节点可能使某子树高度减 1。旋转修复后，该节点的新高度可能仍然比删除前低 1——这意味着它的父节点又可能失衡。这种”连锁反应”可以一路传播到根。

最坏情况：树的每一层都需要一次旋转，总共 O(log n) 次。

构造这种最坏情况并不困难。考虑一棵”Fibonacci AVL 树”（每层都恰好差 1 的最小 AVL 树），删除最深层的某个叶子，就可能触发从底到顶的连锁旋转。

红黑树的删除

红黑树删除也有多种情况，但关键区别在于：

1. 如果删除的是红色节点（或替代节点是红色），直接删除或变色，不影响黑高
2. 如果删除了一个黑色节点且替代节点也是黑色，会导致一条路径上少一个黑色节点，需要修复

修复过程分四种情况（以当前节点是父节点的左子节点为例）：

Case 1：兄弟节点为红色——将兄弟变黑，父变红，对父左旋。转化为 Case 2/3/4。

Case 2：兄弟节点为黑色，兄弟的两个子节点都为黑色——将兄弟变红，“黑色缺失”上移到父节点。如果父是红色，变黑即可结束；如果父是黑色，继续向上。

Case 3：兄弟为黑色，兄弟的左子红、右子黑——将兄弟变红，兄弟左子变黑，对兄弟右旋。转化为 Case 4。

Case 4：兄弟为黑色，兄弟的右子为红色——将兄弟颜色设为父的颜色，父变黑，兄弟右子变黑，对父左旋。结束。

关键观察：

• Case 1 最多发生 1 次（之后转入 2/3/4）
• Case 2 可能向上传播 O(log n) 次，但只涉及重着色，不涉及旋转
• Case 3 最多 1 次旋转（转入 Case 4）
• Case 4 最多 1 次旋转（终止）

因此，删除最多 3 次旋转（Case 1 + Case 3 + Case 4 各一次），加上 O(log n) 次重着色。

这才是决定性差异

在内核的很多场景中——进程退出释放资源、定时器到期删除、内存区域释放——删除操作非常频繁。如果每次删除都可能触发 O(log n) 次旋转，在 n = 100,000 时意味着最多 17 次旋转；用红黑树则最多 3 次。

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

• RCU（Read-Copy-Update）：读者无锁遍历树结构。结构修改需要特殊处理（如发布新版本），但颜色修改对读者透明
• 持久化数据结构：结构修改需要创建新的路径副本（path copying），旋转越多，副本越多
• 并发场景：结构修改需要锁定更多节点，颜色修改的锁粒度更小

六、Linux 内核中的红黑树

内核 rbtree 的节点设计

// include/linux/rbtree_types.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;
};

struct rb_root_cached {
    struct rb_root rb_root;
    struct rb_node *rb_leftmost;
};

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

// include/linux/rbtree_augmented.h
#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
#define __rb_color(pc)     ((pc) & 1)
#define rb_parent(r)       ((struct rb_node *)((r)->__rb_parent_color & ~3))
#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
#define rb_is_red(rb)      (!rb_color(rb))
#define rb_is_black(rb)    rb_color(rb)

这样一个节点只需要 3 个机器字（64 位系统上 24 字节），而非 4 个字段（parent + left + right + color = 32 字节 + padding）。在内核中，每个缓存行 64 字节，节省 8 字节意味着一个缓存行能多放一个半节点。

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+）仍然使用红黑树，但键变成了 virtual deadline，同样利用了红黑树高效的遍历和删除能力。

mm_struct VMA 管理

Linux 的虚拟内存管理中，每个进程的地址空间由多个虚拟内存区域（VMA, Virtual Memory Area）组成。在 Linux 6.1 之前，VMA 用红黑树管理：

// 旧版 include/linux/mm_types.h（Linux < 6.1）
struct mm_struct {
    struct rb_root mm_rb;       // VMA 红黑树
    // ...
};

当进程执行 mmap、munmap、brk 等操作时，需要快速查找和修改 VMA。红黑树以起始地址为键，支持：

• 查找：给定一个虚拟地址，找到包含它的 VMA（page fault 处理）
• 插入：mmap 创建新映射
• 删除：munmap 删除映射
• 范围查找：查找与给定范围重叠的所有 VMA

值得注意的是，Linux 6.1 将 VMA 管理改用了 maple tree（一种基于 B-tree 的 RCU 安全数据结构），原因正是红黑树在 RCU 场景下的结构修改代价和 cache 友好性不如 B-tree 变种。这个迁移本身就说明了：没有永远最优的数据结构，只有特定约束下的最优选择。

epoll 中的红黑树

// fs/eventpoll.c
struct eventpoll {
    struct rb_root_cached rbr;  // 红黑树管理监控的 fd
    struct list_head rdllist;   // 就绪链表
    // ...
};

epoll 使用红黑树管理被监控的文件描述符。每次 epoll_ctl(EPOLL_CTL_ADD) 插入一个 fd，EPOLL_CTL_DEL 删除。选择红黑树而非哈希表的原因：确定性 O(log n) 最坏情况（内核不能容忍哈希冲突导致的 O(n) 退化），以及有序遍历能力。

七、左倾红黑树（LLRB）

Sedgewick 的简化

Robert Sedgewick 在 2008 年提出了左倾红黑树（Left-Leaning Red-Black Tree）。核心思想是在标准红黑树的基础上增加一条约束：

红色链接只能是左链接。

这条额外约束将 3-node 的表示方式从两种（左倾或右倾）限定为一种（只能左倾），消除了大量对称情况，使得实现代码量减少约 50%。

LLRB 与 2-3 树的映射

标准红黑树对应 2-3-4 树，而 LLRB 对应更简单的 2-3 树：

• 2-node：一个黑色节点
• 3-node：一个黑色节点 + 一个左红色子节点

没有 4-node，因为 4-node 在插入时立即分裂（对应重着色操作在向下的过程中提前执行）。

核心操作

LLRB 的实现只需要三个辅助操作：

// 左旋：将右倾红链接转为左倾
static Node *rotate_left(Node *h) {
    Node *x = h->right;
    h->right = x->left;
    x->left = h;
    x->color = h->color;
    h->color = RED;
    return x;
}

// 右旋：将左倾红链接临时转为右倾（用于修复连续两个左红链接）
static Node *rotate_right(Node *h) {
    Node *x = h->left;
    h->left = x->right;
    x->right = h;
    x->color = h->color;
    h->color = RED;
    return x;
}

// 颜色翻转：分裂 4-node
static void flip_colors(Node *h) {
    h->color = !h->color;
    h->left->color = !h->left->color;
    h->right->color = !h->right->color;
}

插入操作变得极其简洁：

static Node *insert(Node *h, int key) {
    if (h == NULL)
        return new_node(key, RED);

    if (key < h->key)       h->left  = insert(h->left, key);
    else if (key > h->key)  h->right = insert(h->right, key);
    else                     h->key = key;  // 重复键：更新

    // 三行修复，顺序不能错
    if (is_red(h->right) && !is_red(h->left))     h = rotate_left(h);
    if (is_red(h->left) && is_red(h->left->left)) h = rotate_right(h);
    if (is_red(h->left) && is_red(h->right))       flip_colors(h);

    return h;
}

三行修复规则，覆盖了标准红黑树插入的所有情况。这就是 LLRB 的魅力：代码量少到可以在白板上完整写出。

性能争议

LLRB 的简洁性是有代价的：

1. 旋转次数更多：标准红黑树允许右倾红链接存在，LLRB 必须立即修复。这导致 LLRB 的平均旋转次数高于标准实现
2. 删除更复杂：虽然代码行数少，但 LLRB 的删除需要在向下搜索路径上预处理（保证到达删除位置时可以直接删除红色节点），逻辑复杂度不低
3. cache 不友好：更多旋转意味着更多的指针修改和潜在的 cache line 失效

实测数据（100 万随机键）：

结论：LLRB 适合教学和代码量敏感的场景（如嵌入式系统），但在高性能场景中不如标准红黑树。

八、完整 C 实现：红黑树（insert + delete + rebalance）

以下是包含插入和删除的完整红黑树实现，含哨兵节点和性质验证：

#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;
            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->right) {
                    z = z->parent;
                    left_rotate(t, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                right_rotate(t, z->parent->parent);
            }
        } else {
            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;
        x = (key < x->key) ? x->left : 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);
}

/* ── 删除 ────────────────────────────────────────── */

static void transplant(RBTree *t, RBNode *u, RBNode *v) {
    if (u->parent == t->nil)       t->root = v;
    else if (u == u->parent->left) u->parent->left = v;
    else                            u->parent->right = v;
    v->parent = u->parent;
}

static RBNode *tree_minimum(RBTree *t, RBNode *x) {
    while (x->left != t->nil)
        x = x->left;
    return x;
}

static void delete_fixup(RBTree *t, RBNode *x) {
    while (x != t->root && x->color == BLACK) {
        if (x == x->parent->left) {
            RBNode *w = x->parent->right;
            if (w->color == RED) {
                // Case 1：兄弟为红
                w->color = BLACK;
                x->parent->color = RED;
                left_rotate(t, x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                // Case 2：兄弟的两个子节点都是黑色
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    // Case 3：兄弟的右子为黑
                    w->left->color = BLACK;
                    w->color = RED;
                    right_rotate(t, w);
                    w = x->parent->right;
                }
                // Case 4：兄弟的右子为红
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                left_rotate(t, x->parent);
                x = t->root;
            }
        } else {
            RBNode *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                right_rotate(t, x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    left_rotate(t, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                right_rotate(t, x->parent);
                x = t->root;
            }
        }
    }
    x->color = BLACK;
}

void rbtree_delete(RBTree *t, RBNode *z) {
    RBNode *y = z;
    RBNode *x;
    Color y_orig_color = y->color;

    if (z->left == t->nil) {
        x = z->right;
        transplant(t, z, z->right);
    } else if (z->right == t->nil) {
        x = z->left;
        transplant(t, z, z->left);
    } else {
        y = tree_minimum(t, z->right);
        y_orig_color = y->color;
        x = y->right;
        if (y->parent == z) {
            x->parent = y;
        } else {
            transplant(t, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(t, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    if (y_orig_color == BLACK)
        delete_fixup(t, x);
    free(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;
    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;
    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("After insert — inorder: ");
    inorder(t, t->root);
    printf("\n");
    printf("Valid RB tree: %s\n", verify_rb(t, t->root) > 0 ? "YES" : "NO");

    // 删除测试
    int del_keys[] = {8, 31, 41, 55};
    int nd = sizeof(del_keys) / sizeof(del_keys[0]);
    for (int i = 0; i < nd; i++) {
        RBNode *node = rbtree_search(t, del_keys[i]);
        if (node) {
            printf("Delete %d → ", del_keys[i]);
            rbtree_delete(t, node);
            inorder(t, t->root);
            printf(" | valid: %s\n",
                   verify_rb(t, t->root) > 0 ? "YES" : "NO");
        }
    }

    // 验证剩余键都能找到
    int remaining[] = {12, 19, 25, 33, 38, 45, 50, 60};
    int nr = sizeof(remaining) / sizeof(remaining[0]);
    for (int i = 0; i < nr; i++) {
        if (!rbtree_search(t, remaining[i]))
            printf("ERROR: %d not found\n", remaining[i]);
    }
    printf("All remaining %d keys verified.\n", nr);
    return 0;
}

九、基准测试：AVL vs RB vs LLRB

测试方法

测试条件：100 万个键，GCC 13 -O3，Intel i7-12700，Ubuntu 22.04。每个测试运行 10 次取中位数。三种负载模式：

模式一：随机插入后随机查找

AVL 查找快 5%（更矮），RB 插入快 5%，LLRB 最慢。

模式二：顺序插入（最坏情况）

顺序插入时 AVL 树反而更紧凑（接近完美平衡），查找优势扩大到 8%。

模式三：随机插入后倾斜删除（删除最小的 50%）

删除性能差距最为显著：红黑树比 AVL 快 20%，比 LLRB 快 17%。删除最小元素意味着持续从树的一侧移除节点，对 AVL 来说可能触发大量连锁旋转。

内存开销对比

Linux 内核的侵入式红黑树（rb_node 嵌入到宿主结构中）是内存效率最高的方案，因为不需要额外的堆分配。

十、工程陷阱表

十一、其他自平衡树简评

伸展树（Splay Tree）

Sleator 和 Tarjan 1985 年提出。核心操作：每次访问一个节点后，通过一系列旋转（zig-zig, zig-zag）将它提升到根。

• 优势：最近访问的元素在根附近，热点访问模式下性能极好；摊还 O(log n)；不需要存储平衡信息
• 劣势：最坏单次操作 O(n)；每次读操作也修改树结构，不适合并发或只读场景
• 适用场景：缓存、垃圾收集器的内存分配器（热点数据重复访问）

替罪羊树（Scapegoat Tree）

不在每次修改后立即重平衡。维护一个全局计数器追踪”不平衡度”。当某次插入导致树过深时，找到最高的”不够平衡”的祖先节点（替罪羊），暴力重建以它为根的整棵子树。

• 优势：不需要存储额外平衡信息（颜色、高度、平衡因子都不需要），节点最小；摊还 O(log n)
• 劣势：最坏单次插入 O(n)（重建子树）；重建时内存分配模式不友好
• 适用场景：内存极度受限的嵌入式系统

权重平衡树（Weight-Balanced Tree）

以子树大小而非高度作为平衡标准。要求每个节点的左右子树大小比不超过某个常数（通常 \(\alpha = 1 - \frac{1}{\sqrt{2}} \approx 0.293\)）。

• 优势：O(1) 的 size() 和 rank() 操作（每个节点存子树大小）；天然支持 order-statistic 查询（第 k 小元素）
• 劣势：旋转条件复杂，参数选择需要理论分析
• 适用场景：Haskell 的 Data.Map/Data.Set（函数式编程中 size 信息用于高效的集合操作）

树堆（Treap）

每个节点同时有一个键（满足 BST 性质）和一个随机优先级（满足堆性质）。

• 优势：实现简单（只需要旋转）；随机化保证期望 O(log n)；支持高效的分裂（split）和合并（merge）
• 劣势：随机数生成开销；期望而非最坏情况保证
• 适用场景：需要可持久化的场景、竞赛编程

选择建议

十二、个人观点

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

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

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

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

四、不要迷信经典。 Linux 内核在 6.1 版本将 VMA 管理从红黑树迁移到 maple tree，说明红黑树也不是银弹。当 RCU 可扩展性和 cache 友好性成为主要矛盾时，B-tree 变种可能是更好的选择。工程选择永远是权衡，不是信仰。

五、理解一种自平衡树到极致，比浅尝辄止五种更有价值。 如果你能完整手写红黑树的删除操作（包括所有四种 case 及其镜像），你对指针操作、不变量维护和 case analysis 的理解会深入到骨子里。这种功力在调试任何复杂数据结构时都有用。

如果让我选：通用场景用红黑树（或直接用标准库），只读场景考虑 AVL，范围查询场景先看 B-tree，其他场景想清楚你的约束再决定。

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

相关阅读： - epoll 的数据结构：红黑树、就绪队列与回调 - 进程调度：从 CFS 到 EEVDF