Linux内核深入学习（4）——内核常见的数据结构2——红黑树

Linux内核深入学习（3）——内核常见的数据结构2红黑树

红黑树

​ 红黑树是一个非常经典也是非常难懂的数据结构，它的数据结构定义在include/linux/rbtree_types.h上，同时，操作则是在include/linux/rbtree.h

啥是红黑树？

​ 红黑树红黑树首先是一个树，他是从二叉树中飞叉出来的一个数据结构，对于最朴实的二叉树（只有本体，左子节点指针、右子节点指针），他还多了父节点指针以及颜色标识。其中颜色标识是红黑树的亮点！

​ 我们关心的是红黑树在静态上颜色必须满足的规则！这些规则实则保证树一定是近似平衡的

1. 根节点恒黑：整棵树的顶点必须为黑色，这为颜色调整提供了基准点。
2. 叶子（NIL）皆黑：所有空节点被视为黑色叶子，统一了路径计算的终点。
3. 红节点无赤子：红色节点的子节点必须为黑色，防止连续红色节点破坏平衡。
4. 黑高恒定：从任意节点到其所有叶子节点的路径包含相同数量的黑色节点（称为黑高）。
5. 新叶染红：插入的新节点初始化为红色，最小化对黑高的影响。

这些规则共同作用，确保从根到叶子的最长路径不超过最短路径的两倍。数学证明表明，含有n个节点的红黑树高度始终满足h ≤ 2log₂(n+1)，这为各项操作的对数时间复杂度提供了理论保证。

插入操作可能出现的操作：

当新节点以红色身份加入红黑树时，可能引发两种冲突场景：双红冲突（父节点同为红色）与根节点变色。插入后的平衡调整如同精密的机械校准，包含三种基本操作：

颜色翻转（Recoloring）
当新节点的父节点和叔节点均为红色时，执行祖父节点变红、父叔节点染黑的色彩变换。这种操作如同电路中的信号传递，将颜色冲突向上层转移，可能递归触发新的调整。

单旋转（Rotation）
当双红节点形成线性结构（左-左或右-右排列），需进行单旋操作。以左旋为例：祖父节点变为父节点的右子，原父节点右子变为祖父节点的左子，同时更新颜色标记。这种操作在常数时间内重构局部结构，恢复颜色约束。

双旋转（Double Rotation）
当冲突节点呈折线排列（左-右或右-左），需先对父节点执行单旋转换为线性结构，再对祖父节点进行反向旋转。这种复合操作虽然步骤较多，但时间复杂度仍保持为O(1)。

删除操作

节点删除引发的平衡破坏更为复杂，特别是移除黑色节点时可能导致黑高失衡。删除算法需要处理四种主要情形：

情形1：后继为红色
当被删节点的继承者（右子树最小节点）为红色时，直接将其染黑即可保持黑高。这种简单情况约占总删除操作的40%。

情形2：远侄子为红
若被删节点的兄弟节点存在红色远侄子（与兄弟同侧的侄子），执行颜色传递与单旋转。例如右兄弟的右子为红时，将兄弟颜色传给父节点，远侄子染黑，并进行左旋。

情形3：近侄子为红
当仅有近侄子（与兄弟异侧的侄子）为红色时，需先旋转兄弟节点转换为情形2，再按情形2处理。这种两步调整确保颜色分布符合规则。

情形4：兄弟节点为黑
当兄弟节点及其子节点均为黑色时，将兄弟染红并将失衡向上传递。这种情形可能递归至根节点，最终通过全局调整恢复平衡。

删除操作的调整过程同样自底向上进行，平均需要1.5次旋转操作。算法通过精心设计的条件判断与状态转移，确保每次调整都在局部范围内完成，避免全局重构带来的性能损耗。

Linux对红黑树的抽象

​ 在include/linux/rbtree_types.h中

