1.1.1 随处可见的红黑树

用在哪里:

• hashmap
• cfs
• epoll
• 定时器
• …

应用实现:

• key-value(强查找)
• 顺序

强查找类型有:

• 红黑树
• hash
• b/b+tree
• 跳表

性质:

• 每个节点为红色或者黑色
• 根节点黑色
• 叶子节点黑色
• 如果一个节点为红色,则他的两个儿子为黑色(不存在两个连续红色)
• 对每个节点,从该节点到其子孙节点的所有路径上的黑节点数目相同

初始化定义:

#define RBTREE_ENTRY(name,type) \
    struct name{                \
        type *left;             \
        type *right;            \
        type *parent;           \
        unsigned char color;    \
    }

typedef int KEY_TYPE;

typedef struct rbtree_node
    {
        KEY_TYPE key;
        void *value;
#if 1
        rbtree_node *left;
        rbtree_node *right;
        rbtree_node *parent;
        unsigned char color;
#else
        RBTREE_ENTRY(,rbtree_node)node;
#endif
    } rbtree_node;

typedef struct rbtree
    {
        rbtree_node *root;
        rbtree_node *nil;
    } rbtree;

红黑树性质被破环时,进行旋转:左旋/右旋