一、红黑树
红黑树也是BST树的一种，它和AVL树不同，它不要求各个节点的高度都是完全一致，是一个近似平衡的树。
红黑树通过黑树节点增加颜色，对每一条根节点到叶子节点上面的各个节点颜色进行约束，确保没有一条路径会比其他路径长出2倍。
红黑树的性质：
- 每个节点的颜色要么是红色，要么是黑色
- 根节点是黑色的
- 每个叶子节点（NIL）是黑色
- 如果一个节点是红色的，则它的两个子节点都是黑色的
- 对于每个节点，其到任意后代的叶子节点的路径上，都包含相同数量的黑色节点
和普通树不同的是，红黑树的叶子节点都是NIL节点，它是一个特殊的节点，颜色是黑色。
定理：一个有n各内部节点的红黑树的高度至多为2lg(n+1)。
下面就是一棵红黑树示例，省去了末尾的NIL叶子节点：
红黑树的操作和BST/AVL树相差不大，搜索、旋转也都是一模一样的代码。红黑树的操作：
RB_INSERT: 插入节点到红黑树RB_DELETE: 从红黑树中删除节点
二、红黑树的添加操作
红黑树每个新插入的节点都是红色，节点添加操作分为以下两步：
- 按照BST的插入节点操作插入一个节点
- 调整节点颜色，以满足红黑树性质
过程中负责的步骤是第二部，也就是插入之后的调整，调整的规则有如下几种。
2.1 节点颜色调整规则
假设待插入节点为z，设其叔叔节点为y。插入节点后，有以下几种情况：
情况一：父节点是红色，叔叔节点也是红色
这种情况下，插入节点z会违反性质4，并且z的叔父节点也是红色，所以为了维持性质，需要修改其父亲节点和叔叔节点的颜色为黑色，修改其祖父节点的颜色为红色。并把z设置为祖父节点，继续判断z的属性，如果修改后z的叔叔节点还是红色，继续当前的操作。直到叔叔节点y是黑色了，情况一就转换成情况二，向下看。
情况二：父节点是红色，叔叔节点是黑色，当前节点是其父节点的右儿子
叔叔节点是黑色，判断当前节点是其父亲的左儿子还是右儿子，如果是左儿子，将满足情况三，按照情况三来处理。如果是右儿子，设置z指向其父节点，并对新的z节点左旋，把情况二转换成情况三。
情况三：父节点是红色，叔叔节点是黑色，当前节点是其父节点的左儿子
这种情况下，为了保持平衡，修改z的父颜色为黑色，z的祖父节点为红色，然后对祖父节点右旋。得到满足条件的红黑树：
情况四：父节点是黑色
如果父节点是黑色，无需调整，插入节点后树依旧是一棵红黑树，性质不会破坏。
2.2 插入节点代码
红黑树的插入代码前部分和BST插入一模一样，最后添加完成之后执行操作FIXUP对红黑树进行调整：
void rb_tree_insert(struct rb_tree_st *tree, struct rb_tree_node_st *node) {
struct rb_tree_node_st *x = tree->root;
struct rb_tree_node_st *y = NULL;
struct rb_tree_node_st *z = node;
while (x != NULL) {
y = x;
if (z->key < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if (y == NULL)
tree->root = z;
else if (y->key > z->key)
y->lchild = z;
else
y->rchild = z;
z->lchild = NULL;
z->rchild = NULL;
node->color = NODE_COLOR_RED;
rb_tree_fixup(tree, node);
}红黑树调整代码：
void rb_tree_fixup(struct rb_tree_st *tree, struct rb_tree_node_st *node) {
struct rb_tree_node_st *z = node;
struct rb_tree_node_st *y = NULL;
while (z->parent && z->parent->color == NODE_COLOR_RED) {
// 如果父节点是红色，那么必定有祖父节点，根据父节点的位置得到叔父节点
if (z->parent == z->parent->parent->lchild)
// 父节点是祖父节点的左子节点
y = z->parent->parent->rchild;
else
y = z->parent->parent->lchild;
if (y && y->color == NODE_COLOR_RED) {
// 叔父节点是红色，把叔父节点和父节点全部置黑，不区分叔父节点是左儿子还是右儿子
y->color = NODE_COLOR_BLACK;
z->parent->color = NODE_COLOR_BLACK;
// 祖父节点置红，然后重新处理祖父节点
z->parent->parent->color = NODE_COLOR_RED;
z = z->parent->parent;
continue;
}
// 此时叔父节点必定是黑色，把y设为祖父节点，需要区分叔父节点是左儿子还是右儿子
y = z->parent->parent;
if (z->parent == y->lchild) {
if (z == z->parent->rchild) {
z = z->parent;
left_rotate(tree, z);
}
z->parent->color = NODE_COLOR_BLACK;
z->parent->parent->color = NODE_COLOR_RED;
right_rotate(tree, z->parent->parent);
} else {
if (z == z->parent->lchild) {
z = z->parent;
right_rotate(tree, z);
}
z->parent->color = NODE_COLOR_BLACK;
z->parent->parent->color = NODE_COLOR_RED;
left_rotate(tree, y);
}
}
// 设置根节点是黑色
tree->root->color = NODE_COLOR_BLACK;
}三、删除节点
和AVL中一样，删除节点总是比增加节点麻烦一些。因为红黑树也是一颗BST树，并且也是一个接近平衡的二叉树，因此它的删除过程也和AVL树一样。先删除节点，然后调整，步骤为：
- 删除或者替换节点，这一步有可能导致红黑树性质不满足
- 调整节点颜色，以满足红黑树性质
在AVL树中，删除节点并不是把这个节点直接删除，而是找到这个节点的后继节点来替代该节点。红黑树中的删除也是按照这种办法，假设删除节点为z，设定y表示替换z位置的节点，x表示实际上被删除的节点（即逻辑上被删除的叶子节点），w是x的兄弟节点。删除节点x点有可能是z的儿子，也有可能是y的儿子，也有可能是NIL。
当删除节点是红色，删除时不会影响红黑树的性质，需要调整的直有删除节点是黑色的场景。
3.1 删除节点调整颜色规则
情况一：删除节点x的兄弟节点w是红色
操作：修改w和父节点的颜色，并对父节点左移。此时x的新兄弟节点是原w节点的左子节点，必定为黑色。情况一可以转换成下面的情况来处理。
情况二：x的兄弟节点w是黑色，且w的两个子节点都是黑色
操作：去掉w上的黑色，并使x为其父节点，继续循环处理新x节点。
情况三：x的兄弟节点w是黑色，w的左孩子是红色，w的右孩子是黑色
操作：修改w和其左儿子的颜色，并对w右旋，然后把w设置为其原来的左儿子。将情况三转换成情况四。
情况四：x的兄弟节点w是黑色，且w的右孩子是红色
第四种情况是我们最终想要转换的情况，因为只有这一种情况能通过旋转来彻底解决平衡。
操作：设置w的颜色为其父节点的颜色，w父节点设置为黑色，w的右儿子设置为黑色，对父节点进行左旋。
上面的描述过于抽象，可以用一个例子来理解。下面是一棵红黑树，想要删除节点60（60原先是黑色）：
删除的步骤：
- 设置80的颜色为其父节点的颜色（红色）
- 设置80的父节点70颜色为黑色，设置80右儿子85的颜色为黑色
- 对70左旋，去掉节点60，得到右边的红黑树，此时红黑树的性质依旧保持
3.2 删除代码实现
删除红黑树节点的伪代码（来自算法导论）：
修复节点伪代码：
此处评论已关闭