/* SPDX-License-Identifier: GPL-2.0-or-later */
#ifndef _LINUX_RBTREE_TYPES_H
#define _LINUX_RBTREE_TYPES_Hstruct rb_node {unsigned long  __rb_parent_color;struct rb_node *rb_right;struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */struct rb_root {struct rb_node *rb_node;
};
#define RB_ROOT (struct rb_root) { NULL, }
#endif

​ 笔者稍微略去了一些没有关系的数据结构，这就是咱们的红黑树。可以看到，Linux对红黑树做的操作很简单，就比正常的红黑树多了父亲节点和对应的颜色，需要注意的是——你可能会问父亲节点呢？答案是使用位运算将父指针与颜色信息打包在同一字段内，减少内存占用和缓存失误率。

​ 这里也就能看到了我们的红黑树的静态初始化，实际上就是将整个结构体制空。

struct rb_root mytree = RB_ROOT;

等同于将 mytree.rb_node = NULL，表示空树状态。如需在运行时初始化，亦可将 struct rb_root 置零或直接赋值 RB_ROOT。插入前，宿主结构体的 struct rb_node node; 无需特别初始化，仅在调用 rb_link_node() 后才需设置父子指针，由后续重平衡函数处理颜色位和指针调整。

核心API与操作

插入操作

• 首先沿树搜索合适插入位置，记录目标父节点和插入点指针地址。换而言之，我们需要自己连接两个子节点，内核不负责比较大小决定插入到哪里，整个数据结构只负责维护平衡，所以需要我们自己找出来预计的插入的节点位置。
• 调用 rb_link_node(&data->node, parent, new_link) 建立节点与父关系。
• 随后调用 rb_insert_color(&data->node, &mytree) 执行必要的旋转与重着色操作，恢复红黑树性质。

static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,struct rb_node **rb_link)
{node->__rb_parent_color = (unsigned long)parent;node->rb_left = node->rb_right = NULL;*rb_link = node;
}

1. rb_link_node() 函数

• 将新节点 node 初步链接到树结构中
• node->__rb_parent_color 存储父节点指针（通过强制类型转换）并默认颜色为红（最低位为0）
• 清空新节点的左右子节点指针
• 通过 *rb_link 将新节点挂载到父节点的正确位置（左/右子节点指针）

static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;while (true) {/** Loop invariant: node is red.*/if (unlikely(!parent)) {/** The inserted node is root. Either this is the* first node, or we recursed at Case 1 below and* are no longer violating 4).*/rb_set_parent_color(node, NULL, RB_BLACK);break;}/** If there is a black parent, we are done.* Otherwise, take some corrective action as,* per 4), we don't want a red root or two* consecutive red nodes.*/if(rb_is_black(parent))break;gparent = rb_red_parent(parent);tmp = gparent->rb_right;if (parent != tmp) {	/* parent == gparent->rb_left */if (tmp && rb_is_red(tmp)) {/** Case 1 - node's uncle is red (color flips).**       G            g*      / \          / \*     p   u  -->   P   U*    /            /*   n            n** However, since g's parent might be red, and* 4) does not allow this, we need to recurse* at g.*/rb_set_parent_color(tmp, gparent, RB_BLACK);rb_set_parent_color(parent, gparent, RB_BLACK);node = gparent;parent = rb_parent(node);rb_set_parent_color(node, parent, RB_RED);continue;}tmp = parent->rb_right;if (node == tmp) {/** Case 2 - node's uncle is black and node is* the parent's right child (left rotate at parent).**      G             G*     / \           / \*    p   U  -->    n   U*     \           /*      n         p** This still leaves us in violation of 4), the* continuation into Case 3 will fix that.*/tmp = node->rb_left;WRITE_ONCE(parent->rb_right, tmp);WRITE_ONCE(node->rb_left, parent);if (tmp)rb_set_parent_color(tmp, parent,RB_BLACK);rb_set_parent_color(parent, node, RB_RED);augment_rotate(parent, node);parent = node;tmp = node->rb_right;}/** Case 3 - node's uncle is black and node is* the parent's left child (right rotate at gparent).**        G           P*       / \         / \*      p   U  -->  n   g*     /                 \*    n                   U*/WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */WRITE_ONCE(parent->rb_right, gparent);if (tmp)rb_set_parent_color(tmp, gparent, RB_BLACK);__rb_rotate_set_parents(gparent, parent, root, RB_RED);augment_rotate(gparent, parent);break;} else {tmp = gparent->rb_left;if (tmp && rb_is_red(tmp)) {/* Case 1 - color flips */rb_set_parent_color(tmp, gparent, RB_BLACK);rb_set_parent_color(parent, gparent, RB_BLACK);node = gparent;parent = rb_parent(node);rb_set_parent_color(node, parent, RB_RED);continue;}tmp = parent->rb_left;if (node == tmp) {/* Case 2 - right rotate at parent */tmp = node->rb_right;WRITE_ONCE(parent->rb_left, tmp);WRITE_ONCE(node->rb_right, parent);if (tmp)rb_set_parent_color(tmp, parent,RB_BLACK);rb_set_parent_color(parent, node, RB_RED);augment_rotate(parent, node);parent = node;tmp = node->rb_left;}/* Case 3 - left rotate at gparent */WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */WRITE_ONCE(parent->rb_left, gparent);if (tmp)rb_set_parent_color(tmp, gparent, RB_BLACK);__rb_rotate_set_parents(gparent, parent, root, RB_RED);augment_rotate(gparent, parent);break;}}
}

