在了解了红黑树的基本概念之后，接下来我们详细了解一下红黑树的插入操作的几种场景

默认规定

对于红黑树而言，需要默认遵守如下两个规定

• 插入节点一定是红色(为了代码简化,默认黑色节点维持平衡)
• 插入操作都是在叶子节点执行

所有场景

根据前面的规定的插入操作，我们可以将全部的插入场景列举出来，将确定的场景在后面标号为(n)

• 将插入节点self称之为: (s)
• 将父亲节点parent称之为: (p)
• 将祖父节点grandfather称之为: (g)
• 将叔叔节点uncle称之为: (u)

如下：

首先根据父节点颜色区分：

如果插入节点(s)的父节点(p)是黑色的 (1)

• 那么插入节点(s)什么都不做，维持平衡

如果插入节点(s)的父节点(p)是红色的

• 那么平衡破坏，需要进一步调整

然后根据叔叔节点的颜色区分

现在假设所有的插入操作，父节点(p)都是红色的，那么得出其祖父节点(g)一定是黑色的。 这时候叔叔节点(u)的颜色是红色或者黑色。 那么场景如下：

如果插入节点的叔叔节点(u)是红色的 (2)

• 那么将关注节点的父节点(p)，叔叔节点(u)的颜色都设置为黑色
• 然后将关注节点的祖父节点(g)设置为红色.（维持红黑树的颜色）
• 将关注节点转换成祖父节点(g)
• 进一步调整（迭代）

这里进一步调整后，我们可以知道从自身修改为祖父节点(g)之后，情况肯定会发生改变，所以代码需要迭代来确定下一步动作

如果插入节点的叔叔节点(u)是黑色的

• 那么需要进一步调整

再根据插入节点相对于父节点(p)的位置区分

根据上面的统计，目前红黑树的已知现状为：
插入节点本身是红色的，插入节点的父节点(p)是红色的，插入节点的叔叔节点(u)是黑色的，插入节点的祖父节点(g)是黑色的，但是对于插入节点而言，不清楚其位于父节点(p)的左子树还是右子树

如果插入节点属于父节点(p)的右子树(3)

• 那么将关注节点设置为父节点(p)
• 然后将父节点(p)进行左旋。也就是让父节点(p)和父节点(p)的右节点断开，改变其父子关系
• 此时因为关注节点为父节点(p),经过左旋之后，它是原插入节点的左子树，所以进入情况(4)

提前说明的是，这里假定父节点(p)是祖父节点(g)的左子树，所以在此情况下执行左旋

因为其父节点(p)左旋，则其右子树会变为原父节点(p)的父节点。
这里父节点(p)的右节点其实就是之前的关注节点，那么也就是将原关注节点作为原父节点(p)的父节点

因为此时我们的关注节点是父节点(p)，父节点(p)经过左旋之后，自然成为插入节点的左子树。所以我们直接按照情况(4)进行调整，如下介绍情况(4)

如果插入节点属于父节点的左子树(4)

• 那么将关注节点的祖父节点(g)进行右旋
• 调整完成之后，关注节点的父节点(p)和兄弟节点(b)颜色互换

提前说明的是，这里假定父节点(p)是祖父节点(g)的左子树，所以在此情况下执行右旋

这里值得注意的是，将祖父节点(g)进行右旋之后，则祖父节点(g)和父节点(p)会断开，从而形成祖父节点(g)会成为父节点(p)的右子树。然后我们知道祖父节点(g)是黑色，父节点(p)是红色，那么右旋之后，形成的关系按照前序遍历是
父节点(p)--->关注节点(s)--->祖父节点(g)
其颜色状态如下
红(p)--->红(s)--->黑(g)
明显不满足红黑树的规则，所以就需要将父节点(p)的颜色红色和祖父节点(g)的黑色颜色互换，则颜色改变后如下：
黑(p)--->红(s)--->红(g)

最后根据叔叔节点相对于祖父节点的位置区分

根据之前的解析，我们确定的信息如下：

1. 插入节点(s)是红色的
2. 父节点(p)是红色的
3. 叔叔节点(u)是黑色的
4. 祖父节点(g)是黑色的
5. 插入节点(s)位于父节点(p)的左子树情况已解析
6. 插入节点(s)位于父节点(p)的右子树情况已解析

这个时候，我们发现，父节点(p)位于祖父节点(g)的左右情况并没有分析。而上面的情况(3)和(4)都假定了插入节点(s)的父节点(p)位于祖父节点(g)的左子树。而实际上父节点(p)相对于祖父节点(g)的关系既可能是左子树，也可能是右子树。所以出现如下情况：

如果父节点(p)位于祖父节点(g)的左子树

• 按照情况(3)和(4)执行

如果父节点(p)位于祖父节点(g)的左子树

• 对于情况(3)，那么将关注节点设置为父节点(p)后，执行的是右旋
• 对于情况(4)，那么将关注节点设置为祖父节点(g)后，执行的是左旋，然后再染色

简化记忆

根据上面所有场景的介绍，为了方便记忆，本章以容易记忆的方式将场景简单列举出来，简化的场景如下

1. 对黑色节点的插入无需操作
2. 对红色节点的插入，如果叔叔节点(u)都是红色，想办法染色成黑色
   具体染色操作是：将父节点(p)和叔叔节点(u)设置为黑色，并将祖父节点(g)设置为红色。然后将关注节点设置为祖父节点(g)，向上递归，这样就把所有红黑树的叔叔节点(u)染色为黑色了
3. 根据父节点(p)相对于祖父节点(g)，插入节点(s)相对于父节点(p)的位置设置标号
   具体标号操作是：从上往下的视角，如果父节点(p)在祖父节点(g)左边则记作L，右边记作R，插入节点(s)和父节点(p)的关系同理
4. 如果是LL，则对祖父节点(g)右旋
5. 如果是RR，则对祖父节点(g)左旋
6. 如果是LR，则对父节点(p)左旋后，再按照LL操作给祖父节点(g)右旋
7. 如果是RL，则对父节点(p)右旋后，再按照RR操作给祖父节点(g)左旋

进一步简化记忆，可以如下：

• 插入是红色才调整
• 如果叔叔是红色，则先染色
• 如果叔叔是黑色，根据LL/RR/LR/RL来执行操作

总结

至此，我们详细的了解了红黑树关于插入的操作步骤。并进一步的进行了简化记忆，接下来通过实验演示的方式验证所有的场景，下一个文章见