//rbtree.h#ifndef _RBTREE_H_#define _RBTREE_H_#include 
    
     #include 
     
      #include 
      
       typedef unsigned int rbtree_key_t;typedef unsigned char u_char;typedef struct rbtree_node_s rbtree_node_t;struct rbtree_node_s{    rbtree_key_t    key;    rbtree_node_t   *left;    rbtree_node_t   *right;    rbtree_node_t   *parent;    u_char            color;    string            data;//
       
          };typedef struct rbtree_s rbtree_t;typedef void (*rbtree_insert_pt) (rbtree_node_t *root,//函数指针,可以实现自定义插入方法        rbtree_node_t *node, rbtree_node_t *sentinel);struct rbtree_s{    rbtree_node_t    *root;    rbtree_node_t    *sentinel;//all leaf nodes point to the sentinel node    rbtree_insert_pt insert;};void rbtree_insert_value(rbtree_node_t *temp, rbtree_node_t *node,        rbtree_node_t *sentinel);#define rbt_red(node)            ((node)->color = 1)#define rbt_black(node)            ((node)->color = 0)#define rbt_is_red(node)        ((node)->color)#define rbt_is_black(node)        (!rbt_is_red(node))#define rbt_copy_color(n1, n2)    (n1->color = n2->color)#define rbtree_sentinel_init(node)    rbt_black(node)#define rbtree_init(tree, s, i)        \    rbtree_sentinel_init(s);        \    (tree)->root = s;                \    (tree)->sentinel = s;            \    (tree)->insert = i#endif//rbtree.cpp#include "rbtree.h"static inline void rbtree_left_rotate(rbtree_node_t **root, rbtree_node_t *sentinel,        rbtree_node_t *node);/*root是二级指针*/static inline void rbtree_right_rotate(rbtree_node_t **root, rbtree_node_t *sentinel,        rbtree_node_t *node);void rbtree_insert_fixup(rbtree_node_t **root, rbtree_node_t *sentinel,        rbtree_node_t *node){    rbtree_node_t *temp;    while(node != *root && rbt_is_red(node->parent))    {        if(node->parent == node->parent->parent->left)//left        {            temp = node->parent->parent->right;//右叔叔            //case 1            if(rbt_is_red(temp))            {                rbt_black(node->parent);                rbt_black(temp);                rbt_red(node->parent->parent);                node = node->parent->parent;            }            else//black            {                //case 2                if(node == node->parent->right)//RR                {                    node = node->parent;                    rbtree_left_rotate(root, sentinel, node);                }                //case 3                rbt_black(node->parent);                rbt_red(node->parent->parent);                rbtree_right_rotate(root, sentinel, node->parent->parent);            }        }        else//symmetric        {            temp = node->parent->parent->left;//左叔叔            //case 1            if(rbt_is_red(temp))            {                rbt_black(node->parent);                rbt_black(temp);                rbt_red(node->parent->parent);                node = node->parent->parent;            }            else//black            {                //case 2                if(node == node->parent->left)//LL                {                    node = node->parent;                    rbtree_right_rotate(root, sentinel, node);                }                //case 3                rbt_black(node->parent);                rbt_red(node->parent->parent);                rbtree_left_rotate(root, sentinel, node->parent->parent);            }        }    }    rbt_black(*root);}void rbtree_insert(rbtree_t *tree, rbtree_node_t *node){    rbtree_node_t **root, *temp, *sentinel;    root = &tree->root;    sentinel = tree->sentinel;    if(*root == sentinel)    {        node->parent = NULL;        node->left = sentinel;        node->right = sentinel;        rbt_black(node);        *root = node;        return;    }    tree->insert(*root, node, sentinel);    /*rbtree-insert-fixup*/    rbtree_insert_fixup(root, sentinel, node);//将blance操作封装了一下}void rbtree_insert_value(rbtree_node_t *temp, rbtree_node_t *node,        rbtree_node_t *sentinel){    rbtree_node_t **p;    //与常规二叉树插入类似    for(;;)    {        p = (node->key < temp->key) ? &temp->left : &temp->right;        if(*p == sentinel)        {            break;        }        temp = *p;    }    *p = node;//此处*p已经具有孩子节点的左右属性,不必像算法导论书中一样来判断左右属性,二级指针很强大^-^    node->parent = temp;    node->left = sentinel;    node->right = sentinel;    rbt_red(node);}static inline voidrbtree_left_rotate(rbtree_node_t **root, rbtree_node_t *sentinel,        rbtree_node_t *node){    rbtree_node_t* tmp;    /*       |                       |       x                       y      / \                     / \     a   y     ---left--->   x   c        / \                 / \       b   c               a   b     */    /*node = x*/    tmp = node->right;    node->right = tmp->left;    //父节点设置---3个    if(tmp->left != sentinel)    {        tmp->left->parent = node;    }    tmp->parent = node->parent;    if(node == *root)    {        *root = tmp;    }    else if(node == node->parent->left)    {        node->parent->left = tmp;    }    else    {        node->parent->right = tmp;    }    tmp->left = node;    node->parent = tmp;}static inline voidrbtree_right_rotate(rbtree_node_t **root, rbtree_node_t *sentinel,        rbtree_node_t *node){    rbtree_node_t* tmp;    /*       |                       |       x                       y      / \                     / \     a   y     <---right--   x   c        / \                 / \       b   c               a   b     */    /*node = y*/    tmp = node->left;    node->left = tmp->right;    if(tmp->right != sentinel)    {        tmp->right->parent = node;    }    tmp->parent = node->parent;    if(node == *root)    {        *root = tmp;    }    else if(node == node->parent->left)    {        node->parent->left = tmp;    }    else    {        node->parent->right = tmp;    }    tmp->right = node;    node->parent = tmp;}