2. __rb_insert() 函数
循环处理红黑树插入后的平衡调整，主要处理三种经典情况：

Case 1：叔父节点为红色

• 执行颜色翻转：父节点、叔节点变黑，祖父节点变红
• 将当前节点指针上移至祖父节点，继续向上递归调整
• 例如当新节点n的父p和叔u均为红色时：

      G(B)            G(R)  /  \            /  \  p(R) u(R)  →   p(B) u(B)  /              /  
  n(R)          n(R)  
  

Case 2：叔父为黑且形成三角结构

• 先通过单旋转转换为线性结构
• 例如新节点n是父p的右子时：
  对p执行左旋，使n成为p的父节点

      G             G  /             /  p(R)   →     n(R)  \          /  n(R)     p(R)  
  

Case 3：叔父为黑且形成线性结构

• 对祖父节点执行单旋转并重新着色
• 例如左-左结构时：
  对G执行右旋，p成为新父节点，G变红，p变黑

      G(B)          p(B)  /            /   \  p(R)   →    n(R)  G(R)  /  
  n(R)  
  

关键实现细节

• WRITE_ONCE 宏确保指针修改的原子性，防止并发访问问题
• augment_rotate 回调函数用于处理旋转时的额外数据结构维护（如AVL树的高度更新）
• 颜色信息通过 __rb_parent_color 的最低比特位存储（0:红，1:黑）
• 循环通过向上遍历（node = gparent）处理颜色冲突传播
• 最终根节点强制设为黑色保持规则

删除节点

• 直接调用 rb_erase(&victim->node, &mytree)，内核自动完成平衡调整并移除节点。
• 若仅需替换节点，可使用 rb_replace_node(&old->node, &new->node, &mytree)，但需保证键不变，否则树结构将被破坏。

void rb_erase(struct rb_node *node, struct rb_root *root)
{struct rb_node *rebalance;rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);if (rebalance)____rb_erase_color(rebalance, root, dummy_rotate);	/* need balance */
}

