红黑树与 AVL：旋转次数、树高与 Linux 内核的选择

关于这两种树，流传最广的说法是：“AVL 更平衡所以查找更快，红黑树旋转更少所以插删更快，Linux 内核因此选了红黑树。”这句话里有三个需要拆开核对的判断。

第一，树高差多少、查找路径差多少。AVL 的最坏高度约为 \(1.44\log_2 n\)，红黑树是 \(2\log_2(n+1)\)，最坏界相差近四成；但随机插入 \(2^{20}\) 个键后，本文实测两者高度都是 24，平均查找深度相差不到 0.5%。

第二，旋转次数差在哪里。两者插入都至多旋转 2 次。删除时红黑树至多 3 次，AVL 最坏是 \(\Theta(\log n)\) 次；可是在随机删除下，AVL 平均每次删除旋转 0.373 次，红黑树 0.379 次，几乎一样。差别在最坏情形和平衡信息的写入量上。

第三，Linux 为什么用红黑树。内核在 2.4.10 把 VMA 索引从 AVL 树换成了 Andrea Arcangeli 写的 lib/rbtree.c，但当时的变更记录只写了“major VM merge”，没有给出换树理由；而从 6.1 起，VMA 本身已改由 maple tree 管理。今天红黑树在内核里的价值，更多来自侵入式节点、rb_root_cached 和增强红黑树（augmented rbtree）这些接口设计。

本文先给出两种树的平衡条件、高度界和更新算法（每一步都配图），再用一个与内核实现逐操作对照过的计数程序测量旋转、平衡标记写入、比较次数和树高，最后回到 Linux v6.12 源码和从 AVL 到 WAVL 的文献谱系。

一、平衡条件与高度界

本文的“高度”按节点数计：空树高度为 0，单节点高度为 1。\(\lg\) 表示 \(\log_2\)。

AVL：左右子树高度差不超过 1

AVL 树（Adelson-Velsky 与 Landis，1962）要求每个节点的左右子树高度差至多为 1。实现里每个节点存一个平衡因子（balance factor）\(\mathrm{bf} = h(\text{right}) - h(\text{left}) \in \{-1, 0, +1\}\)。

设 \(N(h)\) 为高度 \(h\) 的 AVL 树最少节点数。最稀疏的树由根、一棵高 \(h-1\) 的最稀疏子树和一棵高 \(h-2\) 的最稀疏子树组成：

\[ N(0) = 0,\quad N(1) = 1,\quad N(h) = N(h-1) + N(h-2) + 1 . \]

令 \(M(h) = N(h) + 1\)，得到 \(M(h) = M(h-1) + M(h-2)\)，且 \(M(0) = 1 = F_2\)、\(M(1) = 2 = F_3\)，所以 \(N(h) = F_{h+2} - 1\)（\(F_1 = F_2 = 1\) 的斐波那契数）。这类最稀疏树叫斐波那契树（Fibonacci tree）。注意初值：若把单节点树的高度记为 0，递推式不变但下标整体平移，结果是 \(F_{h+3} - 1\)；把 \(N(0)=1, N(1)=2\) 与 \(F_{h+2}-1\) 混用是常见错误。

由 \(F_k > \varphi^k/\sqrt5 - 1\)（\(\varphi = (1+\sqrt5)/2\)），\(n \ge N(h)\) 推出 \(n + 2 > \varphi^{h+2}/\sqrt5\)，即

\[ h < \log_\varphi(n+2) + \log_\varphi\sqrt5 - 2 \approx 1.4404\,\lg(n+2) - 0.3277 . \]

这就是 Knuth 在 TAOCP 第 3 卷 6.2.3 节给出的界，常简写为 \(h \lesssim 1.44\lg n\)。

红黑树：黑高相等、红节点不相邻

红黑树（Guibas 与 Sedgewick，1978）按 CLRS 的表述满足五条性质：每个节点非红即黑；根是黑色；外部空叶子（NIL）是黑色；红节点的两个孩子都是黑色；从任一节点到其所有后代 NIL 的路径上黑节点数相同，这个数叫该节点的黑高（black-height）\(\mathrm{bh}\)。

对黑高归纳可得：以 \(x\) 为根的子树至少有 \(2^{\mathrm{bh}(x)} - 1\) 个内部节点。红节点不相邻，所以任一根到叶路径上至少一半节点是黑色，\(\mathrm{bh}(\text{root}) \ge h/2\)，于是 \(n \ge 2^{h/2} - 1\)：

\[ h \le 2\lg(n+1) . \]

这是 CLRS 引理 13.1。这个界几乎可以取到：一条全黑的最短路径和一条红黑交替的最长路径可以同时存在。第五节的实验里，按升序插入 \(2^{20}\) 个键后红黑树高度为 38，恰为 \(2\lg n - 2\)。

红黑树就是用二叉节点画出的 2-3-4 树

红黑树的规则直接来自 2-3-4 树（每个节点有 2 到 4 个孩子、所有叶子同深度的 B 树）。把每个黑节点和它的红孩子合起来看作一个 B 树节点，红边就是“同一个 2-3-4 节点内部”的边：

