一般的，红黑树同时满足以下五大特性：

1. 所有节点的颜色是红色或者黑色；
2. 根节点是黑色；
3. 所有的叶子节点是黑色（叶子节点包含NULL）；
4. 每个红色的节点都有两个黑色的子节点；
5. 从任意节点出发，到其所有叶子节点的简单路径上都包含相同数目的黑色节点.

[cpp] view plaincopyprint?

 

1. #define COLOR_RED 0  
2. #define COLOR_BLACK 1  
3.   
4. typedef int keyType;  
5.   
6. // 定义而二叉树节点数据结构  
7. struct BinaryTreeNode {  
8.     keyType key;      
9.     int color;  
10.     BinaryTreeNode* parent; // 保存父节点  
11.     BinaryTreeNode* left; // left child  
12.     BinaryTreeNode* right; // right child  
13. };  
14.   
15. // define red-black tree node  
16. typedef BinaryTreeNode rbnode;  
17.   
18. // define red-black tree  
19. typedef BinaryTreeNode rbtree;  

情形1 、空树

当树为空的时候，直接将N节点设为黑色作为树的根节点返回。

情形2 、P为黑色节点

图中所示为N插入到P左孩子节点中，这个过程完全满足性质 1 - 5 的要求，并没有破坏 RBT 的规则，因此，此时即可停止检查，插入过程结束。

同理，若P为黑色节点，N插入后作为P的右孩子节点也不会破坏 RBT的规则。

（下面开始讨论 P 为红色 的情形，由 性质2 推导出 G 一定存在，根据性质 4，G一定是黑色）

情形3 、P为红色节点，U存在且为红色节点

情形4 、P为红色节点，U不存在或者U为黑色

	（a） 若P在G的左侧，插入点N也在P的左侧 ------ LL 型 假设G的右侧有 路径有 x个黑色节点，则c有x个黑色节点，G为root的子树路径有x+1个黑色节点。 此时， 只需要以P为中心右旋，将P变为黑色，G变为红色，G的左子树替换为c，这样就可以继续保证以P为root的子树有x+1个黑色节点，检查停止。
	（b）若P在G的左侧，N在P的右侧  -----LR型 这时候先将节点P和节点N做调整，进行左旋，变化成（a）的形态，然后做一次右旋。到此，调整完毕。
图略	（c）若P在G的右侧，N在P的右侧 ----------RR型 情形和（a）正好相反，做一次左旋即可。
图略	（d）若P在G的右侧，N在P的左侧 ----------RL型 情形和（b）正好相反，先做做一次右旋，后进行一次左旋即可。

[cpp] view plaincopyprint?

 

