算法学习之数据结构之红黑树（二）
红黑树的删除。 红黑树的删除是在二叉查找树的基础上修改得来的，从红黑树上删除一个节点，可以先用普通二叉搜索树的方法，将节点从红黑树上删除掉，然后再将被破坏的红黑性质进行恢复。 我们回忆一下普通二叉树的节点删除方法：Z指向需要删除的节点，Y指向实质结构上被删除的结点，如果Z节点只有一个子节点或没有子节点，那么Y就是指向Z指向的节点。如果Z节点有两个子节点，那么Y指向Z节点的后继节点（其实前趋也是一样的），而Z的后继节点绝对不可能有左子树。因此，仅从结构来看，二叉树上实质被删除的节点最多只可能有一个子树。伪代码如下：
改变w和parent[x]的颜色，再对parent[x]做一次左旋转，并将w置为x新的兄弟节点，红黑性质得到保持，转到情况2,3,4.
情况2：x的兄弟节点w是黑色的，而且w的两个孩子都是黑色的。
因为w两个孩子都是黑色的，w也是黑色的，所以从x和w上去掉一重黑色，从而x只有一重黑色，w为红色，通过x为parent[x]及诶单来重复while循环，如果是从情况1进入情况2，新节点x的color为red则结束循环。
情况3：x的兄弟节点是黑色的，左孩子是红色的，右孩子是黑色的。
交换w和左孩子的颜色，并对w进行右旋转，从而红黑性质保持一致，这样情况3转为情况4。
情况4：x的兄弟节点w是黑色的，w的右孩子是红色的。
对颜色做修改，并对parent[x]做一次左旋，可以去掉x的额外黑色来把它变成单独黑色，而不破坏红黑性质。将x置为根后，while循环结束。
