红黑树
红黑树常用的操作是插入、删除和查找，并且它对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保，对于红黑树的概念、性质、插入、查找和旋转等这里不再多讲，不了解的请点击 wikipedia rb-tree，这里重点讲一下红黑树的删除，这是红黑树中最难但又必须使用的操作。

红黑树的 5 条性质:

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是 NIL 节点）。
每个红色节点的父子节点都不能为红色。
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
  
可能出现的组合
红黑树的删除之所以难就是因为删除节点遇到的情形太多，容易把人绕晕，那么接下来这篇将一步一步的分析各种情形，只要你静下心来慢慢的分析，将各种情况分清楚，那么写代码就显得比较简单了。

红黑树中删除一个节点，遇到的各种情形就是其子节点的状态和颜色的组合，子节点状态共有 3 种：无子节点、有一个子节点、有两个子节点，颜色有红色和黑色两种，所以共会有 6 种组合。接下来我们逐一分析：   

组合 1：被删节点无子节点，且被删结点为红色
这是最简单的一种情况，直接将节点删除即可，不破坏任何红黑树的性质   

组合 2：被删结点无子结点，且被删结点为黑色
这是最复杂的情况，我们稍后再讨论   

组合 3：被删结点有一个子结点，且被删结点为红色

这是一种不可能的情况，此时不符合性质 5   

组合 4：被删结点有一个子结点，且被删结点为黑色

这种组合下，被删结点 node 的另一个子结点 value 必然为红色，此时直接将 node 删掉，用 value 代替 node 的位置，并将 value 着黑即可。   

组合 5&6：被删结点有两个子结点，且被删结点为黑色或红色
当被删结点 node 有两个子结点时，我们先找到这个被删结点的后继结点 successor（前驱节点也可以），然后用 successor 替换 node 的值，不用改变颜色，此时转换为删除 node 的后继节点 successor。

这里使用 node 的后继节点替换 node，必然是下图两种形态中的一种:

若是(a)的情形，用 successor 代替 node 后，转换为 successor 被删，若 successor 为红色，则变成了组合 1；若 successor 为黑色，则变成了组合2。

若是(b)的情形，用 successor 代替 node 后，转换为 successor 被删，若 successor 为红色，则变成了组合 1（组合 3 是不可能的）；若 successor 为黑色，则变成了组合2或4。
  
  
综上所述：组合 5 6 被转换为前面几种组合，我们真正要进行删除的只有组合 1 2 4，对于组合 1 和 4，删除操作相当简单，这里不再多讲，接下来再逐一分析组合 2 可能的几种情形。         

再论组合 2：被删结点无子结点，且被删结点为黑色
因为删除黑色结点会破坏红黑树的性质 5，所以为了不破坏性质 5，将 node 删除后用一个拥有额外黑色的 null 替代它（可以想象是将 node 删除后，在这个位置放了一个黑色的权值），剩下的就是调平的过程，最终这个游离的黑色权值被扔掉，整个删除操作完成。

然后再结合 node 的父结点 father 和其兄弟结点 brother 来分析。      

情形一：brother 为黑色，且 brother 有一个与其方向一致的红色子结点 son
所谓方向一致，是指 brother 为 father 的左子结点，son 也为 brother 的左子结点；或者 brother 为 father 的右子结点，son 也为 brother 的右子结点。

图(c )中，白色代表随便是黑或是红，方形结点存储的是一个游离的黑色权值。将 brother 和 father 旋转（是左旋还是右旋自己根据情景体会，下同），并重新上色后，变成了图(d)，将游离的黑色权值扔掉，此时不违背任何红黑树的性质，删除操作完成。

图(c )中的情形颠倒过来，也是一样的操作。      

情形二：brother 为黑色，且 brother 有一个与其方向不一致的红色子结点 son

图(e)中，将 son 和 brother 旋转，重新上色后，变成了图(f)，转化为情形一。

图(e)中的情形颠倒过来，也是一样的操作。      

情形三：brother 为黑色，且 brother 无红色子结点
此时若 father 为红，则重新着色即可，删除操作完成。如图下图(g)和(h)

此时若 father 为黑，则重新着色，将游离的黑色权值存到 father（此时 father 的黑色权重为 2），将 father 作为新的结点进行情形判断，遇到情形一、情形二，则进行相应的调整，完成删除操作；如果没有，则结点一直上溯，直到根结点存储额外的黑色，此时将该额外的黑色扔掉，即完成了删除操作。

注意： 这里第二种情况有点不好理解，之所以要加一个游离的黑色是因为删除 node 后造成 node 子树和 brother 子树的黑节点个数不平衡，这里的操作实际是将 brother 子树中黑节点个数减少一个，而将 father 黑色权重设为 2，这样 father 左右两边的子树不用加游离的权值都是平衡的了。接下来将问题转移到了 father、father 的 father、father 的 brother 三个之间，这样向上递归，如果一直是这种情况，最终必定转化为 root 的左子节点或者右子节点权重为 2，同样的将 root 黑色权重设为 2，将另外一边的黑色权重减小 1，再将 root 的黑色权重扔掉一个，此时整棵树重回平衡，只是 root 到叶节点路径的黑节点少了一个。      

情形四：brother 为红色，则 father 必为黑色。

图(i)中，将 brother 和 father 旋转，重新上色后，变成了图(j)，新的 brother（原来的 son）变成了黑色，这样就成了情形一、二、三中的一种。如果将 son 和 brother 旋转，无论怎么重新上色，都会破坏红黑树的性质 4或5，例如图(k)。
图(i)中的情形颠倒过来，也是一样的操作。
  
至此，所有情形都以分析完毕，总的来说，我们要处理的是 3 种组合、7 种情形，其中很多过程都是目标转移的过程，最终转移到可以通过旋转和变色达到平衡的节点或者转移到 root 节点，使红黑树重回平衡。