下一篇：红黑树删除篇（可能是你至今遇到最简单的解释方式了）
前言
红黑树的插入过程有多种实现方式，以下内容为个人总结，如果发现文章有错误、对内容有疑问，请直接留言，我会在第一时间回复。
红黑树的五个性质
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通过父节点和祖父节点的右和左旋转，然后原父节点变黑，原祖父节点变红
问题解决思想：
先进行旋转，然后变色，一步到位解决问题，这种方式被我称为内部解决方式。
下一篇：红黑树删除篇（可能是你至今遇到最简单的解释方式了）
禁止抄袭，支持原创！