static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,const struct rb_augment_callbacks *augment)
{struct rb_node *child = node->rb_right;struct rb_node *tmp = node->rb_left;struct rb_node *parent, *rebalance;unsigned long pc;if (!tmp) {/** Case 1: node to erase has no more than 1 child (easy!)** Note that if there is one child it must be red due to 5)* and node must be black due to 4). We adjust colors locally* so as to bypass __rb_erase_color() later on.*/pc = node->__rb_parent_color;parent = __rb_parent(pc);__rb_change_child(node, child, parent, root);if (child) {child->__rb_parent_color = pc;rebalance = NULL;} elserebalance = __rb_is_black(pc) ? parent : NULL;tmp = parent;} else if (!child) {/* Still case 1, but this time the child is node->rb_left */tmp->__rb_parent_color = pc = node->__rb_parent_color;parent = __rb_parent(pc);__rb_change_child(node, tmp, parent, root);rebalance = NULL;tmp = parent;} else {struct rb_node *successor = child, *child2;tmp = child->rb_left;if (!tmp) {/** Case 2: node's successor is its right child**    (n)          (s)*    / \          / \*  (x) (s)  ->  (x) (c)*        \*        (c)*/parent = successor;child2 = successor->rb_right;augment->copy(node, successor);} else {/** Case 3: node's successor is leftmost under* node's right child subtree**    (n)          (s)*    / \          / \*  (x) (y)  ->  (x) (y)*      /            /*    (p)          (p)*    /            /*  (s)          (c)*    \*    (c)*/do {parent = successor;successor = tmp;tmp = tmp->rb_left;} while (tmp);child2 = successor->rb_right;WRITE_ONCE(parent->rb_left, child2);WRITE_ONCE(successor->rb_right, child);rb_set_parent(child, successor);augment->copy(node, successor);augment->propagate(parent, successor);}tmp = node->rb_left;WRITE_ONCE(successor->rb_left, tmp);rb_set_parent(tmp, successor);pc = node->__rb_parent_color;tmp = __rb_parent(pc);__rb_change_child(node, successor, tmp, root);if (child2) {rb_set_parent_color(child2, parent, RB_BLACK);rebalance = NULL;} else {rebalance = rb_is_black(successor) ? parent : NULL;}successor->__rb_parent_color = pc;tmp = successor;}augment->propagate(tmp, NULL);return rebalance;
}

基础流程

1. 确定实际删除节点
   • 若目标节点有两个子节点，寻找右子树的最小节点（后继节点）作为实际删除节点
   • 通过augment->copy将后继节点数据复制到原节点位置，物理上删除后继节点

三种删除情形
情形1：单子节点删除

• 当被删节点只有左/右单个子节点时：
  a. 用子节点直接替换被删节点
  b. 若子节点为红（根据红黑树规则必为红），染黑即可保持平衡
  c. 若子节点不存在且被删节点为黑，标记需要后续平衡(rebalance)

情形2：后继为右子节点

• 当后继节点是被删节点的直接右子时：
  a. 用后继节点替换被删节点
  b. 处理原后继节点的右子树
  c. 若原后继节点为黑且无子节点，标记需要平衡

情形3：后继位于右子树深层

• 当后继节点位于右子树的最左端时：
  a. 将后继节点提升到被删节点位置
  b. 原后继节点的右子接管其原位置
  c. 调整父子指针关系，维护树形结构

关键操作细节

• __rb_change_child：安全更新父节点对子节点的引用
• WRITE_ONCE：确保指针修改的原子性，防止并发问题
• __rb_parent_color：通过位操作同时存储父指针和颜色信息
• augment回调：用于维护额外数据（如子树大小等增强信息）

平衡标记传递

• rebalance变量标记需要开始重新平衡的起始节点
• 若删除黑节点导致黑高失衡，返回待平衡节点供后续__rb_erase_color处理
• 通过颜色判断决定是否需要触发平衡调整流程

