说明：本资料中的内容及截图为本人在网络上学习时记录下的，侵权必删

1、红黑树性质

性质1：每个结点要么是黑色，要么是红色
性质2：根结点是黑色
性质3：每个叶子结点（NIL）是黑色
性质4：每个红色结点的两个子结点一定都是黑色。
不能两个红色结点相连。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

红黑树并不是一个完美平衡的二叉查找树
红黑树维持自平衡的三种操作

a.变色：结点的颜色由红变黑或由黑变红
b.左旋：以某个结点作为支点（旋转结点），其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
c.右旋：以某个结点作为支点（旋转结点），其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

红黑树插入情景4.1：

叔叔结点存在且为红结点
依据红黑树性质4可知，红色结点不能相连==>祖父结点肯定为黑结点
因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑树层数的情况是：黑红红。最简单的处理方式是将其改为：红黑红
示意图

处理方式：
1.将P和U结点改为黑色
2.将PP改为红色
3.将PP设置为当前结点，进行后续处理

插入情景4.2 叔叔结点不存在或为黑色结点，并且插入结点的父亲结点是祖父结点的左子节点

注意：单纯从插入前来看，叔叔结点非红即空（NIL结点），否则破坏了红黑树性质5，此路径会比其他路径多一个黑色结点，

插入情景4.2.1 新插入结点，为其父结点的左子节点（LL红色情况）

处理方式：
1.变颜色：将P设置为黑色，将PP设置为红色
2.对PP结点进行右旋

插入情景4.2.2 新插入结点，为其父结点的右子节点（LR红色情况）

处理：
1.对P进行左旋
2.将P设置为当前结点，得到LL红色情况
3.按照LL红色情况出路（1.变颜色 2.右旋PP）

插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父结点是祖父结点的右子节点

该场景对应情景4.2，只是方向反转。

插入情景4.3.1：新插入结点，为其父结点的右子结点（RR红色情况）

处理：
1.变颜色：将P设置为黑色，将PP设置为红色
2.对PP结点进行左旋

插入情景4.3.2：新插入结点，为其父结点的左子结点（RL红色情况）

处理：
1.对P进行右旋
2.将P设置为当前结点，得到RR红色情况
3.按照RR红色情况处理（1.变颜色 2.左旋PP）