什么是红黑树？
红黑树就是一种平衡二叉树，说它平衡的意思是它不会出现左子树与右子树的高度之差不会大于1，左子树和右子树保持一种平衡的关系。
5个性质:
- 每个节点要么为黑色，要么为红色。
- 根节点是黑色。
- 每个叶子节点是黑色是空节点（null）。
- 每个红色节点的两个子节点一定是黑色。
- 任意一个节点到每个叶子节点的路径都包含数量相同的黑色节点（黑高）。
如图：?
?
为什么红黑树能自平衡？
红黑树自平衡靠的是三种操作：左旋、右旋、变色。
变色：节点的颜色由红变黑或由黑变红
左旋：以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。
如图：?
右旋：以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。?
如图：
红黑树查找?
因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：
- 从根结点开始查找，把根结点设置为当前结点；
- 若当前结点为空，返回null；
- 若当前结点不为空，用当前结点的key跟查找key作比较；
- 若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；
- 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；
- 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；
?红黑树的插入
插入操作包括两部分工作：
- 查找插入的位置
- 插入后自平衡
查找插入的父结点很简单，跟查找操作区别不大：
- 从根结点开始查找；
- 若根结点为空，那么插入结点作为根结点，结束。
- 若根结点不为空，那么把根结点作为当前结点；
- 若当前结点为null，返回当前结点的父结点，结束。
- 若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点的值，结束。
- 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；
- 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；
注意：插入节点，必须为红色，理由很简单，红色在父节点（如果存在）为黑色节点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。
插入的情况有很多，下面将列举出来。
在开始每个情况的讲解前，我们还是先来约定下，如图：
情况1
红黑树为空树
最简单的一种情景，直接把插入结点作为根结点就行
注意：根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。
情况2
插入结点的Key已存在
处理：更新当前节点的值，为插入节点的值
情况3
插入结点的父结点为黑结点
由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。?
情况4
插入节点的父节点为红色
根据性质2：根结点是黑色。如果插入节点的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。又分为很多子情景
4.1.叔叔结点存在并且为红结点
依据红黑树性质4可知，红色节点不能相连 ==> 祖父结点肯定为黑结点；
因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红
处理：
1.将P和U节点改为黑色
2.将PP改为红色
3.将PP设置为当前节点，进行后续处理
可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；?
但如果PP的父结点是红色，则违反红黑树性质了。所以需要将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）
?
?