红黑树

[此恨绵绵]

  红黑树的删除类似于排序二叉树，排序二叉树主要分为三种情况：删除没有左孩子且没有右孩子的结点即：度为0。删除只有左（右）孩子的结点。即：度为1。删除有左孩子且有右孩子的结点。即：度为2。
  由于红黑树还有颜色的区分，所以在上述三种情况的基础上加上颜色，就是六种情况。以 {15, 7, 45, 3, 10, 25, 55, 1, 5, 75} 为例：

  红黑树有六种情况：第一种：删除度为 0 的黑色结点。比如：10、25。第二种：删除度为 0 的红色结点。比如：1、5、75。第三种：删除度为 1 的黑色结点。比如：55。第四种：删除度为 1 的红色结点。这种情况不存在。第五种：删除度为 2 的黑色结点。比如：3、15。第六种：删除度为 2 的红色结点。比如：7、45。

• 第一种情况删除度为 0 的黑色结点：比较复杂，后面专门讨论。
• 第二种情况时候删除度为 0 的红色结点：直接删除即可。
• 第三种情况时候删除度为 1 的黑色结点：必然是"黑-红"的结构，则，删除当前结点（A），让孩子结点（B）代替A，并将B改为黑色。
• 第四种情况时候删除度为 1 的红色结点：这种情况不存在。到情况五的时候删除度为 2 的黑色结点：比如：删除 15，用其前驱10（后继也可以）的值代替15，再删除10（跳到情况1）即可。
  
  　　比如：删除 15，用其前驱10（后继也可以）的值代替15，再删除10（跳到情况3）即可。
  
  　　比如：删除 15，用其前驱12（后继也可以）的值代替15，再删除12（跳到情况2）即可。