目录
一、概述
二、红黑树插入
三、总结
一、概述
红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找没有什么区别，可以看前面的文章进行学习，这里不再过多阐述。本节我们主要总结红黑树插入相关的知识。
二、红黑树插入
红黑树的插入包含两个步骤：
在树中查找插入的位置；插入后自平衡；
查找流程：
从根节点开始查找；若根节点为空，那么插入节点作为根节点，结束；若根节点不为空，那么把根节点作为当前节点；若当前节点为null，返回当前节点的父节点，结束；若当前节点key等于查找key，那么该key所在节点就是插入节点，更新节点的值，结束；若当前节点key大于查找key，把当前节点的左子节点设置为当前节点，重复步骤4；若当前节点key小于查找key，把当前节点的右子节点设置为当前节点，重复步骤4；
经过上面几个步骤已经找到节点插入的位置了，把插入节点放到正确的位置就可以了。
注意：插入节点应该是红色。
原因：根据红黑树特性之一【任意一节点到每个叶子节点的路径都包含数量相同的黑节点】，红色在父节点（如果存在）是黑色节点时，红黑树的黑色平衡不会被破坏，所以不需要进行自平衡操作。但如果插入节点是黑色，那么插入位置所在的子树黑色节点总是多1，必须做自平衡操作。
红黑树插入分很多种情况：
【a】红黑树为空树
因为红黑树为空树，所以直接将插入节点作为红黑树的根节点，然后注意红黑树跟节点必须为黑色，所以还需要将插入节点的颜色变为黑色，这种情况是最简单的红黑树插入操作。
处理步骤总结：
把插入节点作为根节点把节点设置为黑色
【b】插入节点的Key已存在
根据key值，在红黑树中查找已经存在相同key的节点，因为插入之前红黑树已经是平衡的，所以只需要将插入节点的颜色设置为已存在的相同key的节点的颜色，然后更新key值即可。
处理步骤总结：
把插入节点设为当前节点的颜色；更新当前节点的值为插入节点的值；
【c】插入节点的父节点为黑节点
因为红黑树规定新插入节点的颜色为红色，当插入节点的父节点为黑色时，并不会破坏【任意一节点到每个叶子节点的路径都包含数量相同的黑节点】特性，所以无需进行平衡操作，直接插入即可。
处理步骤总结：
无需进行平衡操作，直接插入新节点
【d】插入节点的父节点为红节点
这种情况是最复杂的，因为红黑树规定新插入节点的颜色为红色，当插入节点的父节点为红色时，必然就破坏了【任意一节点到每个叶子节点的路径都包含数量相同的黑节点】特性，所以这种情况必须进行自平衡操作。
这种情况也分为下面好几种场景：
【d-1】叔叔节点存在并且为红节点；【d-2】叔叔节点不存在或为黑节点，并且插入节点的父亲节点是祖父节点的左子节点；
【d-1】叔叔节点存在并且为红节点【叔叔节点：S 插入节点：I 父节点：P 祖父节点：PP】
从红黑树【每个红色节点的两个子节点一定都是黑色】特性可以推测出插入节点的祖父节点PP肯定为黑节点，因为不可以同时存在两个相连的红节点。那么此时该插入子树的红黑层数的情况是：黑红红。最简单的处理方式是把其改为：红黑红。
示意图如下所示：
可见，插入节点的祖父节点PP已经是红色节点，如果PP的父节点是黑色，那么满足【不能存在相连的两个红色节点】特性；如果PP的父节点是红色，那么PP红色，PP父节点也是红色，又得从PP节点出发，继续进行插入自平衡操作，一直到红黑树平衡为止。
【d-2】叔叔节点不存在或为黑节点，并且插入节点的父亲节点是祖父节点的左子节点【叔叔节点：S 插入节点：I 父节点：P 祖父节点：PP】
如果叔叔节点为黑节点，而父节点为红节点，那么叔叔节点所在的子树的黑色节点就比父节点所在子树的多1了，这不满足红黑树【任意一节点到每个叶子节点的路径都包含数量相同的黑节点】特性。下图也可以看出不满足：
【d-2】又可以分为如下两种：
【d-2-1】插入节点是其父节点的左子节点；【d-2-2】插入节点是其父节点的右子节点；
【d-2-1】插入节点是其父节点的左子节点
处理步骤总结：
P设置为黑色PP设置为红色对PP节点进行右旋
【d-2-2】插入节点是其父节点的右子节点
处理步骤总结：
对P节点进行左旋操作就得到上面一种情况【d-2-1】【插入节点是其父节点的左子节点】I设置为黑色PP设置为红色对PP节点进行右旋
【d-3】叔叔节点不存在或为黑节点，并且插入节点的父亲节点是祖父节点的右子节点
【d-3】可以分为如下两种情况：
【d-3-1】插入节点是其父节点的右子节点【d-3-2】插入节点是其父节点的左子节点
【d-3-1】插入节点是其父节点的右子节点
处理步骤总结：
P设置为黑色PP设置为红色对PP节点进行左旋
【d-3-2】插入节点是其父节点的左子节点
处理步骤总结：
对P节点进行右旋操作就得到上面一种情况【d-3-1】【插入节点是其父节点的右子节点】I设置为黑色PP设置为红色对PP节点进行左旋
三、总结
本篇文章主要总结了红黑树插入的四种情况，其中前三种情况都比较好理解，第四种情况比较复杂，需要好好画图才能理解的好一些，附上笔者关于红黑树插入的脑图总结：
由于笔者水平有限，文中可能存在不对之处，还望大家指正，一起学习，一起进步！
如果觉得《数据结构之红黑树插入详解》对你有帮助，请点赞、收藏，并留下你的观点哦！