图底部方框里的两条说明就是上面两条性质的来源：每个 2-3-4 节点在任一根到叶路径上恰好贡献一个黑节点，所以黑高等于 2-3-4 树的高度，而 2-3-4 树所有叶子同深度，于是各路径黑节点数相等；一个 2-3-4 节点在二叉形式里最多占两层，所以不会出现连续红节点。后面插入修复的 Case 1（三色翻转）对应 4-node 分裂，旋转对应“同一个 B 树节点换一种二叉画法”。

一个 3-node 有左倾和右倾两种画法。Guibas–Sedgewick 的原始框架、CLRS 和 Linux 都允许两种；Sedgewick 2008 年的左倾红黑树（left-leaning red-black tree，LLRB）只允许左倾，使 2-3 树与红黑树一一对应，代码因此变短，代价在第五节和第八节讨论。

两个界在 \(n = 2^{20}\) 时的数值

最坏界相差 40%，随机输入下的实际形状几乎一样。平均查找深度按根深度为 1 计，完全平衡树约为 \(\lg n - 1 = 19\)；随机插入得到的两种树都只比它多 2% 左右。

二、旋转：只改一条边的局部重构

两种树恢复平衡都靠旋转（rotation）和修改平衡信息。旋转把一条父子边“翻过来”：

rotate_left(x) 改写三个孩子指针（x.right = B、y.left = x、原父节点指向 y），带父指针的实现再改三个父指针。中序序列不变，所以仍是合法的二叉搜索树。只有 x 和 y 两个节点的深度和子树高度改变，A、B、C 整体搬动。这是后面所有“\(O(1)\) 旋转”结论的基础：一次旋转是常数次指针写入，不论树多大。

旋转的代价在内核里还多一项：增强红黑树的每次旋转都要回调 rotate，重新计算两个节点上维护的附加值（第六节）。所以“每次更新至多几次旋转”对增强树比对普通树更有意义。

三、AVL 的插入与删除

插入：至多一次单旋转或双旋转

插入新叶子后，沿父指针向上更新平衡因子。某个祖先的 bf 变成 0，说明它的高度没变，停止；变成 \(\pm1\)，说明它长高了一层，继续向上；变成 \(\pm2\)，就在这个最低的失衡节点 \(z\) 处旋转：

关键在图右侧的注释：旋转后子树高度恢复为插入前的 \(h+2\)，上面的祖先看不到任何变化，循环立即结束。所以 AVL 插入至多做一次单旋转或一次双旋转，即至多 2 次旋转；但平衡因子的修改可能沿路径一直写到根，最坏 \(O(\log n)\) 次。只有插入的操作序列上，Mehlhorn 与 Tsakalidis（1986）证明平衡因子修改的摊还次数是常数。

删除：旋转可能让子树变矮，失衡继续上传

删除一个节点（有两个孩子时先与后继交换）后，被删一侧变矮。与插入相反，旋转修好当前节点后，子树高度可能比删除前少一层，于是父节点接着失衡：

斐波那契树是最坏情形：每个内部节点都“偏向一边”，从最大键向上的每隔一层都会失衡一次。第五节实验 E6 在高度 \(h\) 的斐波那契树上删除最大键，旋转次数恰为 \(\lceil h/2 \rceil - 1\)，随树高线性增长，也就是 \(\Theta(\log n)\)。

最坏 \(\Theta(\log n)\) 不等于摊还也是 \(\Theta(\log n)\)。Amani、Lai 与 Tarjan（2016）的摘要指出：从 \(n\) 节点树连续删除 \(n\) 次总共只需 \(O(n)\) 次旋转；Haeupler、Sen 与 Tarjan 曾猜想交替的插入和删除可以让每次删除都做 \(\Omega(\log n)\) 次旋转，但没有给出构造。Amani 等人给出了构造：对无穷多个 \(n\) 存在一族“昂贵”的 AVL 树，删除某片叶子再插回去仍得到这一族里的树，而这次删除做了 \(\Theta(\log n)\) 次旋转，这样的删除—插入对可以无限重复。所以 AVL 删除的旋转次数在摊还意义下也没有常数界。

四、红黑树的插入与删除修复

下面的写法与 Linux lib/rbtree.c 的注释一致：大写字母是黑节点，小写是红节点，带括号的是颜色不定的节点。只画父节点是左孩子的情形，另一侧镜像对称。

插入：Case 1 只改色并上移，Case 2、3 旋转后结束

新节点染红挂到叶子位置，黑高不变，唯一可能被破坏的是“红节点不相邻”。若父节点 p 为红（于是祖父 G 必为黑），看叔叔 u 的颜色：

• Case 1：叔叔为红。把 p、u 染黑，G 染红。用 2-3-4 树的语言，这是 4-node \(\{p, G, u\}\) 分裂，中间键 G 上升到父节点。G 变红后可能又和它的父节点构成红红对，于是令 \(n = G\) 重复。这是唯一会循环的情况，只改色、不旋转。
• Case 2：叔叔为黑，n 是内侧孩子。左旋 p，红红对转到外侧，恰好变成 Case 3（n 与 p 名字互换），必然接着执行 Case 3。
• Case 3：叔叔为黑，n 是外侧孩子。右旋 G，p 染黑、G 染红。子树根又是黑色，各路径黑节点数不变，结束。

