自己亲自动手把红黑树实现一遍，发现理论成功了要转换为实际代码还是有点难度的，困难点主要在于一些边界点的确定。花了两小时才把所有的东西调通，还是需要进一步提高自己的C功力。
直接贴代码吧，有需要的拿去用，我自己也留着以后拿来玩玩。
这份代码肯定是需要根据实际环境进行修改的，前两天大概扫了一下 《Linux内核中的红黑树》里面的代码，发现自己写的代码水平跟大神写的还是有些差距啊...加油吧。
//rb_tree.h
[cpp]
#include
#include
#ifndef RB_TREE
#define RB_TREE
typedef struct{int value;}rbtree_key;
typedef struct{int value;}rbtree_data;
typedef enum rbtree_color{RB_RED,RB_BLACK}rbtree_color;
int rbtree_key_cmp(rbtree_key x,rbtree_key y);
typedef struct rbtree_node rbtree_node;
//rb tree node
struct rbtree_node{
rbtree_key key;
rbtree_color color;
rbtree_data data;
rbtree_node *parent;
rbtree_node *left;
rbtree_node *right;
};
rbtree_node * rb_nil;
static int rb_nil_inited;
void rbtree_init_nil();
void rbtree_destroy_nil();
void rbtree_node_cpy(rbtree_node *source,rbtree_node *dest);
rbtree_node * rbtree_search(rbtree_node * t,rbtree_key key);
rbtree_node * rbtree_search_iterative(rbtree_node * t,rbtree_key key);
rbtree_node * rbtree_min(rbtree_node *t);
rbtree_node * rbtree_max(rbtree_node *t);
rbtree_node * rbtree_successor(rbtree_node *t);
rbtree_node * rbtree_predecessor(rbtree_node *t);
void rbtree_insert(rbtree_node **root,rbtree_node *z);
void rbtree_insert_fixup(rbtree_node **root,rbtree_node *z);
void rbtree_delete(rbtree_node **root,rbtree_node *z);
void rbtree_delete_fixup(rbtree_node **root,rbtree_node *z);
void rbtree_left_roate(rbtree_node **root,rbtree_node *z);
void rbtree_right_roate(rbtree_node **root,rbtree_node *z);
#endif
#include
#include
#ifndef RB_TREE
#define RB_TREE
typedef struct{int value;}rbtree_key;
typedef struct{int value;}rbtree_data;
typedef enum rbtree_color{RB_RED,RB_BLACK}rbtree_color;
int rbtree_key_cmp(rbtree_key x,rbtree_key y);
typedef struct rbtree_node rbtree_node;
//rb tree node
struct rbtree_node{
rbtree_key key;
rbtree_color color;
rbtree_data data;
rbtree_node *parent;
rbtree_node *left;
rbtree_node *right;
};
rbtree_node * rb_nil;
static int rb_nil_inited;
void rbtree_init_nil();
void rbtree_destroy_nil();
void rbtree_node_cpy(rbtree_node *source,rbtree_node *dest);
rbtree_node * rbtree_search(rbtree_node * t,rbtree_key key);
rbtree_node * rbtree_search_iterative(rbtree_node * t,rbtree_key key);
rbtree_node * rbtree_min(rbtree_node *t);
rbtree_node * rbtree_max(rbtree_node *t);
rbtree_node * rbtree_successor(rbtree_node *t);
rbtree_node * rbtree_predecessor(rbtree_node *t);
void rbtree_insert(rbtree_node **root,rbtree_node *z);
void rbtree_insert_fixup(rbtree_node **root,rbtree_node *z);
void rbtree_delete(rbtree_node **root,rbtree_node *z);
void rbtree_delete_fixup(rbtree_node **root,rbtree_node *z);
void rbtree_left_roate(rbtree_node **root,rbtree_node *z);
void rbtree_right_roate(rbtree_node **root,rbtree_node *z);
#endif
rb_tree.c
[cpp]
#include "rb_tree.h"
int rbtree_key_cmp(rbtree_key x,rbtree_key y){
return y.value-x.value;
}
void rbtree_node_cpy(rbtree_node *source,rbtree_node *dest){
dest->key.value = source->key.value;
dest->data.value = source->data.value;
}
void rbtree_init_nil(){
if(!rb_nil_inited){
rb_nil = (rbtree_node *)malloc(sizeof(rbtree_node));
rb_n