彻底理解红黑树( 三 ) _红黑树

处理：

将P和S设置为黑色
将PP设置为红色
把PP设置为当前插入结点

文章插图

图9 插入情景4.1_1

文章插图

图10 插入情景4.1_2
可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；但如果PP的父结点是红色，根据性质4，此时红黑树已不平衡了，所以还需要把PP当作新的插入结点，继续做插入操作自平衡处理，直到平衡为止。
试想下PP刚好为根结点时，那么根据性质2，我们必须把PP重新设为黑色，那么树的红黑结构变为：黑黑红。换句话说，从根结点到叶子结点的路径中，黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。
我们还可以总结出另外一个经验：红黑树的生长是自底向上的。这点不同于普通的二叉查找树，普通的二叉查找树的生长是自顶向下的。
插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点
单纯从插入前来看，也即不算情景4.1自底向上处理时的情况，叔叔结点非红即为叶子结点(Nil) 。因为如果叔叔结点为黑结点，而父结点为红结点，那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了，这不满足红黑树的性质5 。后续情景同样如此，不再多做说明了。
前文说了，需要旋转操作时，肯定一边子树的结点多了或少了，需要租或借给另一边。插入显然是多的情况，那么把多的结点租给另一边子树就可以了。
插入情景4.2.1：插入结点是其父结点的左子结点
处理：

将P设为黑色
将PP设为红色
对PP进行右旋

文章插图

图11 插入情景4.2.1
由图11可得，左边两个红结点，右边不存在，那么一边一个刚刚好，并且因为为红色，肯定不会破坏树的平衡。
咦，可以把PP设为红色，I和P设为黑色吗？答案是可以！看过《算法：第4版》的同学可能知道，书中讲解的就是把PP设为红色，I和P设为黑色。但把PP设为红色，显然又会出现情景4.1的情况，需要自底向上处理，做多了无谓的操作，既然能自己消化就不要麻烦祖辈们啦～
插入情景4.2.2：插入结点是其父结点的右子结点
这种情景显然可以转换为情景4.2.1，如图12所示，不做过多说明了。
处理：

对P进行左旋
把P设置为插入结点，得到情景4.2.1
进行情景4.2.1的处理

文章插图

图12 插入情景4.2.2
插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点
该情景对应情景4.2，只是方向反转，不做过多说明了，直接看图。
插入情景4.3.1：插入结点是其父结点的右子结点
处理：

将P设为黑色
将PP设为红色
对PP进行左旋

文章插图

图13 插入情景4.3.1
插入情景4.3.2：插入结点是其父结点的右子结点
处理：

对P进行右旋
把P设置为插入结点，得到情景4.3.1
进行情景4.3.1的处理

文章插图

图14 插入情景4.3.2
好了，讲完插入的所有情景了。可能又同学会想：上面的情景举例的都是第一次插入而不包含自底向上处理的情况，那么上面所说的情景都适合自底向上的情况吗？答案是肯定的。理由很简单，但每棵子树都能自平衡，那么整棵树最终总是平衡的。好吧，在出个习题，请大家拿出笔和纸画下试试（请务必动手画下，加深印象）：
习题1：请画出图15的插入自平衡处理过程。（答案见文末）

文章插图

图15 习题1
四、红黑树删除
红黑树插入已经够复杂了，但删除更复杂，也是红黑树最复杂的操作了。但稳住，胜利的曙光就在前面了！
红黑树的删除操作也包括两部分工作：一查找目标结点；而删除后自平衡。查找目标结点显然可以复用查找操作，当不存在目标结点时，忽略本次操作；当存在目标结点时，删除后就得做自平衡处理了。删除了结点后我们还需要找结点来替代删除结点的位置，不然子树跟父辈结点断开了，除非删除结点刚好没子结点，那么就不需要替代。