红黑树是一种二叉平衡树，在每一个结点增加了一个存储位表示结点的颜色，以维持它的平衡；
红黑树性质
（1）红黑树结点有如下域：color，key，left，right，p；我们把这些NIL结点是为指向外结点的指针，可以自己定义；
（2）每一个结点不是红的就是黑的，根节点和NIL结点都是黑的；
（3）如果一个节点是红的，那么它的父亲和两个孩子都是黑的；
（4）对于每一个结点，它到其子孙结点的所有路径上的包含相同数目的black结点，并不要求父节点到每一层的黑高度相同；
注1：可以使用同一的一个NIL来表示所有的叶子结点和根部的父节点，这样可以减少浪费内存，该NIL的父亲就是上述的普通结点，这样查找不成功时，就可以重新回到根节点root；注2：设某个结点x出发到达任意一个节点的任意路径上，黑结点的个数称为该节点的黑高度，bh(x)表示；可归纳证明出根节点至少有2^h-1个结点，故n>=2^h-1，求得h<=2lg(n+1)；
红黑树插入（1）为了保持上述红黑树的性质（4），插入的节点z颜色一定是红色，其父节点为p;
（2）若刚开始树为空，则z是根节点，p为NIL节点，则将z的结点改为黑色；
（3）若p的颜色是黑色，则直接插入，因为红黑树的性质完全保持；
（4）若p的颜色是红色，违反红黑树的性质3，此时要讨论情况；
（4.1）若p是p父亲的左孩子；
（4.1.1）若p的兄弟节点ps是红色，则改变p和ps为黑色，p父节点改为红色，此时p父节点为新的z，继续判别；
（4.1.2）若p的兄弟节点ps是黑色，且z是父亲的右孩子，做一次左旋，到情况（4.1.3）；
（4.1.3）若p的兄弟节点ps是黑色，且z是父亲的左孩子，做一次右旋，改变z父亲颜色为黑色，z祖父颜色为红色，完毕；
（4.2）若p是p父亲的右孩子；情况与（4.1）类似，执行相反的动作；
（5）始终将根节点的颜色置为黑，因为处理时根节点有可能变红；
（6）时间复杂度为O(lgn)，空间复杂度为O(1)；
红黑树删除（1）首先根据二叉平衡树的删除原理，找到被删除的节点y，x是y的子女（肯定只有一个），x会连接到y的父亲上；
（2）若y为红色，直接删掉，因为红黑树的性质保持不变；
（3）若y为黑色节点，x为红色，则直接删掉y，将x变为黑色；
（4）若y为黑色节点，x（可以为NIl节点）为黑色，则删掉y，将x变为双黑色；
（4.1）若x是x父亲的左孩子，分别有四种情况来讨论；
（4.1.1）若x的兄弟是红色，则左旋一次，改变兄弟颜色为黑，父亲颜色为红，则它仍为新的x，继续；
（4.1.2）若x的兄弟是黑色，且x兄弟的两个孩子都是黑色，则去掉x的一重黑色，将兄弟颜色变为红，将去掉的一重黑色，给x的父亲，若x父亲是红色，则直接改成黑色，否则将变成双黑，成为新的x，继续；
（4.1.3）若x的兄弟是黑色，且x兄弟的右孩子黑色，左孩子是红色，则先将x兄弟那一块右旋，改色，使得x兄弟的右孩子变为红色；进入（4.1.4）；
（4.1.4）若x的兄弟是黑色，且x兄弟的右孩子红色，左孩子可任意色，则左旋，改变x兄弟右孩子颜色为黑色，兄弟变为父亲的颜色，父亲变为黑色，自己去掉一重颜色，完毕；
（4.2）若x是x父亲的右孩子，分别也有四种情况来讨论，但与（4.1）对称，相反来处理；
（5）若根为双黑，直接变为单黑，返回；
（6）时间复杂度为O(lgn)，空间复杂度为O(1)；
代码分析
（本节代码取自nginx中红黑树相关的代码）
红黑树表示typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;//红黑树节点的定义struct ngx_rbtree_node_s {ngx_rbtree_key_tkey; //关键字ngx_rbtree_node_t*left; //左子节点ngx_rbtree_node_t*right; //右子节点ngx_rbtree_node_t*parent;//父节点u_charcolor; //颜色，非红即黑u_chardata; //1个字节的节点数据，空间较小很少使用；};typedef struct ngx_rbtree_s ngx_rbtree_t;//为解决不同节点含有相同关键字元素冲突问题，设置该指针，灵活的添加冲突元素typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);//红黑树的定义struct ngx_rbtree_s {ngx_rbtree_node_t*root;//指向树的根节点，，根结点也是数据元素ngx_rbtree_node_t*sentinel; //指向哨兵NIL节点ngx_rbtree_insert_pt insert; //添加元素的函数指针};
节点颜色相关宏定义//颜色设置#define ngx_rbt_red(node)((node)->color = 1)#define ngx_rbt_black(node)((node)->color = 0)#define ngx_rbt_is_red(node)((node)->color)#define ngx_rbt_is_black(node)(!ngx_rbt_is_red(node))#define ngx_rbt_copy_color(n1, n2)(n1->color = n2->color)
寻找值最小的节点//内联函数，寻找值最小的节点static ngx_inline ngx_rbtree_node_t *ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel){while (node->left != sentinel) {node = node->left;}return node;}
红黑树初始化#define ngx_rbtree_init(tree, s, i)\ngx_rbtree_sentinel_init(s);\(tree)->root = s;\(tree)->sentinel = s;\(tree)->insert = i
其中tree代表红黑树管理结构，s代表NIL节点，i代表添加元素的函数；
/* a sentinel must be black */#define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)左旋转和右旋转//左旋转static ngx_inline voidngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,ngx_rbtree_node_t *node){ngx_rbtree_node_t *temp;temp = node->right;//要旋转节点的右孩子pnode->right = temp->left; //当前节点的右孩子指向改变p的左孩子if (temp->left != sentinel) { //不是NIL节点时temp->left->parent = node; //修改父亲的指向}temp->parent = node->parent; //p指向要旋转节点的父亲if (node == *root) { //如果当前旋转节点的是根结点，那么根指向要改变*root = temp;} else if (node == node->parent->left) { //左孩子时node->parent->left = temp; //新的左孩子} else {node->parent->right = temp; //新的右孩子}temp->left = node; //p的左孩子指向node->parent = temp; //父亲改变}//右旋转，与上述左边旋转对称static ngx_inline voidngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,ngx_rbtree_node_t *node){ngx_rbtree_node_t *temp;temp = node->left;node->left = temp->right;if (temp->right != sentinel) {temp->right->parent = node;}temp->parent = node->parent;if (node == *root) {*root = temp;} else if (node == node->parent->right) {node->parent->right = temp;} else {node->parent->left = temp;}temp->right = node;node->parent = temp;}天不负;卧薪尝胆，三千越甲可吞吴。