所以一次插入至多旋转 2 次（Case 2 接 Case 3），改色最坏 \(O(\log n)\) 次（Case 1 一路上移到根）。

删除：Case 1 至多一次，Case 2 只改色并上移，Case 3、4 旋转后结束

先做普通的二叉搜索树删除：有两个孩子时与中序后继交换位置。若真正摘掉的节点是红色，什么都不用做；若是黑色而顶替它的孩子是红色，把孩子染黑即可；否则顶替位置 N 所在的路径比别处少一个黑节点，需要修复：

• Case 1：兄弟 s 为红。左旋 P、交换 P 和 S 的颜色。N 仍有亏空，但它的新兄弟是黑色、父节点是红色，于是转入后三种情况之一；若转入 Case 2，红色的 p 直接吸收亏空，循环也在这里结束。
• Case 2：兄弟黑且两个孩子都黑。把兄弟染红，P 的两侧现在都少一个黑节点，亏空上移到 P。P 为红就染黑结束，P 为黑就令 \(N = P\) 继续。这是唯一会循环的情况，只改色。
• Case 3：兄弟黑、内侧孩子红、外侧孩子黑。右旋 S，N 的新兄弟有了红色的外侧孩子，必然进入 Case 4。Linux 在这里不做 CLRS 里的两次改色，因为 Case 4 会把相关节点的颜色全部覆盖（图中灰字）。
• Case 4：兄弟黑、外侧孩子红。左旋 P，S 继承 P 原来的颜色，P 和外侧孩子染黑。经过 N 的路径多了一个黑节点 P，经过 Sr 的路径黑节点数不变，结束。

旋转次数的上界由情况之间的转移决定：Case 1 只能出现在循环开头且至多一次，Case 3 之后必是 Case 4，Case 4 结束循环，而 Case 2 不旋转。于是一次删除至多旋转 \(1 + 1 + 1 = 3\) 次。内核文档 Documentation/core-api/rbtree.rst 写的正是“插入至多两次旋转、删除至多三次”。

改色的摊还次数是常数

两个会循环的情况都只改色。最坏情况下一次插入或删除要改 \(O(\log n)\) 个节点的颜色，但摊还后是常数。Huddleston 与 Mehlhorn（1982）用多层记账法证明了“weak” B 树（包括 2-4 树）在插入、删除混合序列下摊还 \(O(1)\) 的重平衡代价，经过第一节的二叉化就是红黑树的结论；Tarjan（1983）的“Updating a balanced search tree in \(O(1)\) rotations”给出了每次更新最坏 \(O(1)\) 次旋转的红黑树更新算法。

把第三、四节合起来：

最后一行 AVL 的两项来自 Amani–Lai–Tarjan 的构造：每次昂贵的删除都做 \(\Theta(\log n)\) 次旋转，每次旋转至少改一个平衡因子。

五、计数实验：旋转、平衡标记、比较与树高

程序与口径

reproduce/bst_count.c 实现三种树：

• AVL：自底向上修复，带父指针，平衡因子取 \(\{-1, 0, +1\}\)。
• 红黑树：自底向上修复，带父指针，情况划分与 lib/rbtree.c 相同。
• LLRB：Sedgewick 的 2-3 变体，递归实现、无父指针，删除按 Sedgewick 与 Wayne《Algorithms》第 4 版的 RedBlackBST。

计数全部与时钟无关：

• 旋转：单旋转记 1 次，双旋转记 2 次。
• 平衡标记写入：平衡因子或颜色位的值真正改变一次记 1 次；写入同值不计。
• 比较：查找路径上每访问一个节点记一次三路比较。
• 树高按节点数计，平均查找深度是所有节点深度的均值（根为 1）。

test 模式在随机操作序列的每一步之后检查全部不变式。

红黑树实现先与内核对照过。reproduce/run.sh 下载 Linux v6.12 的 lib/rbtree.c 和三个头文件（校验 sha256，不存入仓库），配上几行用户态替身头文件编译，用 rb_insert_augmented/rb_erase_augmented 的 rotate 回调数旋转。对种子 1、2、3 各插入 20 万个随机排列的键、再删除一半，逐次操作的旋转数和最终树（前序的键与颜色）两边完全相同；内核版本的平均值为每次插入 0.584 次旋转，每次删除 0.367、0.361、0.363 次。所以下面红黑树的数字可以直接当作 Linux 的数字。

环境与命令：Intel Core i9-12900K，WSL2（内核 6.6.87.2），GCC 16.1.1，-O2 -Wall -Wextra；程序另用 -fsanitize=address,undefined 跑过自检与对照。\(n = 2^{20}\)，随机实验取 5 个种子的中位数，表中的“最大”是 5 个种子里的最大值。计数是确定性的，与机器负载无关，重复运行输出逐字节相同。全部结果在 reproduce/results.txt，完整运行约 5 分钟：

cd reproduce
BUILD=/tmp/rbtree-build ./run.sh

E1：随机插入，再按另一随机顺序全部删除

