4.2、P 为红色且 U 不存在或为黑色
4.2.1、P 是左节点，C 左节点 （P 为红色且 U 不存在或为黑色）（如图4.2.1）
（1）将 P 设为黑色
（2）将 PP 设为红色
（3）对 PP 进行右旋
4.2.2、P 是左节点，C 右节点 （P 为红色且 U 不存在或为黑色）（如图4.2.2）
（1）对 P 进行左旋
（2）设 PP 为当前节点
（3）此时结构变为 4.2.1 结构，继续进行 4.2.1 操作
4.2.3、P 是右节点，C 右节点 （P 为红色且 U 不存在或为黑色）（如图4.2.3）
（1）将 P 设为黑色
（2）将 PP 设为红色
（3）对 PP 进行左旋
4.2.4、P 是右节点，C 左节点 （P 为红色且 U 不存在或为黑色）（如图4.2.4）
（1）对 P 进行右旋
（2）设 PP 为当前节点
（3）此时结构变为 4.2.3 结构，继续进行 4.2.3 操作
节点插入总结：
当前节点（新插入的节点）会在旋转变色之前就设置为红色；为什么插入节点为红色？因为根据红黑树的特性，当父节点为黑色时，不需要做自平衡操作，如果为黑色，那么插入后褐色层次增加了，破坏特性5。
在4.1情况中(P为红色且U为红色)如果重复递归判断到根节点，把根节点设置成了红色，则根据特性1，必须把根节点变回黑色，此时红黑树的黑色节点层次就增加了一层（自底向上生长）。
四、节点的删除
红黑树的节点插入比较复杂，删除操作更加复杂，但掌握了规律理解起来就简单多了；
说到节点删除之前，需要先了解一下前继节点和后继节点的概念，笔者学习过程中看到一个非常容易理解的描述，如下图：
把所有的节点投射到X轴上，这时所有的节点都是自左至右排好的，这样某个节点的左边的节点就是它的前继节点，右边的节点就是它的后继节点。
由上图可以看到，后继节点是右子树的最左节点，前继节点是左子树的最右节点。
如150节点的前继节点就是130，后继节点就是160。
节点删除后空出的位置需要找到其后继节点或前继节点进行补位，如果被删除的节点没有子节点还好，要是有子节点，不补位的话树就散了；并且补位之后有可能会破坏红黑树的平衡结构，这时就需要进行自平衡了。
所以节点的删除过程可以理解为寻找后继节点或前继节点（一般习惯用后继几点）进行补位后进行自平衡的过程；这样理解，节点删除问题就可以转换为补位节点（后继节点）的问题，补位完成后节点的颜色变为被删除的颜色。
而这一结果再简单就可以理解为：补位节点（后继节点）的删除的自平衡问题，后继节点总是在树的最底层。
这样一来就可以区分补位节点的几种情况：