测试颜色和设置颜色也是水到渠成的事了。需要特别指出的是下面的一个内联函数：
| staticinline void rb_link_node(struct rb_node * node, struct rb_node *parent, struct rb_node ** rb_link); |
它把parent设为node的父结点，并且让rb_link指向node。
我们把重点集中在lib/rbtree.c上，看看一些和红黑树相关的重要算法。开始之前我们一起回忆一下红黑树的规则：
1.每个结点要么是红色要么是黑色；
2.根结点必须是黑色；
3.红结点如果有孩子，其孩子必须都是黑色；
4.从根结点到叶子的每条路径必须包含相同数目的黑结点。
这四条规则可以限制一棵排序树是平衡的。
__rb_rotate_left是把以root为根的树中的node结点进行左旋，__rb_rotate_right是进行右旋。这两个函数是为后面的插入和删除服务，而不是为外部提供接口。
新插入的结点都设为叶子，染成红色，插入后如果破坏了上述规则，通过调整颜色和旋转可以恢复，二叉树又重新平衡。插入操作的接口函数是
| voidrb_insert_color(struct rb_node *node, struct rb_root *root); |
它把已确定父结点的node结点融入到以root为根的红黑树中，具体算法的分析可以参考[1]中第14.3节，这里的实现和书中的讲解几乎完全一样。怎么确定node的父结点应该在调用rb_insert_color之前通过手工迭带完成。值得指出的一点是，虽然插入操作需要一个循环迭代，但是总的旋转次数不会超过两次！所以效率还是很乐观的。
