红黑树插入的四种情况分析

1 红黑树的性质

（1）每个节点或是红色，或是黑色

（2）根节点是黑色

（3）每个叶节点是黑色

（4）如果一个节点是红色的。则它的连个子节点是黑色的

（5）对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

2 红黑树的三种情况与处理方式

定义z节点：红黑树处理旋转的时候需要防止出现两个连续的红色节点。两个连续的红色节点其中有个节点为父节点，子节点这里定义为z节点。

（1）情况1：z的叔节点是红色的。

（2）情况2：z的叔节点是黑色的，且z是一个右孩子节点

（3）情况3：z的叔节点是黑色的，且z是一个左节点

3 红黑树插入举例

插入数据为11，2，14，1，7，5，8，4，15。步骤如下

图3-1：防止违反规则2，数字2和4插入的时候，直接将2和4变为黑色。并未使用情况2的规则

图3-2：数字5和7插入的时候，可应用规则1

图3-3：插入数字8，未违反红黑树的性质

图3-4：插入数字4的时候，可应用规则2来符合红黑树的性质。但是出现了，数字2和7两个红色连续节点。

图3-5：数字2和7是两个连续的红色的节点，属于情况2 ，情况2 需要进行旋转和变色来满足红黑树的性质

4 红黑树的插入情况的合理性

如果从0构建一个红黑树，需要对红黑树的全部情况进行分析。需要考虑清楚所有的情况。

4.1 研究对象分析

如果红黑树存在两个连续的红色节点，那么情况无外乎如下图所示

图4.1-1：C和D节点如果相遇，那么周边的节点情况如上图所示

图4.1-1解释：

图中有两个A,B,D,E等节点，代表了以 C节点为父节点的情况下，C节点的相关节点的所有可能情况（备注：C节点不为根节点）。

去掉对称情况（对称情况下红黑树的插入时候的转换策略是一致的），剩下两两种情况：

图４．１－２

图４．１－３

上述的两种情况中去掉不需要研究的节点：

（1）A节点和H节点：只需要保持B为根节点的下面的树黑高不变即可忽略掉A和H节点的分析

（2）I节点：I节点可能为红色和黑色，如果I节点为红色，只需要B节点涂成红色，I和C节点涂成黑色即可

（3）如果I节点为黑色或者不存在（I不存在，G也就不存在）

图４.１－３可转换成图４.１－２

图４．１．４：旋转不破坏红黑树的性质

那么图图４.１－２如何保持红黑树的性质呢

５结论

红黑树插入可概括成四种情况

（1）情况1：z的叔节点是红色的。

（2）情况2：z的叔节点是黑色的，且z是一个右孩子节点

（3）情况3：z的叔节点是黑色的，且z是一个左节点

补充４：情况１变换后，根节点为红色节点。直接将根节点变成黑色节点

学习红黑树有一段时间，一直想从自己从０到１论证红黑树插入过程情况变换的完备性。感觉将明白还是很困难的。