• 查找代价几乎相同：插入时的比较次数只差 0.3%。“AVL 更平衡所以查找明显更快”在随机输入下不成立。
• 插入时 AVL 反而旋转更多（0.697 对 0.583），平衡标记写入多 64%。AVL 的平衡条件更紧，更容易触发旋转。
• 删除的平均旋转次数几乎一样（0.373 对 0.379），差别在最大值：AVL 在这组数据里单次删除最多旋转 9 次，红黑树不超过 3 次。

E2：升序插入，再升序删除

升序插入时红黑树的高度（38）接近 \(2\lg n\) 的上界，AVL 几乎是完全平衡树（平均深度恰为 19.000，即完全平衡树的值）。但红黑树的平均深度只多 0.5，长路径上的节点只占少数。三种树在升序输入下的旋转次数完全相同，差别只在删除：LLRB 每次删除 1 次旋转，AVL 和红黑树是 0.5 次。

E3：高度与上界

升序插入下红黑树高度恰为 \(2\lg n - 2\)。随机插入的 LLRB 高度 28 与 Sedgewick 观察到的“约 \(2\ln N\)”（\(2\ln 2^{20} \approx 27.7\)）一致。

E4 与 E5：两种稳态负载

E4 模拟定时器或运行队列式的用法：先放入 \(n\) 个键，再重复 \(4n\) 次“删除最小键、插入一个比当前最小键更大的随机键”。键分布是本文设定的，不代表任何真实内核负载。E5 是随机替换：每次删除一个随机的现存键，再插入一个新的随机键。

反复删除最左节点会持续削薄树的左侧，AVL 的删除级联在这里最明显：单次删除最多 15 次旋转，红黑树仍不超过 3 次。平均旋转次数只差 11%。E5 里两者的平均旋转几乎相同，但每对操作 AVL 写 6.0 次平衡因子，红黑树写 2.7 次颜色。

“标记写入”是逻辑计数，不等于缓存行写入。Linux 的颜色位与父指针共用一个字，改色时写的正是这个字；AVL 的平衡因子也可以同样塞进指针低位。两者的写放大比例要在具体布局上测，这里不下结论。

E6：AVL 删除的最坏情形

在高度 \(h\) 的斐波那契树（\(n = F_{h+2} - 1\)）上删除最大键：

旋转次数为 \(\lceil h/2 \rceil - 1\)，平衡因子写入恰为旋转次数的 3 倍。\(h = 5\) 的情形就是第三节的级联图。

LLRB 的数字与已有测量的对比

LLRB 插入的平均旋转是红黑树的 2 倍，最坏一次插入旋转 18 次；删除平均旋转 8.3 次、写 64 次颜色、比较 46.6 次，是红黑树的 2.6 倍。原因在删除算法的结构：下行时在路径的每一层都可能用 moveRedLeft/moveRedRight 预先“借”一个红节点，回溯时每一层都要 balance 一次；标准红黑树的修复从删除点向上进行，E1 里平均写 1.8 次颜色就结束。

Eddie Kohler 的笔记《Left-Leaning Red-Black Trees Considered Harmful》测过 100 万个随机键：红黑树每次插入 0.582 次旋转、每次删除 0.380 次，与本文的 0.583 和 0.379 吻合；LLRB 为 1.725 和 19.757，本文是 1.187 和 8.301。趋势相同，数值差了约 1.5 到 2.4 倍。本文没有拿到 Kohler 的 LLRB 实现，无法确认差异来自 2-3 与 2-3-4 变体的选择还是删除细节，因此只把“LLRB 的删除旋转远多于标准红黑树”当作结论，不引用具体倍数。

六、Linux 内核里的红黑树

从 AVL 换到红黑树：有记录的只有时间，没有理由

Linux 2.2 已经用平衡树索引进程的虚拟内存区（VMA）。mm/mmap_avl.c 由 Bruno Haible 编写，文件开头说明了动机：线性链表查找 VMA 太慢，一个进程的 VMA“通常 6 个左右，但在面向对象数据库、分代垃圾回收、ElectricFence 等场景可达 3000 个”。这棵 AVL 树以 vm_end 为键，vm_area_struct 里只有 short vm_avl_height 和左右两个指针，没有父指针，更新时把路径压在一个深度为 41 的显式栈里回溯。到 2.4.9，mm/mmap.c 只在 map_count >= AVL_MIN_MAP_COUNT（32）时才建树，VMA 少时仍走链表。

2.4.10（2001 年）引入了 lib/rbtree.c，文件头是“(C) 1999 Andrea Arcangeli”，当时唯一的调用者就是 mm/mmap.c，AVL 代码随之删除。那时的节点是：

/* Linux 2.4.10, include/linux/rbtree.h */
typedef struct rb_node_s
{
    struct rb_node_s * rb_parent;
    int rb_color;
#define RB_RED      0
#define RB_BLACK    1
    struct rb_node_s * rb_right;
    struct rb_node_s * rb_left;
}
rb_node_t;