1. // 向右旋转  
2. void rb_right_rotate(rbnode* g) {  
3.     rbnode * p = g->left;  
4.     keyType k = g->key;  
5.     g->key = p->key;  
6.     p->key = k;  
7.     g->left = p->left;  
8.     if (NULL != p->left) {  
9.         p->left->parent = g;  
10.     }  
11.     p->left = p->right;  
12.     p->right = g->right;  
13.     if (NULL != g->right) {  
14.         g->right->parent = p;  
15.     }  
16.     g->right = p;  
17. }  
18.   
19. // 向左旋转  
20. void rb_left_rotate(rbnode* g) {  
21.     rbnode* p = g->right;  
22.     keyType k = g->key;  
23.     g->key = p->key;  
24.     p->key = k;  
25.     g->right = p->right;  
26.     if (NULL != p->right) {  
27.         p->right->parent = g;  
28.     }  
29.     p->right = p->left;  
30.     p->left = g->left;  
31.     if (NULL != g->left) {  
32.         g->left->parent = p;  
33.     }  
34.     g->left = p;  
35. }  
36.   
37. // check and adjust after insertion  
38. void rbt_insert_check(rbnode* node) {  
39.     // CASE 1 :  if the node equals the root  
40.     // set the color of the node black and return.  
41.     if (NULL == node->parent) {  
42.         node->color = COLOR_BLACK;  
43.         return;  
44.     }  
45.     // CASE 2 : when the parent of the node is black  
46.     // All features have been met, stop check and return  
47.     if (node->parent->color == COLOR_BLACK) {  
48.         return;  
49.     }  
50.   
51.     // Otherwise, the the parent node is RED, and this means the grandfather node exists.  
52.     rbnode* gf = node->parent->parent;  
53.     rbnode* uf = (gf->left == node->parent) ? gf->right : gf->left;  
54.   
55.     // CASE 3 : When the uncle node exists and it‘s RED  
56.     if (NULL != uf && uf->color == COLOR_RED) {  
57.         // set parent and uncle black, set grandfather red  
58.         node->parent->color = COLOR_BLACK;  
59.         uf->color = COLOR_BLACK;  
60.         gf->color = COLOR_RED;  
61.         // then re check the tree at grandfather node from CASE 1.  
62.         rbt_insert_check(gf);  
63.         return;  
64.     }  
65.   
66.     // CASE 4 : when the uncle is NULL or its color is Black.  
67.     if (node->parent == gf->left) { // the node in the left of its grandfather  
68.         // (a) LL model  
69.         if (node == node->parent->left) { // the node in the left of its parent  
70.             rb_right_rotate(gf);  
71.         }  
72.         // (b) LR model  
73.         else if (node == node->parent->right) { //the node in the right of its parent.  
74.             rb_left_rotate(node->parent);  
75.             rb_right_rotate(gf);  
76.         }  
77.     } else if (node->parent == gf->right) { //the node in the right of its grandfather  
78.         // (c) RR model  
79.         if (node == node->parent->right) { //the node in the right of its parent.  
80.             rb_left_rotate(gf);  
81.         }  
82.         // (d) RL model  
83.         else if (node == node->parent->left) { //the node in the left of its parent.  
84.             rb_right_rotate(node->parent);  
85.             rb_left_rotate(gf);  
86.         }  
87.     }  
88. }  
89.   
90. // 插入新的关键字  
91. int rbt_insert(rbtree* &tree, keyType key) {  
92.     if (NULL == tree) { // if the tree is NULL  
93.         tree = (rbtree*) malloc((sizeof(rbnode)));  
94.         tree->key = key;  
95.         tree->color = COLOR_BLACK;  
96.         tree->parent = tree->left = tree->right = NULL;  
97.         return 1;  
98.     }  
99.     // find insert point  
100.     rbnode *n = tree, *p = tree->parent;  
101.     while (NULL != n) {  
102.         if (key == n->key) {  
103.             return 0;  
104.         }  
105.         p = n;  
106.         n = (key > p->key) ? p->right : p->left;  
107.     }  
108.     // insert the node  
109.     n = (rbtree*) malloc((sizeof(rbnode)));  
110.     n->key = key;  
111.     n->color = COLOR_RED;  
112.     n->parent = p;  
113.     n->right = n->left = NULL;  
114.     ((key > p->key) ? p->right : p->left) = n;  
115.   
116.     // adjust the tree  
117.     rbt_insert_check(n);  
118.   
119.     return 1;  
120. }  

4.删除Key

情形1 、N节点为红色

当N节点为红色的时候，由于左侧缺少一个黑色的节点，可以将N节点的颜色修改为黑色，这样即可从新满足性质5. 调整完毕。

情形2、S节点为红色

当S节点为红色节点时，则可以将P节点向左旋转，旋转之后P为红色，S为黑色，这个时候S-Sl这条简单路径黑色节点数目合法，S-P-Sl节点数目也合法，S-P-N路径黑色节点数目少一个。 相当于，P的左侧删除了一个黑色节点，应当重新调整 P，S，Sl，Sr所指向的节点，进行后续操作。 后续可能的情形为：3，5，6

情形3、P节点为红色，S，Sl，Sr为黑色

当P为红色，S为黑色，Sl和Sr均为黑色的时候，则可以简单的交换P节点和S节点的颜色，这样即可使各条简单路径的黑色节点数目和删除节点前相等。 调整完毕。

情形4、P，S，Sl，Sr均为黑色

当P、S、Sl、Sr均为黑色节点的时候，只需要简单的将S节点标记为红色，这样以P节点为根的个简单路径黑色节点数目比删除之前少一个。 因此，P相当与N的位置，从P的父节点开始递归进行调整。 （如果此时P为树的根节点，即可停止调整）

情形5、Sl为红色节点并且Sr为黑色

这种情况下，可以将Sl进行右旋操作，右旋之后，Sl为黑色，S为红色，Sr不变，这样保持P节点右子树中各简单路径黑色节点数目和旋转前一样。 这个时候，原来的S相当于Sl的位置，Sl相当与a，Sr相当与S。 更新S，Sl，Sr新指向的位置，进行下一步操作。 后续情形为：6.

情形6、Sr为红色

