一.红黑树的性质（一种自平衡的二叉查找树）
1. 根节点是黑色。
2. 节点是红色或黑色
3. 叶子节点都是黑色的空节点（NIL节点） 意思就是末尾一排是黑色空节点（可全部省略）
（叶子节点意思是没有子节点的节点）
4. 红色节点不能相连 意思就是每个红色节点的两个子节点都是黑色，且可能出现连续黑色节点
5. 从任意节点出发，到其每个叶子节点（nil节点）的路径中包含相同数量的黑色节点
（这个数值叫黑高度）
（保证树每条分支的黑节点高度一样）
6. 新加入到红黑树的节点为红色节点
7. 从根节点到叶子节点的最长路径不大于最短路径的2倍
①最短路径：根节点到叶子节点只数黑色节点的数量
②最长路径：根节点到叶子节点，红色节点和黑色节点数量相同，即最长路径，也就是黑色节点（或红色节点）* 2
（注：一般需要红黑树自平衡是因为违反了了性质4和性质5）
二.红黑树的实例图
* 红黑树虽然是自平衡的二叉查找树，但是却不能完全保证红黑树绝对平衡
1. 红黑树1
2. 红黑树2
三. 红黑树的自平衡方式
方式1：变色 红变黑 黑变红（不能连续出现两个相邻的红色节点，否则就要变色）
方式2：旋转（左旋，右旋）
1. 左左节点旋转：以祖父节点【右旋】，搭配【变色】
①红黑树
②插入节点65后的自平衡
第一步：以插入节点65的祖父节点69进行右旋
第二步：为了符合红黑树性质5进行变色（注：66为根节点必须为黑色）
2. 左右节点旋转：先父节点【左旋】，然后祖父节点【右旋】，搭配【变色】
①红黑树
②插入节点67后的自平衡
第一步：以插入节点67的父节点66进行左旋
第二步：根据左左节点旋转规则进行后续自平衡
3. 右右节点旋转：以祖父节点【左旋】，搭配【变色】
①红黑树
②插入节点70后进行自平衡
第一步：以插入节点70的祖父节点66进行左旋
第二步：为了符合红黑树性质5进行变色（注：69为根节点必须为黑色）
4. 右左节点旋转：先父节点【右旋】，然后祖父节点【左旋】，搭配【变色】
①红黑树
②插入节点68后进行自平衡
第一步：以插入节点68的父节点69进行右旋
第二步：根据右右节点旋转规则进行后续自平衡
四. 红黑树插入
五. 红黑树删除
情况1：删除的是根节点，则直接将根节点置为null
情况2：待删除节点的左右子节点都为null，删除时将该节点置为null
情况3：待删除节点的左右子节点有一个有值，则用有值的节点替换该节点即可；
情况4：待删除节点的左右子节点都不为null，则找前驱或者后继（一般都是找后继节点），
将前驱或者后继的值复制到该节点中，然后删除前驱或者后继
4.1 前驱为黑色节点，同时子节点都为null
4.2 前驱为黑色节点，并且有一个非null子节点
第一步：用前驱对待删除的节点进行赋值（用后驱节点也可以，这里以前驱节点为例）（待删除节点是64）
第二步：删除前驱节点并进行自平衡
4.3 前驱为红色节点，同时子节点都为null
六. 4道红黑树图解例题
第一题：
①红黑树
②向红黑树中插入节点66
③因为符合红黑树的性质，所以不用自平衡
第二题：
①红黑树
②插入节点51
③红黑树的自平衡
第一步：变色（出现了连续的两个节点是红色节点）
注：这里变色时要时刻记得要满足红黑树性质5
第二步：变色后的树符合红黑树的性质，所以自平衡完成
第三题:
①红黑树
②插入节点65：符合插入的右左节点旋转
③红黑树的自平衡
第一步：以插入节点65的父节点66进行右旋
第二步：以66的祖父节点进行左旋
第三步：自平衡（变色达到自平衡）
第四题：
①红黑树
②插入节点6并进行自平衡
第一步：插入节点6
第二步：变色
第三步：左旋
第四步：右旋
第五步：变色