它比被替换的 AVL 字段更大：多了父指针，颜色占一个 int。2.4.10 的 ChangeLog 里能与这次改动对上的只有 pre11 中的一条“Andrea Arkangeli: major VM merge”，没有说明为什么换树。所以“内核因为红黑树旋转少、省内存而选择它”没有一手依据：省内存在当时不成立，旋转少是事实，但没有文献或提交说明它是决策理由。本文能确认的只是换树的时间和作者。

颜色和父指针合并是后来的事。2006 年 David Woodhouse 的提交“Merge colour and parent fields”把颜色塞进父指针的最低位，理由是颜色只需要 1 位，节点从 4 个字段降为 3 个字。同样的技巧对 AVL 也成立：平衡因子只有三种取值，2 位就够，而指针至少 4 字节对齐时最低两位恒为 0。节点大小不是两种树的本质差别。

v6.12 的节点与根

/* Linux v6.12, 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_cached {
    struct rb_root rb_root;
    struct rb_node *rb_leftmost;
};

include/linux/rbtree_augmented.h 定义 RB_RED 为 0、RB_BLACK 为 1，__rb_parent(pc) 取 pc & ~3，__rb_color(pc) 取 pc & 1。第二低位没有使用。

内核红黑树是侵入式（intrusive）的：rb_node 嵌在宿主结构里，库本身不比较键。调用者自己写查找循环，找到插入位置后调用 rb_link_node 和 rb_insert_color，或者用 rb_add/rb_add_cached 传入一个“小于”函数。lib/rbtree.c 只负责第四节的颜色修复和旋转，删除有两个孩子的节点时通过改指针与后继交换位置，从不复制宿主结构。

rb_root_cached 由 Davidlohr Bueso 在 2017 年（4.14 合并窗口）引入，多存一个最左节点指针，使 rb_first_cached 为 \(O(1)\)。提交说明列出的动机是统一各子系统各自手写的 leftmost 缓存，并加速区间树；调度器、rtmutex、epoll 等随后改用它。头文件的注释特意说明不缓存最右节点：多一个指针的内存开销，比不上能从 \(O(1)\) 的 rb_last 受益的用户数量。

增强红黑树：旋转次数进入了接口

增强红黑树在每个节点上维护一个由子树决定的附加值（例如子树内区间右端点的最大值）。2010 年 Venkatesh Pallipadi 为 x86 PAT 内存类型区间跟踪引入了第一版，2012 年 Michel Lespinasse 重写为今天的回调接口：

/* Linux v6.12, include/linux/rbtree_augmented.h */
struct rb_augment_callbacks {
    void (*propagate)(struct rb_node *node, struct rb_node *stop);
    void (*copy)(struct rb_node *old, struct rb_node *new);
    void (*rotate)(struct rb_node *old, struct rb_node *new);
};

propagate 沿路径向上重算附加值，copy 用于删除时后继顶替，rotate 在每次旋转后修正两个节点的附加值。第五节的内核对照正是借 rotate 回调数旋转的。每次更新至多 3 次旋转，意味着至多 3 次 rotate 回调；换成 AVL，一次删除的 rotate 回调次数会随树高增长。但 propagate 本身就要走 \(O(\log n)\) 层，这个差别只影响常数。

v6.12 里两个典型的增强树用户：

• 文件页的反向映射：vm_area_struct 的 shared.rb 和 rb_subtree_last 构成一棵以 VMA 区间为键的区间树（include/linux/interval_tree_generic.h），挂在 address_space 的 i_mmap 上。
• EEVDF 调度器：CFS 运行队列的树按虚拟截止时间排序，同时用增强值维护子树内最小的 vruntime。

/* Linux v6.12, kernel/sched/fair.c（节选） */
static inline bool entity_before(const struct sched_entity *a,
                 const struct sched_entity *b)
{
    return (s64)(a->deadline - b->deadline) < 0;
}

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    avg_vruntime_add(cfs_rq, se);
    se->min_vruntime = se->vruntime;
    se->min_slice = se->slice;
    rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
                __entity_less, &min_vruntime_cb);
}

pick_eevdf 上方的注释写明：树按截止时间有序，同时借 se->min_vruntime = min(se->vruntime, se->{left,right}->min_vruntime) 充当以 vruntime 为键的堆，于是可以在 \(O(\log n)\) 时间内找到“有资格运行且截止时间最早”的实体：左子树的 min_vruntime 表明其中有合格实体时就往左走，否则检查当前节点。rb_add_augmented_cached 是 Peter Zijlstra 在 2023 年为 EEVDF 加入的。

无锁查找与 latch tree

lib/rbtree.c 开头的注释规定：所有对 rb_left/rb_right 的写入都用 WRITE_ONCE()，并且在程序顺序上不能临时形成环。这样无锁的查找一定会结束，只会看到合法节点，找到的元素一定正确；但旋转不是原子的，查找可能漏掉整棵子树，“没找到”不代表不存在。这是 Peter Zijlstra 2015 年的改动。

需要可靠无锁查找（例如 NMI 上下文）时，内核用 include/linux/rbtree_latch.h 的 latched RB-tree：维护两份树，写者借 seqcount latch 轮流修改，读者总能找到一份稳定的副本。代价是内存翻倍、写入做两遍。

