【数据结构学习笔记】_红黑树之节点删除(二)
来，继续，听说红黑树删除比插入要复杂，来试试看，机智如你我，怕甚(*^__^*) ……
目录
第一点 你的名字
第二点 为何是你
第三点 你的性质
第四点 开始删除
作为老牌电影，我们恶心一点，首先介绍下约定的出场演员名单：
D：需要删除的节点
M：删除节点D后被选中取代D位置的节点
P：M的爸爸（父节点）
G：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--红下面不能为红
来，说人话上图：
按上面分析的4大类（M的颜色+S的颜色+P的颜色）15种场景（Case15）来具体分析，删除节点后需要做的操作：
Case1 ~~~情形：1、删除D（0012），它的M是红色（0010）
2、M没有左右孩子
~~~策略为：直接将M和D位置、颜色交换，然后删除D-----------操作后都不会引起红黑树的“不平衡”，所以交换后可以直接删除D
Case2~~~情形：1、删除D（0012），它的M是黑色（0010）、S是黑色（0006）、P是红色（0008）
2、M如果有孩子（只能是左红孩子ML）
~~~策略为：将M和D位置、颜色交换，删除D，P变成黑色、S变成红色-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P变成黑色、S变成红色（如果M有孩子，ML颜色不用变化挂在P的右边即可）
Case3~~~情形：删除D（0012），它的M是黑色（0010）、S是黑色（0006）、P是红色（0008）-------S有左儿子（只能是红色的一层哈）
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，P右旋-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case4~~~情形：删除D（0012），它的M是黑色（0010）、S是黑色（0006）、P是红色（0008）-------S有右儿子（只能是红色的一层哈）
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，SR变成S的左孩子，然后和S的位置交换后，P右旋-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case5~~~情形：删除D（0012），它的M是黑色（0010）、S是黑色（0006）、P是红色（0008）-------S有左和右儿子（只能是红色的一层哈）
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，P右旋-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case6~~~情形：删除D（0010），它的M是黑色（0008）、S是黑色（0004）、P是红色（0006）-------S没有儿子
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，G(P的父节点)的右子树上G到每个叶子节点路径上的黑点总数均变少一个-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case7~~~情形：删除D（0010），它的M是黑色（0008）、S是黑色（0004）、P是红色（0006）-------S有左儿子（只能是红色的一层哈）
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，右旋P-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case8~~~情形：删除D（0010），它的M是黑色（0008）、S是黑色（0004）、P是红色（0006）-------S有右儿子（只能是红色的一层哈）
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，SR变成S的左孩子，然后和S的位置交换后，P右旋-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case9~~~情形：删除D（0010），它的M是黑色（0008）、S是黑色（0004）、P是红色（0006）-------S有左和右儿子（只能是红色的一层哈）
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，P右旋-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case10~~~情形：删除D（0024），它的M是黑色（0016）、S是红色（0008）、P是黑色（0010）-------S没有孙子：SLL/SLR/SRL/SRR
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，P右旋-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case11~~~情形：删除D（0024），它的M是黑色（0016）、S是红色（0008）、P是黑色（0010）-------S仅仅有孙子：SLL
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，P右旋-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case12~~~情形：删除D（0024），它的M是黑色（0016）、S是红色（0008）、P是黑色（0010）-------S仅仅有孙子：SLR
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，P右旋-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case13~~~情形：删除D（0024），它的M是黑色（0016）、S是红色（0006）、P是黑色（0010）-------S仅仅有孙子：SRL
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，P右旋之后再右旋一次-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case14~~~情形：删除D（0024），它的M是黑色（0016）、S是红色（0006）、P是黑色（0010）-------S仅仅有孙子：SRR
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，P右旋之后，交换SRR和SR的内容并且从右孩子变成左孩子，P再右旋一次-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
Case15~~~情形：删除D（0024），它的M是黑色（0016）、S是红色（0006）、P是黑色（0010）-------S有孙子：SLL/SLR/SRL/SRR
情形①：M没有孩子
~~~策略为：将M和D位置、颜色交换，删除D，P右旋之后，P再右旋一次-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要P右旋
情形②：M有孩子----只能是左红色
~~~策略为：将M和D位置、颜色交换，删除D，ML直接变黑变成P的右孩子-----------MD交换操作后PR少了个黑点，引起红黑树的“不平衡”，所以要ML变成黑色成为P的右孩子
总结：
1、D的颜色不用管，是红色/黑色直接交换给M即可；
2、M为红色或者M是黑色但是有左孩子-------只需要M替换D的位置即可，ML直接变成PR；
3、其他的情况就需要将P进行右转（如果M的定义是“右子树的最小值”，那么这里就需要的是左转）了，情况复杂时需要转两次（也最多转两次）。