红黑树的插入和删除(真正讲清楚删除)

回顾红黑树5个性质：

红黑树的节点不是黑色的就是红色的
红黑树的根节点一定是黑色的
红黑树的所有叶子节点都是黑色的（注意：红黑树的叶子节点指Null节点）
红黑树任何路径上不允许出现相邻两个红色节点
从红黑树的任一节点开始向下到任意叶子节点所经过的黑色节点数目相同

性质分析：
1.前3条性质很好理解
2.第4条性质是指红色节点不能相连，必须被黑色节点隔开
3.第5条性质如果被打破，比第4条性质更难恢复，情况会更复杂
4.根节点到叶子节点的路径上，红色节点数不会超过黑色节点数，最长路径不会大于最短路径的两倍
5.树上的黑色节点是平衡的

基于性质分析第3条，插入和删除的时候，都优先操作红色节点以便满足性质5，再进行调整以便满足性质4
调整时，若节点没有左/右子节点时，则将其叶子节点(Null节点)考虑进来，当成黑色子节点，简化分类情形
在实际处理时，子节点为空或子节点为黑色，采取相同处理措施，可得到相同的结果

插入思路：
1.确定插入位置
2.创建红色的新节点(i)，插入该位置
3.判断父节点(p)是否为黑色
4.父节点(p)为红色则需再调整(为黑色无需调整)
因父节点是红色，则祖父节点必是黑色
4.1叔叔节点(u)是红色的
将祖父节点(g)的黑色交给其子节点，各条路径上的黑色节点数不变，同时达到分离红色节点的目的，如图一
但祖父节点(g)的父节点(gp)可能也是红色，需要以祖父节点(g)的视角再做处理
图一只考虑了叔叔节点(u)无子节点的情况，所以需要补充考虑叔叔节点(u)有子节点的情况
叔叔节点(u)有子节点的情况，处理方式不变，如图二，如果祖父节点(g)是根节点，则将祖父节点(g)置为黑色
4.2叔叔节点(u)是黑色的
可通过旋转将一个红色转移到叔叔节点(u)所在子树上，各条路径上的黑色节点数不变，如图三

【图一】将g的黑色给两个子节点

【图二】将g的黑色给两个子节点

【图三】右旋分离红色节点

删除思路：
先按欲删除节点(d)的子节点个数分类

1.欲删除节点(d)有两个子节点时不好直接处理，需要转化成只有一个子节点或没有子节点的情形

转化细节可阅读：红黑树删除节点有两个子节点的转化分析

2.欲删除节点(d)只有一个子节点

子节点必然是红色，欲删除节点(d)是黑色
如果子节点是黑色，则欲删除节点(d)左右子树的黑色节点数不一致
此时交换欲删除节点(d)和子节点的值，删除子节点或者交换欲删除节点(d)和子节点的颜色，删除欲删除节点(d)

3.欲删除节点(d)没有子节点

欲删除节点(d)如果是黑色，通过调整将其变成红色，更易于删除

3.1欲删除节点(d)是红色，可直接删除

3.2欲删除节点(d)是黑色

此时需要考虑父节点(p)，兄弟节点(b)，兄弟节点的子节点的状态，分类处理
第一种情况：父节点、兄弟节点、兄弟节点的子节点都是黑色时，向父节点的上层借红色
第二种情况：兄弟节点的子节点有红色时，转移其红色给当前节点
第三种情况：兄弟节点的子节点都是黑色，但父节点是红色时，转移父节点的红色给其子节点
第四种情况：兄弟节点(b)是红色时，通过旋转，转化成第二、三种情况

下面来详细分析这几种情况的处理