VMA 在 6.1 离开了红黑树

2021 年 LWN 的《Introducing maple trees》总结了 Liam Howlett 与 Matthew Wilcox 提出 maple tree 的理由：红黑树不擅长表示区间，难以做成 RCU 下的无锁读，遍历效率低以至于 VMA 还要另挂一条链表；背后的动因是 mmap_lock 的争用，而无锁读 VMA 需要一个 RCU 友好的结构。maple tree 合入 Linux 6.1（2022 年 12 月发布），VMA 的红黑树和链表都被取代。v6.12 的 mm_struct 里是 struct maple_tree mm_mt，Documentation/core-api/maple_tree.rst 称它是面向不重叠区间的 B 树，节点约 256 字节，可工作在 RCU 安全模式，最重要的用户是 VMA。

LWN 列出的理由针对的是二叉平衡树本身（区间表示、RCU 无锁读、遍历效率），而不是红黑树相对 AVL 的劣势。红黑树在内核里最早的用户已经离开，它仍在调度器、epoll、区间树等处服役，靠的是上面这些接口。内核自带的 rbtree.rst 还引用旧 LWN 文章，说 VMA 用红黑树管理，这在 6.1 之后已经过时。

七、谱系：从 AVL、对称二叉 B 树到 WAVL

graph LR
    AVL["AVL tree<br/>Adelson-Velsky, Landis 1962"]
    SBB["symmetric binary B-tree<br/>Bayer 1972"]
    RB["red-black tree<br/>Guibas, Sedgewick FOCS 1978"]
    T83["O(1) rotations per update<br/>Tarjan 1983"]
    AA["AA tree<br/>Andersson 1993"]
    LLRB["left-leaning RB<br/>Sedgewick 2008"]
    LNX["Linux lib/rbtree.c<br/>2.4.10, 2001"]
    WAVL["rank-balanced / WAVL<br/>Haeupler, Sen, Tarjan 2009, 2015"]
    RAVL["deletion without rebalancing<br/>Sen, Tarjan 2010, 2016"]
    ALT["AVL deletions: amortized Theta(log n) rotations<br/>Amani, Lai, Tarjan 2016"]
    SBB --> RB
    SBB --> AA
    RB --> T83
    RB --> LLRB
    RB --> LNX
    AVL --> WAVL
    T83 --> WAVL
    WAVL --> RAVL
    WAVL --> ALT

• AVL 树（Adelson-Velsky 与 Landis，1962，Soviet Mathematics Doklady）是第一种平衡二叉搜索树。
• Bayer（1972，Acta Informatica）提出对称二叉 B 树（symmetric binary B-tree），用二叉节点加“水平指针”表示 B 树节点，是红黑树的直接前身。
• Guibas 与 Sedgewick（FOCS 1978）的《A dichromatic framework for balanced trees》用红、黑两种颜色的链接统一描述 B 树族的二叉表示及其更新算法，“红黑树”的名字由此而来。
• Tarjan（1983）给出每次更新 \(O(1)\) 次旋转的红黑树更新方法，这是红黑树相对 AVL 的主要理论优势。
• Andersson（WADS 1993）实现了 Bayer 的右倾二叉 B 树（后称 AA 树），把重平衡拆成 skew 和 split 两个过程；Sedgewick 2008 年的 LLRB 走镜像的路线（只许左倾）。两者都靠打破对称减少情况数、缩短代码。
• Haeupler、Sen 与 Tarjan（WADS 2009，TALG 2015）用“秩差”（rank difference）重新统一了 AVL 和红黑树的定义，并提出弱 AVL 树（weak AVL tree，WAVL）。
• Sen 与 Tarjan（SODA 2010；与 Kim 合作的 TALG 2016 版）研究删除后完全不做重平衡的松弛 AVL 树（ravl tree）：只在插入时重平衡，树高仍不超过 \(\log_\varphi m\)，\(m\) 为插入次数。

WAVL 值得单独说明，因为它恰好落在两者之间：没有删除时，WAVL 树就是 AVL 树，高度至多 \(\log_\varphi n\)；有删除时，高度至多 \(\log_\varphi m\)，并且在任何情况下不超过 \(2\lg n\)。WAVL 树是红黑树的真子集。插入和删除都至多 2 次旋转，比红黑树删除的 3 次还少；HST 的论文说他们不知道还有别的平衡二叉树能在 2 次旋转内完成删除。WAVL 的删除重平衡总量与删除次数成线性、与插入次数无关，HST 指出红黑树没有这个性质：第一次删除的改色就可能一直传到根。

八、争论与开放问题

AVL 是否“过时”

Skiena 在《The Algorithm Design Manual》（1998 年版第 177 页）里说“AVL… trees are now passé”。HST 2015 年的论文开篇把这句话放在“红黑树每次更新最坏 \(O(1)\) 旋转、摊还 \(O(1)\) 时间”这一段历史之后引用，结论是“AVL trees are anything but passé”：把 AVL 的秩规则放松一点得到的 WAVL，同时拿到了 AVL 的高度界（无删除时）和比红黑树更好的删除旋转上界。本文 E1、E5 的数据给这场争论补了一个经验侧面：随机负载下 AVL 与红黑树的平均旋转次数几乎相同，差别集中在最坏情形和平衡信息写入量上。

