红黑树是一种自平衡二叉搜索树。红黑树和AVL树类似，但是最差情况下的插入和删除更快，查询时间稍微变慢，但仍然是O(log n)。
Linux红黑树实现在/lib/rbtree.c，头文件linux/rbtree.h
Linux红黑树对速度进行了优化，减少了一层indirection，提高了缓存命中率。和list一样，每个struct rb_node节点嵌入到数据结构中。
为了不丢失性能，需要自己实现插入和搜索函数。
结构体
1 2 3 4 5 6 7 8 9 10 | struct 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;}; |
__rb_parent_color用来存储parent节点的地址和颜色，低2位用于父节点的颜色。
为了学习，定义people结构体，将rb_node嵌入其中。定义rb_root变量people_tree。
1 2 3 4 5 6 7 | static struct rb_root people_tree = RB_ROOT;struct people{ int score; struct rb_node node;}; |
插入：需要自己找到插入的位置，然后插入，然后旋转上色。示例代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | int people_insert(struct rb_root *root, struct people *people){ struct rb_node **new = &(root->rb_node), *parent = NULL; struct people *this; while (*new) { this = rb_entry(*new, struct people, node); parent = *new; if (people->score > this->score) new = &((*new)->rb_right); else if (people->score < this->score) new = &((*new)->rb_left); else return 0; } rb_link_node(&people->node, parent, new); rb_insert_color(&people->node, root); return 1;} |
parent是父节点，new是要插入的父节点的子节点的地址。
rb_link_node()插入节点：将parent的子节点指向新节点，将新节点的父设置为parent，将新节点的左右子节点设置为NULL。
rb_insert_color()：进行上色旋转，保持为红黑树。
遍历：4个接口
1 2 3 4 | extern struct rb_node *rb_next(const struct rb_node *);extern struct rb_node *rb_prev(const struct rb_node *);extern struct rb_node *rb_first(const struct rb_root *);extern struct rb_node *rb_last(const struct rb_root *); |
用于正向遍历和逆向遍历，正向遍历：
1 2 3 4 5 6 7 8 9 10 11 | void people_interate(struct rb_root *root){ struct rb_node *node = rb_first(root); struct people *this; while (node) { this = rb_entry(node, struct people, node); printk("%d\n", this->score); node = rb_next(node); }} |
使用rb_first获取最左边的节点，然后使用rb_next遍历所有的节点。逆向遍历是对应的另外两个接口。
搜索：自己写2叉树搜索：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | struct rb_node * people_search(struct rb_root *root, int score){ struct rb_node *node = root->rb_node; while (node) { struct people *this = rb_entry(node, struct people, node); if (score < this->score) node = node->rb_left; else if (score > this->score) node = node->rb_right; else { return node; } } return NULL;} |
删除：使用封装好的接口：
1 | extern void rb_erase(struct rb_node *, struct rb_root *); |
正向遍历的时候，从最左侧的节点开始，每次都要花费logN的代价寻找最左侧节点，为了解决这个问题，引出了cached rbtree，它添加一个指针变量存储最左侧节点。
1 2 3 4 | struct rb_root_cached { struct rb_root rb_root; struct rb_node *rb_leftmost;}; |
初始化
1 | struct rb_root_cached mytree = RB_ROOT_CACHED; |
涉及到最左的节点的，有cached接口：
1 2 3 | struct rb_node *rb_first_cached(struct rb_root_cached *tree); void rb_insert_color_cached(struct rb_node *, struct rb_root_cached *, bool); void rb_erase_cached(struct rb_node *node, struct rb_root_cached *); |
有些特定的树并不能用前面的普通红黑树实现，Linux实现了一种增强红黑树，这种树，每个节点还存储了一个信息，该信息由所有的子节点确定。
区间树（interval tree）是典型的应用例子。区间树每个节点存储它的区间[lo, hi]，同时还存储所有子节点的区间的最大值。树是按lo索引的二叉树。
增强树通过3个回调函数来维护：
A propagation callback
A copy callback
A tree rotation callback
参考
https://lwn.net/Articles/184495/
Document/rbtree.txt