Linux辅导：解读Linux内核中的红黑树

会计考友

红黑树是平衡二叉树的一种，它有很好的性质，树中的结点都是有序的，而且因为它本身就是平衡的，所以查找也不会出现非常恶劣的情况，基于二叉树的操作的时间复杂度是O(log(N))。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。 　　先到include/linux/rbtree.h中看一下红黑树的一些定义，如下：
　　structrb_node
　　{
　　unsignedlong  rb_parent_color;
: |: W3 o) Q' L8 F　　#defineRB_RED          0
* n& [$ q. c7 d3 v: z0 P: q( Y' C　　#defineRB_BLACK        1
　　structrb_node *rb_right;
　　structrb_node *rb_left;
　　}__attribute__((aligned(sizeof(long))));
　　structrb_root只是structrb_node*的一个包装，这样做的好处是看起来不用传递二级指针了。不错，很简单。再看一下下面几个重要的宏，细心的你一定会发现，rb_parent_color其实没那么简单，AndreaArcangeli在这里使用了一个小的技巧，不过非常棒。正如名字所暗示，这个成员其实包含指向parent的指针和此结点的颜色！它是怎么做到的呢？很简单，对齐起了作用。既然是sizeof(long)大小的对齐，那么在IA-32上，任何rb_node结构体的地址的低两位肯定都是零，与其空着不用，还不如用它们表示颜色，反正颜色就两种，其实一位就已经够了。
: x& ~2 N; U  @　　这样，提取parent指针只要把rb_parent_color成员的低两位清零即可：
　　#definerb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
1 m) D4 j% O% I/ z2 y3 |* P6 c　　取颜色只要看最后一位即可：
4 i5 O% d0 {0 W　　#definerb_color(r)   ((r)->rb_parent_color & 1)
　　测试颜色和设置颜色也是水到渠成的事了。需要特别指出的是下面的一个内联函数：
2 U" l% _) \" L/ [0 ^6 E5 P/ ^% F　　staticinline void rb_link_node(struct rb_node * node, struct rb_node *parent, struct rb_node ** rb_link);

- O& i# ]. C. ~: S1 [　　它把parent设为node的父结点，并且让rb_link指向node。

会计考友

</p>　　我们把重点集中在lib/rbtree.c上，看看一些和红黑树相关的重要算法。开始之前我们一起回忆一下红黑树的规则：
& e: O2 j" Z$ \　　1.每个结点要么是红色要么是黑色；
　　2.根结点必须是黑色；
& d$ J* f0 x' g; l4 J( i  Z9 D　　3.红结点如果有孩子，其孩子必须都是黑色；
! w  I2 D. v$ M9 j: a　　4.从根结点到叶子的每条路径必须包含相同数目的黑结点。
0 X4 m2 D8 b9 Y( E　　这四条规则可以限制一棵排序树是平衡的。
* P1 R* {% T4 Z  Y( o2 Y2 H　　__rb_rotate_left是把以root为根的树中的node结点进行左旋，__rb_rotate_right是进行右旋。这两个函数是为后面的插入和删除服务，而不是为外部提供接口。
/ Z, J  k, c( l8 c- s% B1 o　　新插入的结点都设为叶子，染成红色，插入后如果破坏了上述规则，通过调整颜色和旋转可以恢复，二叉树又重新平衡。插入操作的接口函数是
　　voidrb_insert_color(struct rb_node *node, struct rb_root *root);
2 w- z8 h. ~4 f% {1 X　　它把已确定父结点的node结点融入到以root为根的红黑树中，具体算法的分析可以参考[1]中第14.3节，这里的实现和书中的讲解几乎完全一样。怎么确定node的父结点应该在调用rb_insert_color之前通过手工迭带完成。值得指出的一点是，虽然插入操作需要一个循环迭代，但是总的旋转次数不会超过两次！所以效率还是很乐观的。
　　删除操作多多少少都有点麻烦，它要先执行像普通二叉查找树的“删除”，然后根据删除结点的颜色来判断是否执行进一步的操作。删除的接口是：
　　voidrb_erase(struct rb_node *node, struct rb_root *root);
. Q: a# j1 j; ?; h7 V+ U  t　　其实它并没有真正删除node，而只是让它和以root为根的树脱离关系，最后它还要判断是否调用__rb_erase_color来调整。具体算法的讲解看参考[1]中第13.3和14.4节，__rb_erase_color对应书中的RB-DELETE-FIXUP，此处的实现和书上也基本上一致。
　　其余的几个接口就比较简单了。
2 L# u5 U) A& N4 Q　　structrb_node *rb_first(struct rb_root *root);
$ B8 w$ o" H$ K  G$ b　　在以root为根的树中找出并返回最小的那个结点，只要从根结点一直向左走就是了。
　　structrb_node *rb_last(struct rb_root *root);
) T  G: P: f& p  J　　是找出并返回最大的那个，一直向右走。
6 v/ Y- p. A: s1 V) p, w　　structrb_node *rb_next(struct rb_node *node);
, S7 p# `+ }) N1 c$ t+ l$ T　　返回node在树中的后继，这个稍微复杂一点。如果node的右孩子不为空，它只要返回node的右子树中最小的结点即可；如果为空，它要向上查找，找到迭带结点是其父亲的左孩子的结点，返回父结点。如果一直上述到了根结点，返回NULL。
# k: X0 G$ J! S3 n) I　　structrb_node *rb_prev(struct rb_node *node);
　　返回node的前驱，和rb_next中的操作对称。
' x0 O. K$ Q2 F0 E, @/ @/ i　　voidrb_replace_node(struct rb_node *victim, struct rb_node *new, structrb_root *root);
　　用new替换以root为根的树中的victim结点。