AVL 删除的摊还代价曾经是这场讨论里悬而未决的一环。HST 猜想插删交替可以让每次删除都做 \(\Omega(\log n)\) 次旋转，但没有给出构造；Amani、Lai 与 Tarjan（2016）给出了构造，并指出难点在于一对昂贵的删除—插入之后得到的通常不是原来的树：若这族树的高度 \(k\) 为偶数，要 \(2^{k/2}\) 对操作才能回到原树。

LLRB：代码短是否值得

Sedgewick 的 LLRB 论文稿主张，限制 3-node 只能左倾后，插入和删除的代码只有常规红黑树实现的三分之一到四分之一，并把它用在《Algorithms》第 4 版里。反方有理论和实测两方面的依据。理论上，HST 指出只许单侧倾斜的二叉化 2-3 树或红黑树，插入和删除在最坏情况下都需要 \(\Omega(\lg n)\) 次旋转；允许 3-node 两种倾向，才把插入的最坏旋转数降到 2。实测上，Kohler 的笔记和本文 E1、E4、E5 都显示 LLRB 删除的旋转、改色和比较次数成倍增加，本文 E1 中单次插入最多旋转 18 次。Kohler 以 jemalloc 作者 Jason Evans 的文章《Left-leaning red-black trees are hard to implement》为引子，认为 LLRB 并不比经典实现更容易写对；他也承认更复杂的 LLRB 删除实现可以省掉许多旋转，但那样就失去了代码短的初衷。本文的 LLRB 用的是《Algorithms》里的简单版本，数字只代表这一实现。

随机键下平衡树的平均情形

随机插入的普通二叉搜索树有成熟的数学模型：平均查找代价约 \(2\ln n\)，平均高度的系数也已知（略小于 \(3\lg n\)）。平衡树却没有。Sedgewick 在 LLRB 论文稿里写道，所有主要红黑树变体在随机键下“接近最优 \(\lg N\)”的表现都只是猜想、尚未证明，为平衡树建立相应的数学模型是“分析算法领域的突出难题之一”。他观察到 LLRB 在随机键下的平均查找长度接近 \(\lg N - 0.5\)、平均高度约 \(2\ln N\)，并明确说高度这个值“纯属猜测”。本文 E3 中 LLRB 的高度 28 与 \(2\ln 2^{20} \approx 27.7\) 吻合，但这仍是实验而非证明。

HST 列出的开放问题

HST 的论文结尾列了几个与本文直接相关的问题：WAVL 高度界 \(\log_\varphi m\) 的证明用的是依赖更新历史的计数论证，能否换成只依赖当前树状态的势函数；红黑树的自顶向下重平衡能否得到与 WAVL 类似的按秩指数衰减的界（他们猜想可以）；以及能否系统地（例如用线性规划）为这类分析求出最优常数。他们还认为 AVL 树不存在固定前瞻的自顶向下插入删除算法（“we think there is none”）；而自顶向下重平衡只需锁住 \(O(1)\) 个节点，这是 WAVL 和红黑树在并发实现上相对 AVL 的一个结构性优势。

九、工程上怎么选

• 查找占绝大多数、主要是插入：两者的查找深度差距在 1% 以内，选哪个都行。若关心最坏查找路径（例如实时系统的最坏响应时间），AVL 的 \(1.44\lg n\) 比红黑树的 \(2\lg n\) 更紧，升序插入时实测 21 对 38。
• 删除频繁、特别是反复删除最小值的队列式用法：红黑树保证每次删除至多 3 次旋转，AVL 在 E4 中单次删除最多 15 次。对增强树，每次旋转都要回调重算附加值，最坏旋转次数有界更有价值。
• 无锁读或 RCU 场景：二叉平衡树的旋转本身不是原子的，Linux 的做法是降级为“可能漏查”的无锁查找，或用 latch tree 保存两份副本；需要真正并发友好的区间索引时，内核选择了 maple tree 这样的 B 树。
• 需要更少的旋转且愿意实现新结构：WAVL 的插入删除都至多 2 次旋转，无删除时就是 AVL，理论性质优于两者，代价是要自己实现并验证。
• 不要为了“代码短”选 LLRB 作为通用容器：删除代价成倍增加，而经典红黑树可以直接复用成熟实现（例如 Linux lib/rbtree.c）。
• 节点大小不是区分因素：颜色 1 位、平衡因子 2 位，都能塞进对齐指针的低位。

十、参考资料

规范与文档

• Linux v6.12，Documentation/core-api/rbtree.rst（Red-black Trees (rbtree) in Linux，Rob Landley）。
• Linux v6.12，Documentation/core-api/maple_tree.rst。
• Linux 2.4.10 ChangeLog（ChangeLog-2.4.10，kernel.org pub/linux/kernel/v2.4/）：“Andrea Arkangeli: major VM merge”。

源码