static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;while (true) {/** Loop invariants:* - node is black (or NULL on first iteration)* - node is not the root (parent is not NULL)* - All leaf paths going through parent and node have a*   black node count that is 1 lower than other leaf paths.*/sibling = parent->rb_right;if (node != sibling) {	/* node == parent->rb_left */if (rb_is_red(sibling)) {/** Case 1 - left rotate at parent**     P               S*    / \             / \*   N   s    -->    p   Sr*      / \         / \*     Sl  Sr      N   Sl*/tmp1 = sibling->rb_left;WRITE_ONCE(parent->rb_right, tmp1);WRITE_ONCE(sibling->rb_left, parent);rb_set_parent_color(tmp1, parent, RB_BLACK);__rb_rotate_set_parents(parent, sibling, root,RB_RED);augment_rotate(parent, sibling);sibling = tmp1;}tmp1 = sibling->rb_right;if (!tmp1 || rb_is_black(tmp1)) {tmp2 = sibling->rb_left;if (!tmp2 || rb_is_black(tmp2)) {/** Case 2 - sibling color flip* (p could be either color here)**    (p)           (p)*    / \           / \*   N   S    -->  N   s*      / \           / \*     Sl  Sr        Sl  Sr** This leaves us violating 5) which* can be fixed by flipping p to black* if it was red, or by recursing at p.* p is red when coming from Case 1.*/rb_set_parent_color(sibling, parent,RB_RED);if (rb_is_red(parent))rb_set_black(parent);else {node = parent;parent = rb_parent(node);if (parent)continue;}break;}/** Case 3 - right rotate at sibling* (p could be either color here)**   (p)           (p)*   / \           / \*  N   S    -->  N   sl*     / \             \*    sl  sr            S*                       \*                        sr** Note: p might be red, and then both* p and sl are red after rotation(which* breaks property 4). This is fixed in* Case 4 (in __rb_rotate_set_parents()*         which set sl the color of p*         and set p RB_BLACK)**   (p)            (sl)*   / \            /  \*  N   sl   -->   P    S*       \        /      \*        S      N        sr*         \*          sr*/tmp1 = tmp2->rb_right;WRITE_ONCE(sibling->rb_left, tmp1);WRITE_ONCE(tmp2->rb_right, sibling);WRITE_ONCE(parent->rb_right, tmp2);if (tmp1)rb_set_parent_color(tmp1, sibling,RB_BLACK);augment_rotate(sibling, tmp2);tmp1 = sibling;sibling = tmp2;}/** Case 4 - left rotate at parent + color flips* (p and sl could be either color here.*  After rotation, p becomes black, s acquires*  p's color, and sl keeps its color)**      (p)             (s)*      / \             / \*     N   S     -->   P   Sr*        / \         / \*      (sl) sr      N  (sl)*/tmp2 = sibling->rb_left;WRITE_ONCE(parent->rb_right, tmp2);WRITE_ONCE(sibling->rb_left, parent);rb_set_parent_color(tmp1, sibling, RB_BLACK);if (tmp2)rb_set_parent(tmp2, parent);__rb_rotate_set_parents(parent, sibling, root,RB_BLACK);augment_rotate(parent, sibling);break;} else {sibling = parent->rb_left;if (rb_is_red(sibling)) {/* Case 1 - right rotate at parent */tmp1 = sibling->rb_right;WRITE_ONCE(parent->rb_left, tmp1);WRITE_ONCE(sibling->rb_right, parent);rb_set_parent_color(tmp1, parent, RB_BLACK);__rb_rotate_set_parents(parent, sibling, root,RB_RED);augment_rotate(parent, sibling);sibling = tmp1;}tmp1 = sibling->rb_left;if (!tmp1 || rb_is_black(tmp1)) {tmp2 = sibling->rb_right;if (!tmp2 || rb_is_black(tmp2)) {/* Case 2 - sibling color flip */rb_set_parent_color(sibling, parent,RB_RED);if (rb_is_red(parent))rb_set_black(parent);else {node = parent;parent = rb_parent(node);if (parent)continue;}break;}/* Case 3 - left rotate at sibling */tmp1 = tmp2->rb_left;WRITE_ONCE(sibling->rb_right, tmp1);WRITE_ONCE(tmp2->rb_left, sibling);WRITE_ONCE(parent->rb_left, tmp2);if (tmp1)rb_set_parent_color(tmp1, sibling,RB_BLACK);augment_rotate(sibling, tmp2);tmp1 = sibling;sibling = tmp2;}/* Case 4 - right rotate at parent + color flips */tmp2 = sibling->rb_right;WRITE_ONCE(parent->rb_left, tmp2);WRITE_ONCE(sibling->rb_right, parent);rb_set_parent_color(tmp1, sibling, RB_BLACK);if (tmp2)rb_set_parent(tmp2, parent);__rb_rotate_set_parents(parent, sibling, root,RB_BLACK);augment_rotate(parent, sibling);break;}}
}

