红黑树是一种二叉搜索树，它最长路径不超过最短路径的2倍，没有AVL树那么平衡。
红黑树的约束：
1 节点是红色或者黑色
2 根节点是黑色
3 叶子节点（NIL节点）是黑色
4 红色节点的子结点是黑色
5 根节点到任意叶子节点，黑色节点的数量相同
上述约束，隐含的约束是：
1 红色节点的父节点是黑色节点（否则违反4）
2 红色节点要么没有子节点，要么有两个子节点，不可能只有一个黑色子结点。
（一个黑色子结点，那么左右两边的黑色节点个数不同，违反5）
3 黑色节点，如果只有一个儿子，那儿子一定是红色（否则左右两边黑色节点个数不同，违反5）
4 最长路径不超过最短路径的2倍
（任意两个路径黑色节点个数相同，那差距就是红色，而红色的儿子不能是黑色，所以红色的个数不大于黑色，
因此（B+R1）和（B+R2），R1和R2都不大于B，所以差距不可能大于2倍）
插入
待插入的节点，先着红色，然后按照二插树插入到树中，插入后可能违反约束，那么需要进行重新着色或旋转，来维持约束。
新插入节点的关系节点主要有：兄弟节点，父节点，叔叔节点，祖父节点，如下图：
情况如下：
1 如果插入的是根节点，那么将颜色改成黑色，插入完成。
2 如果父节点是黑色的，那么新插入的节点，不违背约束，插入完成。
3 如果父节点是红色，新插入的节点也是红色，违反了约束4。需要进行Recoloring和Rotation，根据情况做不同操作，如下：
由于父亲是红色，那么祖父肯定是黑色kk。
处理情况跟叔叔的颜色关系很大。
3.1 如果叔叔的颜色也是红色
那么只要将叔叔和父亲的颜色改成黑色，对于祖父以下的树，就完全满足约束了。
但是改成黑色，会导致叔叔和父亲两条路径的黑色节点个数加1，那么此时根据祖父的位置，又有两种情况：
3.1.1 祖父是根目录
那么此时，插入完成了，因为根目录的所有路径，都走父亲或者叔叔，因此虽然黑色节点数加1了，但是所有路径都加1，所以仍然相等。
3.1.2 祖父不是根目录
由于父亲和叔叔是红色，所以祖父肯定是黑色。那么只要将祖父的颜色改成红色，那么黑色节点数又减1了，因此走祖父的路径，黑色节点数仍然不变。
3.1.2.1 如果祖父的父亲是黑色，那么插入完成。
3.1.2.2 如果祖父的父亲是红色，那么违反了约束4，此时对祖父重新做上述3处理，以此类推。
3.2 如果叔叔的颜色是黑色，那么需要旋转来保持平衡，总共有4种情况。
3.2.1 Left Left Case
新插入节点是父亲的左儿子，父亲是祖父的左儿子。旋转方法如下：
往右旋转一下，父亲坐祖父的位置，祖父变成父亲的儿子，同时颜色也互换。这样路径上黑色节点的个数不变，又不再违反约束4。
此时插入完成了。
另外注意，刚插入的节点不存在这种情况，因为上述图中去掉x，不是一个合法的红黑树，这种情况出现在3.1.2.2情况中，向上继续处理。
3.2.2 Left Right case
3.2.3 Right Right Case
3.2.4 Right Left Case
注意上图，最后结果是错误的，T1/T2是挂在u下面，T4/T5是挂在P下面。
上述4种情况，处理完后，就是一个合法的红黑树了，因此插入完成。
还有一种从上往下的插入方法，这种方法的好处是，不用先插到底部，再向上修复，速度更快。
插入代码，下面结果经过严格的对比测试，请放心使用：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 | struct rb_node { // kernel's rbtree impl put color in parent, using last 2 bits. // that save memory, but with a little performance downgrade. int color; struct rb_node *parent; struct rb_node *left; struct rb_node *right;};struct rb_tree { struct rb_node *root; int (* cmp)(struct rb_node *, struct rb_node *);};static void inline rotate(struct rb_tree *tree, struct rb_node *x){ struct rb_node *p = x->parent; struct rb_node *g = p->parent; struct rb_node *head = g->parent; struct rb_node **link; if (g == tree->root) link = &tree->root; else if (g == g->parent->left) link = &g->parent->left; else link = &g->parent->right; if (p == g->left) { // Left left case if (x == p->left) { p->color = RB_BLACK; g->color = RB_RED; // note, node's parent is also need changed. g->left = p->right; if (p->right) p->right->parent = g; p->right = g; g->parent = p; *link = p; p->parent = head; } // Left right case else { x->color = RB_BLACK; g->color = RB_RED; p->right = x->left; if (x->left) x->left->parent = p; g->left = x->right; if (x->right) x->right->parent = g; x->left = p; x->right = g; p->parent = g->parent = x; *link = x; x->parent = head; } } else { // Right left case if (x == p->left) { x->color = RB_BLACK; g->color = RB_RED; p->left = x->right; if (x->right) x->right->parent = p; g->right = x->left; if (x->left) x->left->parent = g; x->left = g; x->right = p; p->parent = g->parent = x; *link = x; x->parent = head; } // Right right case else { p->color = RB_BLACK; g->color = RB_RED; g->right = p->left; if (p->left) p->left->parent = g; p->left = g; g->parent = p; *link = p; p->parent = head; } }}int rb_insert(struct rb_tree *tree, struct rb_node *node){ struct rb_node **tmp = &tree->root; struct rb_node *parent = NULL; int ret; // make the colour of newly inserted nodes as RED node->color = RB_RED; node->left = NULL; node->right = NULL; // Perform standard BST insertion while (*tmp) { parent = *tmp; ret = tree->cmp(parent, node); if (ret < 0) tmp = &parent->left; else if (ret > 0) tmp = &parent->right; else return 0; } *tmp = node; node->parent = parent; // Condition 1, If x is the root, change the colour of x as BLACK if (tree->root == node) { node->color = RB_BLACK; return 1; } // Condition 2, If parent is BLACK, insert done // Condition 3, parent is red while (parent->color == RB_RED) { struct rb_node *uncle, *grandpa; grandpa = parent->parent; uncle = (parent == grandpa->left) ? grandpa->right : grandpa->left; // 3.1 uncle is red if (uncle && uncle->color == RB_RED) { // change parent and uncle to BLACK parent->color = RB_BLACK; uncle->color = RB_BLACK; // 3.1.1 grandpa is root, insert done if (grandpa == tree->root) break; // 3.1.2 grandpa is not root, change its color to RED grandpa->color = RB_RED; // set x to grandpa, and continue to check node = grandpa; parent = node->parent; continue; } // 3.2 uncle is BLACK, we need recoloring and rotating rotate(tree, node); // after recoloring and rotating, the tree is balanced break; } return 1;} |
删除在下一节讲
参考：
https://www.geeksforgeeks.org/insertion-in-red-black-tree/
https://www.geeksforgeeks.org/red-black-trees-top-down-insertion/
https://baike.baidu.com/item/红黑树/2413209