• Linux v6.12：lib/rbtree.c、include/linux/rbtree.h、include/linux/rbtree_types.h、include/linux/rbtree_augmented.h、include/linux/rbtree_latch.h、include/linux/interval_tree_generic.h、include/linux/mm_types.h、kernel/sched/fair.c（entity_before、__enqueue_entity、pick_eevdf）。
• Linux 2.2.26 mm/mmap_avl.c、include/linux/mm.h；Linux 2.4.9 mm/mmap.c、include/linux/sched.h（AVL_MIN_MAP_COUNT）；Linux 2.4.10 lib/rbtree.c、include/linux/rbtree.h。
• Linux 提交 55a981027fc3，David Woodhouse，“[RBTREE] Merge colour and parent fields of struct rb_node.”，2006-04-21。
• Linux 提交 17d9ddc72fb8，Venkatesh Pallipadi，“rbtree: Add support for augmented rbtrees”，2010-02-10。
• Linux 提交 14b94af0b251，Michel Lespinasse，“rbtree: faster augmented rbtree manipulation”，2012-10-08。
• Linux 提交 d72da4a4d973，Peter Zijlstra，“rbtree: Make lockless searches non-fatal”，2015-05-27；ade3f510f93a，“rbtree: Implement generic latch_tree”，2015-05-27。
• Linux 提交 cd9e61ed1eeb，Davidlohr Bueso，“rbtree: cache leftmost node internally”，2017-09-08。
• Linux 提交 99d4d26551b5，Peter Zijlstra，“rbtree: Add rb_add_augmented_cached() helper”，2023-05-31。
• R. Sedgewick, K. Wayne, Algorithms, 4th ed., RedBlackBST.java（本文 LLRB 删除的依据）。

核心论文

• G. M. Adelson-Velsky, E. M. Landis, “An algorithm for the organization of information”, Soviet Mathematics Doklady 3, 1962, pp. 1259–1263.
• R. Bayer, “Symmetric binary B-Trees: Data structure and maintenance algorithms”, Acta Informatica 1(4), 1972, pp. 290–306.
• L. J. Guibas, R. Sedgewick, “A dichromatic framework for balanced trees”, 19th Annual Symposium on Foundations of Computer Science (FOCS), 1978, pp. 8–21.
• R. E. Tarjan, “Updating a balanced search tree in O(1) rotations”, Information Processing Letters 16(5), 1983, pp. 253–257.
• R. Sedgewick, “Left-leaning Red-Black Trees”, 2008（论文稿，作者主页发布）。
• B. Haeupler, S. Sen, R. E. Tarjan, “Rank-Balanced Trees”, ACM Transactions on Algorithms 11(4), 2015；初版见 WADS 2009, pp. 351–362.

其他论文

• S. Huddleston, K. Mehlhorn, “A new data structure for representing sorted lists”, Acta Informatica 17(2), 1982, pp. 157–184.
• K. Mehlhorn, A. Tsakalidis, “An amortized analysis of insertions into AVL-trees”, SIAM Journal on Computing 15(1), 1986, pp. 22–33.
• A. Andersson, “Balanced search trees made simple”, WADS 1993, pp. 60–71.
• S. Sen, R. E. Tarjan, “Deletion without rebalancing in balanced binary trees”, SODA 2010, pp. 1490–1499；S. Sen, R. E. Tarjan, D. H. K. Kim, “Deletion without rebalancing in binary search trees”, ACM Transactions on Algorithms 12(4), 2016.
• M. Amani, K. A. Lai, R. E. Tarjan, “Amortized rotation cost in AVL trees”, Information Processing Letters 116(5), 2016, pp. 327–330（预印本 arXiv:1506.03528）。
• D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., §6.2.3（AVL 高度界）。
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., Chapter 13（红黑树性质、引理 13.1、插入与删除修复）。
• S. S. Skiena, The Algorithm Design Manual, 1998, p. 177（经 HST 2015 转引）。

工程资料

• J. Corbet, “Introducing maple trees”, LWN.net, 2021-02-12, https://lwn.net/Articles/845507/。
• Kernel Newbies, “Linux 6.1”（maple tree 合入），https://kernelnewbies.org/Linux_6.1。
• E. Kohler, “Left-Leaning Red-Black Trees Considered Harmful”, https://read.seas.harvard.edu/~kohler/notes/llrb.html。

实验

• reproduce/bst_count.c：AVL、红黑树、LLRB 的旋转、平衡标记写入、比较次数与树高计数，第一节表格与第五节 E1–E6 的全部数据。
• reproduce/kernel_rbtree/kernel_count.c 与 reproduce/kernel_rbtree/shim/：在用户态编译 Linux v6.12 lib/rbtree.c，逐操作对照旋转次数与最终树。
• reproduce/run.sh：下载并校验内核源码、编译、自检、对照、完整实验；reproduce/results.txt 为本文使用的输出。

系列导航： - 上一篇：XXH3 与 wyhash：SIMD 累加器和 128 位标量乘法两条提速路线 - 下一篇：B-tree 深度解剖：从磁盘 I/O 模型到 boltdb 源码

相关阅读： - epoll 的数据结构：红黑树、就绪队列与回调机制 - 进程调度：从 CFS 到 EEVDF - Treap 与跳表：随机平衡的期望代价与生产参数