这时，将P节点做一次左旋操作，将Sr的颜色设置为黑色，P和S交换颜色，调整之后，各简单路径的黑色节点数目和删除节点之前一样。 此时调整结束。

[cpp] view plaincopyprint?

 

1. int is_black(rbnode * node) {  
2.     if (node == NULL) return 1;  
3.     if (node->color == COLOR_BLACK) return 1;  
4.     return 0;  
5. }  
6.   
7. // check and adjust after deletion  
8. void rbt_delete_check(rbnode* p, bool delLeft) {  
9.     rbnode * n = delLeft ? p->left : p->right;  
10.     // case 1: n is red  
11.     if (NULL != n && n->color == COLOR_RED) {  
12.         n->color = COLOR_BLACK;  
13.         return;  
14.     }  
15.     // else the other subtree of p at least has one more node.  
16.     rbnode * s = delLeft ? p->right : p->left;  
17.     rbnode * sl = s->left;  
18.     rbnode * sr = s->right;  
19.   
20.     // case 2 : S is red , p left rotate  
21.     if (s->color == COLOR_RED) {  
22.         if (delLeft) {  
23.             rb_left_rotate(p);  
24.         } else {  
25.             rb_right_rotate(p);  
26.         }  
27.         p = s;  
28.         s = delLeft ? sl : sr;  
29.         sl = s->left;  
30.         sr = s->right;  
31.     }  
32.     // Other cases : S is black  
33.     // when SL and SR  are black  
34.     if (is_black(sl) && is_black(sr)) {  
35.         // case 3 : P is red,  S SL and SR are black  
36.         if (!is_black(p)) {  
37.             p->color = COLOR_BLACK;  
38.             s->color = COLOR_RED;  
39.         }  
40.         // case 4: P ,S, SL and SR are black  
41.         else {  
42.             s->color = COLOR_RED;  
43.             if (NULL == p->parent) {  
44.                 return;  
45.             }  
46.             delLeft = (p == p->parent->left);  
47.             rbt_delete_check(p->parent, delLeft);  
48.         }  
49.         return;  
50.     }  
51.     // when SL and SR has red node  
52.     if (delLeft) {  
53.         if (is_black(sr)) {    // case 5(a) : delLeft is true and SR is black  
54.             rb_right_rotate(s);  
55.             sr = s->right;  
56.         }  
57.         rb_left_rotate(p);    // case 6(a) : rotate the p node  
58.         sr->color = COLOR_BLACK;  
59.     } else {  
60.         if (is_black(sl)) {    // case 5(b) : delLeft is false and SL is black  
61.             rb_left_rotate(s);  
62.             sl = s->left;  
63.         }  
64.         rb_right_rotate(p);    // case 6(b) : rotate the p node  
65.         sl->color = COLOR_BLACK;  
66.     }  
67. }  
68.   
69. // delete a key from the RBT  
70. int rbt_delete(rbtree* &tree, keyType key) {  
71.     if (NULL == tree) {  
72.         return 0;  
73.     }  
74.     // find the node  
75.     rbnode *curr, *temp;  
76.     for (curr = tree;;) {  
77.         if (key == curr->key) {  
78.             break;  
79.         }  
80.         curr = (key > curr->key) ? curr->right : curr->left;  
81.         if (NULL == curr) {  
82.             return 0;  
83.         }  
84.     }  
85.     // if the node to delete has two children  
86.     if (NULL != curr->left && NULL != curr->right) {  
87.         for (temp = curr->left; NULL != temp->right; temp = temp->right) {  
88.         }  
89.         curr->key = temp->key;  
90.         curr = temp;  
91.     }  
92.     if (NULL == curr->parent) { // it is the tree root  
93.         tree = (NULL == curr->left) ? curr->right : curr->left;  
94.         if (tree != NULL) {  
95.             tree->color = COLOR_BLACK;  
96.             tree->parent = NULL;  
97.         }  
98.         free(curr);  
99.         return 1;  
100.     }  
101.     // delete the node  
102.     rbnode* fa = curr->parent;  
103.     temp = (NULL == curr->left) ? curr->right : curr->left;  
104.     bool delLeft = (fa->left == curr);  
105.     if (NULL != temp) {  
106.         temp->parent = fa;  
107.     }  
108.     delLeft ? fa->left = temp : fa->right = temp;  
109.     if (curr->color != COLOR_RED) { // adjust after deletion  
110.         rbt_delete_check(fa, delLeft);  
111.     }  
112.     free(curr);  
113.     return 1;  
114. }