这里不涉及到avl树和红黑树谁优谁劣，只是谈谈在两种实现的一些细节，以及最后给出一些性能比较。
这里先给出linux下面的红黑树的实现，因为linux下面的两个宏定义不好直接使用，原型如下：
#definerb_entry(ptr, type, member) container_of(ptr, type, member)#ifndef container_of/** * container_of - cast a member of a structure out to the containing structure * @ptr:the pointer to the member. * @type:the type of the container struct this is embedded in. * @member:the name of the member within the struct. * */#define container_of(ptr, type, member) ({\const typeof(((type *)0)->member) * __mptr = (ptr);\(type *)((char *)__mptr - offsetof(type, member)); })#endif#ifndef offsetof#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)#endif
修改如下：
#ifndef offsetof#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)#endif#ifndef container_of/** * container_of - cast a member of a structure out to the containing structure * @ptr:the pointer to the member. * @type:the type of the container struct this is embedded in. * @member:the name of the member within the struct. * * !!! modify the typeof marco, just use the rb_node */#define container_of(ptr, type, member) \(((char *)ptr) - offsetof(type, member))#endif#definerb_entry(ptr, type, member) container_of(ptr, type, member)
语义可以认为不变的。
linux的RB_TREE源代码移植到vc上后，命名为：rb_tree.h， 如下：
/* Red Black Trees (C) 1999 Andrea Arcangeli <andrea@suse.de> This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA linux/include/linux/rbtree.h To use rbtrees you'll have to implement your own insert and search cores. This will avoid us to use callbacks and to drop drammatically performances. I know it's not the cleaner way, but in C (not in C++) to get performances and genericity... Some example of insert and search follows here. The search is a plain normal search over an ordered tree. The insert instead must be implemented in two steps: First, the code must insert the element in order as a red leaf in the tree, and then the support library function rb_insert_color() must be called. Such function will do the not trivial work to rebalance the rbtree, if necessary.-----------------------------------------------------------------------static inline struct page * rb_search_page_cache(struct inode * inode, unsigned long offset){struct rb_node * n = inode->i_rb_page_cache.rb_node;struct page * page;while (n){page = rb_entry(n, struct page, rb_page_cache);if (offset < page->offset)n = n->rb_left;else if (offset > page->offset)n = n->rb_right;elsereturn page;}return NULL;}static inline struct page * __rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node){struct rb_node ** p = &inode->i_rb_page_cache.rb_node;struct rb_node * parent = NULL;struct page * page;while (*p){parent = *p;page = rb_entry(parent, struct page, rb_page_cache);if (offset < page->offset)p = &(*p)->rb_left;else if (offset > page->offset)p = &(*p)->rb_right;elsereturn page;}rb_link_node(node, parent, p);return NULL;}static inline struct page * rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node){struct page * ret;if ((ret = __rb_insert_page_cache(inode, offset, node)))goto out;rb_insert_color(node, &inode->i_rb_page_cache); out:return ret;}-----------------------------------------------------------------------*/#ifndef_LINUX_RBTREE_H#define_LINUX_RBTREE_H#define EXPORT_SYMBOL(i)#pragma pack (push)#pragma pack(4)struct rb_node{unsigned long rb_parent_color;#defineRB_RED0#defineRB_BLACK1struct rb_node *rb_right;struct rb_node *rb_left;} ;#pragma pack (pop) /* The alignment might seem pointless, but allegedly CRIS needs it */struct rb_root{structrb_node *rb_node;int(*cmp)(void *src, void *dst);void(*insert)(struct rb_root *root, void *ins);void(*remove)(struct rb_root *root, void *del);};#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))#define rb_color(r) ((r)->rb_parent_color & 1)#define rb_is_red(r) (!rb_color(r))#define rb_is_black(r) rb_color(r)#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p){rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;}static inline void rb_set_color(struct rb_node *rb, int color){rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;}#ifndef offsetof#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)#endif#ifndef container_of/** * container_of - cast a member of a structure out to the containing structure * @ptr:the pointer to the member. * @type:the type of the container struct this is embedded in. * @member:the name of the member within the struct. * * !!! modify the typeof marco, just use the rb_node */#define container_of(ptr, type, member) \(((char *)ptr) - offsetof(type, member))#endif#define RB_ROOT(struct rb_root) { NULL, }#definerb_entry(ptr, type, member) container_of(ptr, type, member)#define RB_EMPTY_ROOT(root)((root)->rb_node == NULL)#define RB_EMPTY_NODE(node)(rb_parent(node) == node)#define RB_CLEAR_NODE(node)(rb_set_parent(node, node))static inline void rb_init_node(struct rb_node *rb){rb->rb_parent_color = 0;rb->rb_right = NULL;rb->rb_left = NULL;RB_CLEAR_NODE(rb);}extern void rb_insert_color(struct rb_node *, struct rb_root *);extern void rb_erase(struct rb_node *, struct rb_root *);typedef void (*rb_augment_f)(struct rb_node *node, void *data);extern void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data);extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);extern void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data);/* Find logical next and previous nodes in a tree */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 *);/* Fast replacement of a single node without remove/rebalance/add/rebalance */extern void rb_replace_node(struct rb_node *victim, struct rb_node *new_node_node, struct rb_root *root);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;}#endif/* _LINUX_RBTREE_H */
实现文件移植之后，命名为rb_tree.cpp， 如下：
/* Red Black Trees (C) 1999 Andrea Arcangeli <andrea@suse.de> (C) 2002 David Woodhouse <dwmw2@infradead.org> This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA linux/lib/rbtree.c*/#include "rb_tree.h"static void __rb_rotate_left(struct rb_node *node, struct rb_root *root){struct rb_node *right = node->rb_right;struct rb_node *parent = rb_parent(node);if ((node->rb_right = right->rb_left))rb_set_parent(right->rb_left, node);right->rb_left = node;rb_set_parent(right, parent);if (parent){if (node == parent->rb_left)parent->rb_left = right;elseparent->rb_right = right;}elseroot->rb_node = right;rb_set_parent(node, right);}static void __rb_rotate_right(struct rb_node *node, struct rb_root *root){struct rb_node *left = node->rb_left;struct rb_node *parent = rb_parent(node);if ((node->rb_left = left->rb_right))rb_set_parent(left->rb_right, node);left->rb_right = node;rb_set_parent(left, parent);if (parent){if (node == parent->rb_right)parent->rb_right = left;elseparent->rb_left = left;}elseroot->rb_node = left;rb_set_parent(node, left);}void rb_insert_color(struct rb_node *node, struct rb_root *root){struct rb_node *parent, *gparent;while ((parent = rb_parent(node)) && rb_is_red(parent)){gparent = rb_parent(parent);if (parent == gparent->rb_left){{register struct rb_node *uncle = gparent->rb_right;if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node = gparent;continue;}}if (parent->rb_right == node){register struct rb_node *tmp;__rb_rotate_left(parent, root);tmp = parent;parent = node;node = tmp;}rb_set_black(parent);rb_set_red(gparent);__rb_rotate_right(gparent, root);} else {{register struct rb_node *uncle = gparent->rb_left;if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node = gparent;continue;}}if (parent->rb_left == node){register struct rb_node *tmp;__rb_rotate_right(parent, root);tmp = parent;parent = node;node = tmp;}rb_set_black(parent);rb_set_red(gparent);__rb_rotate_left(gparent, root);}}rb_set_black(root->rb_node);}EXPORT_SYMBOL(rb_insert_color);static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root){struct rb_node *other;while ((!node || rb_is_black(node)) && node != root->rb_node){if (parent->rb_left == node){other = parent->rb_right;if (rb_is_red(other)){rb_set_black(other);rb_set_red(parent);__rb_rotate_left(parent, root);other = parent->rb_right;}if ((!other->rb_left || rb_is_black(other->rb_left)) && (!other->rb_right || rb_is_black(other->rb_right))){rb_set_red(other);node = parent;parent = rb_parent(node);}else{if (!other->rb_right || rb_is_black(other->rb_right)){rb_set_black(other->rb_left);rb_set_red(other);__rb_rotate_right(other, root);other = parent->rb_right;}rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other->rb_right);__rb_rotate_left(parent, root);node = root->rb_node;break;}}else{other = parent->rb_left;if (rb_is_red(other)){rb_set_black(other);rb_set_red(parent);__rb_rotate_right(parent, root);other = parent->rb_left;}if ((!other->rb_left || rb_is_black(other->rb_left)) && (!other->rb_right || rb_is_black(other->rb_right))){rb_set_red(other);node = parent;parent = rb_parent(node);}else{if (!other->rb_left || rb_is_black(other->rb_left)){rb_set_black(other->rb_right);rb_set_red(other);__rb_rotate_left(other, root);other = parent->rb_left;}rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other->rb_left);__rb_rotate_right(parent, root);node = root->rb_node;break;}}}if (node)rb_set_black(node);}void rb_erase(struct rb_node *node, struct rb_root *root){struct rb_node *child, *parent;int color;if (!node->rb_left)child = node->rb_right;else if (!node->rb_right)child = node->rb_left;else{struct rb_node *old = node, *left;node = node->rb_right;while ((left = node->rb_left) != NULL)node = left;if (rb_parent(old)) {if (rb_parent(old)->rb_left == old)rb_parent(old)->rb_left = node;elserb_parent(old)->rb_right = node;} elseroot->rb_node = node;child = node->rb_right;parent = rb_parent(node);color = rb_color(node);if (parent == old) {parent = node;} else {if (child)rb_set_parent(child, parent);parent->rb_left = child;node->rb_right = old->rb_right;rb_set_parent(old->rb_right, node);}node->rb_parent_color = old->rb_parent_color;node->rb_left = old->rb_left;rb_set_parent(old->rb_left, node);goto color;}parent = rb_parent(node);color = rb_color(node);if (child)rb_set_parent(child, parent);if (parent){if (parent->rb_left == node)parent->rb_left = child;elseparent->rb_right = child;}elseroot->rb_node = child; color:if (color == RB_BLACK)__rb_erase_color(child, parent, root);}EXPORT_SYMBOL(rb_erase);static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data){struct rb_node *parent;up:func(node, data);parent = rb_parent(node);if (!parent)return;if (node == parent->rb_left && parent->rb_right)func(parent->rb_right, data);else if (parent->rb_left)func(parent->rb_left, data);node = parent;goto up;}/* * after inserting @node into the tree, update the tree to account for * both the new_node entry and any damage done by rebalance */void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data){if (node->rb_left)node = node->rb_left;else if (node->rb_right)node = node->rb_right;rb_augment_path(node, func, data);}EXPORT_SYMBOL(rb_augment_insert);/* * before removing the node, find the deepest node on the rebalance path * that will still be there after @node gets removed */struct rb_node *rb_augment_erase_begin(struct rb_node *node){struct rb_node *deepest;if (!node->rb_right && !node->rb_left)deepest = rb_parent(node);else if (!node->rb_right)deepest = node->rb_left;else if (!node->rb_left)deepest = node->rb_right;else {deepest = rb_next(node);if (deepest->rb_right)deepest = deepest->rb_right;else if (rb_parent(deepest) != node)deepest = rb_parent(deepest);}return deepest;}EXPORT_SYMBOL(rb_augment_erase_begin);/* * after removal, update the tree to account for the removed entry * and any rebalance damage. */void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data){if (node)rb_augment_path(node, func, data);}EXPORT_SYMBOL(rb_augment_erase_end);/* * This function returns the first node (in sort order) of the tree. */struct rb_node *rb_first(const struct rb_root *root){struct rb_node*n;n = root->rb_node;if (!n)return NULL;while (n->rb_left)n = n->rb_left;return n;}EXPORT_SYMBOL(rb_first);struct rb_node *rb_last(const struct rb_root *root){struct rb_node*n;n = root->rb_node;if (!n)return NULL;while (n->rb_right)n = n->rb_right;return n;}EXPORT_SYMBOL(rb_last);struct rb_node *rb_next(const struct rb_node *node){struct rb_node *parent;if (rb_parent(node) == node)return NULL;/* If we have a right-hand child, go down and then left as far as we can. */if (node->rb_right) {node = node->rb_right; while (node->rb_left)node=node->rb_left;return (struct rb_node *)node;}/* No right-hand children. Everything down and left is smaller than us, so any 'next' node must be in the general direction of our parent. Go up the tree; any time the ancestor is a right-hand child of its parent, keep going up. First time it's a left-hand child of its parent, said parent is our 'next' node. */while ((parent = rb_parent(node)) && node == parent->rb_right)node = parent;return parent;}EXPORT_SYMBOL(rb_next);struct rb_node *rb_prev(const struct rb_node *node){struct rb_node *parent;if (rb_parent(node) == node)return NULL;/* If we have a left-hand child, go down and then right as far as we can. */if (node->rb_left) {node = node->rb_left; while (node->rb_right)node=node->rb_right;return (struct rb_node *)node;}/* No left-hand children. Go up till we find an ancestor which is a right-hand child of its parent */while ((parent = rb_parent(node)) && node == parent->rb_left)node = parent;return parent;}EXPORT_SYMBOL(rb_prev);void rb_replace_node(struct rb_node *victim, struct rb_node *new_node, struct rb_root *root){struct rb_node *parent = rb_parent(victim);/* Set the surrounding nodes to point to the replacement */if (parent) {if (victim == parent->rb_left)parent->rb_left = new_node;elseparent->rb_right = new_node;} else {root->rb_node = new_node;}if (victim->rb_left)rb_set_parent(victim->rb_left, new_node);if (victim->rb_right)rb_set_parent(victim->rb_right, new_node);/* Copy the pointers/colour from the victim to the replacement */*new_node = *victim;}EXPORT_SYMBOL(rb_replace_node);
其实，可以看出，linux内核里面并没有提供直接可以用的insert delete 以及walk遍历的函数接口，linux提供的是最基本一个插入节点后的re-fixup， 删除后的re-fixup，以及walk需要的get-firt, get-next等等。
这里是需要自己提供插入，删除，以及walk函数的，相比freebsd的avl树，完全就是一步到位了，而且好用很多，这里不谈谁好用，然后举例简单说说怎么使用linux的基本的这些函数，晚点会比较二者在插入删除以及walk方面的优劣。
自己提供相应的一些接口了，时间有限随便写写：
应用头文件，rb_tree_main.h：
#ifndef RB_TREE_MAIN_H#define RB_TREE_MAIN_H#include "rb_tree.h"void my_insert(struct rb_root *root, void *ins);int my_cmp(void *src, void *dest);void my_rb_walk(const struct rb_root *root);void my_remove(struct rb_root *g_my_root, void *del);#endif
man文件：rb_tree_main.cpp
// rb_tree_main.cpp : Defines the entry point for the console application.//#include <string.h>#include <stdlib.h>#include "rb_tree.h"#include "rb_tree_main.h"typedef struct my_rb{ int rand_val; struct rb_node my_rb_node;}my_rb;struct rb_root g_my_root = {NULL, my_cmp, my_insert, my_remove};void my_insert(struct rb_root *root, void *ins){ struct my_rb *iter; struct my_rb *src = (struct my_rb *)ins; struct rb_node **p = &root->rb_node; struct rb_node *parent = NULL; if(!ins) { return; } while (*p != NULL) { parent = *p; iter = (struct my_rb *)rb_entry(parent, struct my_rb, my_rb_node); if (root->cmp(src, iter) < 0) p = &(*p)->rb_left; else p = &(*p)->rb_right; } rb_link_node(&src->my_rb_node, parent, p); rb_insert_color(&src->my_rb_node, root);}int my_cmp(void *src, void *dest){ struct my_rb *my_src = (struct my_rb *)src; struct my_rb *my_dest = (struct my_rb *)dest; if(!my_src || !my_dest) { return 0; } if(my_src->rand_val < my_dest->rand_val) { return -1; } else if(my_src->rand_val > my_dest->rand_val) { return 1; } else { return 0; }}void my_remove(struct rb_root *g_my_root, void *del){ struct my_rb *entry = NULL; struct my_rb *del_node = (struct my_rb *)del; struct rb_node *n = NULL; if(!g_my_root || !del) { return; } n = g_my_root->rb_node; while (n) { entry = (struct my_rb *)rb_entry(n, struct my_rb, my_rb_node); if (g_my_root->cmp(entry, del_node) > 0) { n = n->rb_left; } else if (g_my_root->cmp(entry, del_node) < 0) { n = n->rb_right; } else { rb_erase(n, g_my_root); free(entry); entry = NULL; return ; } } return ;}void my_rb_walk(const struct rb_root *root){ struct rb_node *temp = rb_first(root); struct my_rb *my_entry = NULL; while(temp) { my_entry = (struct my_rb *)rb_entry(temp, my_rb, my_rb_node); printf("node with rand_val %d .\n", my_entry->rand_val); temp = rb_next(temp); }}int main(int argc, char* argv[]){ struct my_rb *my_rb_node = NULL; struct my_rb del_node = {4, {0}}; for (int i = 0; i < 5; i++) { my_rb_node = (struct my_rb *)malloc(sizeof *my_rb_node); memset(my_rb_node, 0, sizeof *my_rb_node); my_rb_node->rand_val = i; g_my_root.insert(&g_my_root, my_rb_node); } my_rb_walk(&g_my_root); g_my_root.remove(&g_my_root, &del_node); my_rb_walk(&g_my_root); return 0;}
注意四点：
1、insert里面的双重指针，直接找到要插入的位置的父节点，省去了一堆赋值比如parent->left or right = p, p->parent 啥啥啥的，直接在父节点（叶子节点）的左或者右节点NULL的取一次地址，然后，地址上面写值，不细说了；
2、插入的节点应该动态分配，或者是已经静态分配好的多个节点
3、删除操作，内核提供的只是re-fixup，不会帮你释放内存的，我们要做的是找到这个节点，然后调用内核提供的rb_erase，把节点从rb树上移去，如果是动态分配，再释放之。
4、内核的红黑树是带有parent属性的，只是么有用指针，而是把parent和left和right子标记用了一个字段而已：
unsigned long rb_parent_color;
最低的一位用作了left和right的flag，最高的31位，用作存储parent指针的地址，这种rb树就要求插入的节点地址必须是偶数的，一般的cpu架构使得分配出来的内存都是偶数地址对齐的了，但是有些也会以奇数开始，比如ppc，就可能动态分配出一个节点就是从奇数地址开始的。只要是偶数地址开始那么地址的最低位一定是0了。
其实在3.0.1的内核里面是这种rb设计，在早期的内核里面rb_node就是另外一种设计了，是引入了parent指针的，比如2.6.11的内核的结构体设计如下：
struct rb_node{struct rb_node *rb_parent;int rb_color;#defineRB_RED0#defineRB_BLACK1struct rb_node *rb_right;struct rb_node *rb_left;};
其实在freebsd 8.0的avl树64位设计就是这种，32二位的设计类似于早些时候的内核的rb树的节点设计：
#ifndef _LP64struct avl_node {struct avl_node *avl_child[2];/* left/right children */struct avl_node *avl_parent;/* this node's parent */unsigned short avl_child_index;/* my index in parent's avl_child[] */short avl_balance;/* balance value: -1, 0, +1 */};#else /* _LP64 *//* * for 64 bit machines, avl_pcb contains parent pointer, balance and child_index * values packed in the following manner: * * |63 3| 2 |1 0 | * |-------------------------------------|-----------------|-------------| * | avl_parent hi order bits | avl_child_index | avl_balance | * | | | + 1 | * |-------------------------------------|-----------------|-------------| * */struct avl_node {struct avl_node *avl_child[2];/* left/right children nodes */uintptr_t avl_pcb;/* parent, child_index, balance */};
#endif
说这么多，以后再说freebsd的avl树咋用的吧。
销售世界上第一号的产品–不是汽车，而是自己。