这段代码实现了红黑树删除节点后的再平衡逻辑（即红黑树删除算法中的颜色调整阶段），通过处理四种经典情况恢复红黑树的平衡性。整个函数以被删节点的父节点 parent 为起点，逐步向上调整直至满足红黑树规则。

循环条件

• 当前节点 node 为黑色（初始时为被删节点的替代节点）
• parent 不为空（未到达根节点）
• 经过 parent 和 node 的路径黑高比其他路径少1

四大处理情形
情形1：兄弟节点为红色

• 执行左旋/右旋将兄弟节点变为黑色
• 例如当 node 是左子且兄弟为红时：
  对父节点左旋，原兄弟节点成为新祖父，其左子变为新兄弟
  旋转后兄弟节点必为黑，进入后续情形处理

情形2：兄弟及其子节点均为黑色

• 将兄弟节点染红，使经过父节点的路径黑高减1
• 若父节点原为红色：
  • 直接染黑父节点，补足黑高，终止调整
• 若父节点原为黑色：
  • 将 node 上移至父节点，继续向上递归调整

情形3：兄弟为黑且远侄子为黑

• 通过旋转将远侄子变为红色
• 例如当 node 是左子且兄弟的右子为黑时：
  对兄弟节点右旋，使兄弟的左子（原红）成为新兄弟
  旋转后进入情形4处理

情形4：兄弟为黑且远侄子为红

• 对父节点左旋/右旋，并通过颜色调整补足黑高
  例如：
  1. 兄弟的远侄子染黑
  2. 父节点染黑
  3. 兄弟节点继承原父节点颜色
  4. 旋转操作将子树黑高恢复
     此情形可彻底消除黑高失衡，结束调整循环

实现细节

1. 方向对称处理

   • 代码分为 node == parent->rb_left 和 node == parent->rb_right 两个镜像分支
   • 每个分支内处理逻辑对称，但旋转方向相反

2. 原子写操作

   • 使用 WRITE_ONCE 宏保证指针修改的原子性
   • 防止多线程环境下的内存访问冲突

3. 颜色传播

   • rb_set_parent_color 同时设置父指针和颜色
   • 颜色信息通过指针变量的最低比特位存储（0:红，1:黑）

4. 增强回调

   • augment_rotate 函数指针用于维护额外数据结构
   • 在旋转时同步更新附加信息（如子树统计值）

调整示例

以 node 为左子且兄弟为黑为例：

初始状态（情形4）:P(B)              P(B)/   \             /   \N(B)  S(B)  →     N(B)  S(B)\                 \Sr(R)            Sr(R)处理步骤:
1. 左旋父节点 P  
2. 将 S 染为 P 的原色  
3. 将 P 染黑  
4. 将 Sr 染黑  最终状态:S(P_color)/   \P(B)  Sr(B)/
N(B)

终止条件

• 情形2中父节点为红时直接染黑终止
• 情形4通过旋转重构后完全恢复平衡
• 调整传递至根节点时自动结束

遍历

• 按序访问

  • rb_first(&mytree) 返回最小节点；
  • rb_next(node) 返回在中序遍历下的后继节点；
  • rb_last() 和 rb_prev() 类似操作；
    通过循环可轻松实现排序访问：

  for (node = rb_first(&mytree); node; node = rb_next(node))process(rb_entry(node, struct mytype, node));
  

• 查找
  红黑树不提供通用查找函数，用户需自行编写：

  struct mytype *my_search(struct rb_root *root, key_t key) {struct rb_node *n = root->rb_node;while (n) {data = rb_entry(n, struct mytype, node);if (key < data->key) n = n->rb_left;else if (key > data->key) n = n->rb_right;else return data;}return NULL;
  }