文档介绍：一篇不错的红黑树代码
一篇不错的红黑树代码总想有一个简单的 RBTree 类， 又不想自己实现，找来找去找到这篇好文，除了讲解的清楚 简明外，代码也不错，无递归的迭代，而且很容易“拿来” 做成模板，如果你也不想"再发明一次轮子"的话...转化 成 Case 3。
Case 3. uncle 是黑色，并且 z 是 z->parent 的左子节点。到 了这一步，我们就剩最后一步了。只要把 z->parent 设成 黑色，把 grandfather 设成红色，再做一次 Right-Rotate(grandfather) ，整棵树就修补完毕了。可以思考一 下，这样一次操作之后， 确实满足了所有红黑树的性质。 Case 2 和 Case 3 如下图：反复进行迭代，直到某一次迭代开 始时 z->parent 为黑色而告终，也就是当遇到 Case 3 后， 做完它而告终。
二、删除
让我们来回顾一下二叉搜索树的删除节点 z 的过程：如果 z 没有子节点，那么直接删除即可；如果 z 只有一个子节点， 那么让这个子节点来代替 z 的 位置，然 后把 z 删除即可； 如果 z 有两个子节点，那么找到 z 在中序遍历中的后继节点 s (也就是从z->rchild开始向左下方一直走到底的那一个 节点)，把s的key赋值给z的key,然后删除s。
红黑树中删除一个节点 z 的方法也是首先按部就班以上的过
程。 如果删除的节点是黑色的，那么显然它所在的路径上 就少一个黑色节点，那么红黑树的性质就被破坏了。这时我 们就要执行一个称为 Delete-Fixup 的过程，来修补这棵树。 下面我就来讲解一下。
一个节点被删除之后，一定有一个它的子节点代替了它的位 置（即使是叶节点被删除后，也会有一个空节点来代替它的 位置。前面说过，在红黑树中，空节点是一个实际存在的节 点。）。我们就设指针 x 指向这个代替位置的节点。
显然，如果 x 是红色的，那么我们只要把它设成黑色，它所 在的路径上就重新多出了一个黑色节点，那么红黑树的性质 就满足了。
然而，如果 x 是黑色的，那我们就要假想 x 上背负了 2 个单 位的黑色。那么红黑树的性质也同样不破坏，但是我们要找 到某一个红色的节点，把 x 上“超载”的这 1 个单位的黑色 丢给它，这样才算完成。Delete-Fixup做的就是这个工作。
Delete-Fixup 同样是一个循环迭代的过程。每一次迭代开始 时，如果指针 x 指向一个红色节点，那么大功告成，把它设 成黑色即告终。相反如果 x 黑色，那么我们就会面对以下 4
种情况。
这里引入另一个指针W,指向x的兄弟。这里我们都默认x 是 x->parent 的左子节点，则 w 是 x->parent 的右子节 点。（如果实际遇到相反的情况,只要把所有操作中的左、 右互反一下就可以了。）
Case 1. W 是红色。这时我们根据红黑树的性质可以肯定
x->parent 是黑色、w->lchild 是黑色。我们把 x->parent 与w的颜色互换，然后做一次Left-Rotate（x->parent）。做 完之后x就有了一个新的兄弟：原w->lchild,前面说过它 一定是 黑色的。那么我们就在不破坏红黑树性质的前提下, 把Case 1转换成了 Case2、3、4中的一个，也就是w是黑色 的情况。如下图：Case 2. w是黑色，并且w的两个子节点都 是黑色。这时我们只要把w设成红色。然后把x移到
x->parent,开始下一轮迭代（注意，那“超载”的1单位 的黑色始终是跟着指针x走的，直到x走到了一个红色节 点上才能把它“卸下”）。思考一下,这一次操作不会破坏红 黑树的性质。这如下图（图中节点 B 不一定是红 色，也可 能是黑色）： Case 3. w 是黑色，并且 w 的右子节点也是黑色。 这时我们把 w 与 w->lchild 的颜色互换，然后做 Right-Rotate（w）。思考一下，这样做之后 不会破坏红黑树的 性质。这时x的新的兄弟就是原w->lchild。而Case 3被 转化成了
Case 4。 Case 4. w 是黑色，并且 w 的右子节点是红 色。一但遇到 Case 4，就胜利在望了。我看下面一张图。先 把w与x->parent的颜色互换，再做
Left-Rotate（x->parent）。这时图中节 点E （也就是原 w->rchild）所在的路径就肯定少了一个黑色，而x所在的 路径则多了一个黑色。那么我们就把x上多余的1个单位的 黑色丢给 E 就 可以了。至此， Delete-Fixup 就顺利完成了。