下一篇：红黑树删除篇（可能是你至今遇到最简单的解释方式了）

前言

红黑树的插入过程有多种实现方式，以下内容为个人总结，如果发现文章有错误、对内容有疑问，请直接留言，我会在第一时间回复。

红黑树的五个性质

1.节点是红色或黑色

2.根节点是黑色

3.所有叶子节点都是黑色（叶子节点是NIL节点）

4.如果一个节点是红的，则它的两个儿子节点都是黑的

5.从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。

插入过程分析

说明：

1.每次改变节点颜色或者旋转时，都要保证不影响性质5

2.新插入的节点为红色（也是保证不影响性质5）

Case1：插入节点为根节点时，直接插入后涂黑

Case2：插入节点的父节点为黑色，直接插入即可

Case3：插入节点的父节点为红色，分为两种情况：

            Case3.1：叔父节点为红色

            Case3.2：叔父节点为黑色，分为四种情况

                            Case3.2.1：父节点在左侧，插入节点在左侧（简称：左左）

                            Case3.2.2：父节点在左侧，插入节点在右侧（简称：左右）

                            Case3.2.3：父节点在右侧，插入节点在左侧（简称：右左）

                            Case3.2.4：父节点在右侧，插入节点在右侧（简称：右右）

下面针对上面提到的7种情况进行说明：

Case1:插入节点为根节点时，直接插入后涂黑。（不解释，有疑问留言）

Case2：插入节点的父节点为黑色，直接插入即可

当父节点为黑色时，插入节点为红色，仍满足红黑树的五个性质，故可直接插入。（此处解释比较简单，有疑问留言）

Case3.1：叔父节点为红色（祖父节点一定为黑色，性质4）

处理方法：变色--->父亲节点变黑，祖父节点变红，叔父节点变黑（继续迭代）

问题解决思想：推托式，意思就是你给我加的这个节点我处理不了，往上面报吧。这种情况不能直接解决问题，但是可以推动问题的解决。

Case3.2：叔父节点为黑色，分为四种情况

                            Case3.2.1：父节点在左侧，插入节点在左侧（简称：左左）

                            Case3.2.2：父节点在左侧，插入节点在右侧（简称：左右）

                            Case3.2.3：父节点在右侧，插入节点在左侧（简称：右左）

                            Case3.2.4：父节点在右侧，插入节点在右侧（简称：右右）

Case3.2.2（如图中2）和Case3.2.3（如图中3）可以转化为Case3.2.1（如图中1）和Case3.2.4（如图中4）。

处理方法：

2和3通过插入节点和父节点的左和右旋转变为1和4

1和4通过父节点和祖父节点的右和左旋转，然后原父节点变黑，原祖父节点变红

问题解决思想：

先进行旋转，然后变色，一步到位解决问题，这种方式被我称为内部解决方式。

下一篇：红黑树删除篇（可能是你至今遇到最简单的解释方式了）

禁止抄袭，支持原创！