【数据结构学习笔记】_红黑树之节点删除(二)
来，继续，听说红黑树删除比插入要复杂，来试试看，机智如你我，怕甚(*^__^*) ……
目录
第一点 你的名字
第二点 为何是你
第三点 你的性质
第四点 开始删除
作为老牌电影，我们恶心一点，首先介绍下约定的出场演员名单：
D：需要删除的节点
M：删除节点D后被选中取代D位置的节点
P：M的爸爸（父节点）—————-打酱油的，没什么用
S：M的姐妹节点
L：节点的左子节点
R：节点的右子节点
SL：S节点的左子节点
SRR：S节点的右子节点的右子节点
SRRR：这种不用去管，因为这场电影用不到它也没给它准备盒饭，我穷o(╯□╰)o
M：还记得【数据结构学习笔记】_红黑树之基础知识(一)里面提到的：
“如果要删除的节点有左右孩子，则找左子树的最大值或者右子树的最小值，来替换要删除的节点，然后删除需要删除的节点”吗？
Q1：为什么要这样选呢？
A1：这是个有序的东东，删除一个节点，当然是让它值相邻的两个手牵手了，“左子树的最大值或者右子树的最小值”不就是它值相邻的两个吗
A2：自己想象或者度娘吧
把二叉树想象成真正的一颗树，M就是从最靠近树干两侧的节点里面取的
以左子树的最大值M为例：
1、首先M是没有右子树的（因为M的定义就是“需要删除的节点D的左子树的最大值”，就是从D的左子树往下，节点有右孩子就继续找其右孩子，一直到没有右孩子为止）；
2、如果M是红色；
1）P是黑色的—————————因为如果是红色就违背了红黑树气质第4条
2）M没有左孩子————————因为如果是红色就违背了红黑树气质第4条，如果是黑色就违背了红黑树气质第5条
3）S要么是空节点、要么是红色节点（下面只有NIL节点了哟）————————如果是黑色就违背了红黑树气质第5条
3、如果M是黑色；
A）对于M：
情形1：M没有左孩子
情形2：M有左孩子（肯定是红色），而且下面没有子节点了————————-因为如果是黑色就违背了红黑树气质第5条
B）对于S：
情形1：S如果是红色
1）S下肯有左右两个黑色子节点————————-红下面不能为红
2）S下左右子节点的左右子节点如果存在就必须为红色，而且下面再无子节点，即有SLL、SLR、SRL、SRR，没有类似SLLL————————-红下面不能为红、路径上黑点数目要一致
情形2：S如果是黑色
1）S下如果有左右子节点必为红色————————-路径上黑点数目要一致
2）S下左右子节点没有子节点，即有SL、SR没有类似SLL————————-红下面不能为红
来，说人话上图：