什么是红黑树
红黑树是在AVL树的基础上改进的一种二叉查找树，英文名R-B Tree
上一篇我们已经讲过，AVL树是一种高度平衡的二叉查找树
它的查找效率最高，但是由于要维护平衡性，插入和删除效率便降低了
红黑树则是降低了一点平衡性的要求，从而来提升插入和删除效率
由于在实际场景中，很难有数据只查询不修改的，因此红黑树的适用场景更广，综合效率更高
红黑树的特性
红黑树的节点必须满足以下五个特性
- 每个节点带有颜色，要么红色，要么黑色
- 根节点必须为黑色
- 叶节点必须为黑色（红黑树所有的叶节点，都是虚构出来的NIL节点，这是为了方便调整红黑树的平衡性）
- 每个红节点的孩子必定为黑色（不存在两个连续的红色节点）
- 任意节点，到其所有的叶节点，中间经过的黑色节点数量是相同的
以上规定，最终决定了红黑树的平衡性：
根节点到任意叶节点的最长路径，不多于最短路径的两倍（路径全黑时最短，红黑相间时最长）
可见，红黑树中的节点平衡因子，是可以大于1的
红黑树插入时的平衡性修复
红黑树的平衡修复，主要是通过染色、左旋、右旋三种方式来实现的
在向红黑树插入新节点时，我们一般都将节点染成红色
因为插入红色节点时，只需要处理两个节点连续红色的问题，比较容易修复
如果插入黑色节点，则会出现根节点到叶节点黑色点数量异常的问题，这个比较难修复
红黑树的插入大致可以分为七大类情形，在讲述这七大类情形时，我们先了解一下术语定义
- N：Now，刚插入的待平衡的新节点
- P：Parent，新节点的父节点
- GP：GrandParent：祖父节点，即父节点的父节点
- U：Uncle，叔父节点，即父节点的兄弟节点
情形一：N为根节点
N染成黑色，直接作为红黑树根节点即可，修复完成
情形二：P为黑色
黑色点数量不变，不影响平衡性，无需任何处理，修复完成
情形三：P为红色，U为红色
P和U染黑，GP染红。再以GP作为新的N节点，递归修复平衡性
情形四：P为红色，U为黑色，P左N左
GP右旋，P染黑，GP染红，修复完成
情形五：P为红色，U为黑色，P右N右
GP左旋，P染黑，GP染红，修复完成
情形六：P为红色，U为黑色，P左N右
N右旋。再以P作为新的N节点，递归修复平衡性
情形七：P为红色，U为黑色，P右N左
N左旋。再以P作为新的N节点，递归修复平衡性
红黑树删除时的平衡性修复
红黑树的删除比较繁琐，分为很多种情况，每种情况又有很多子类型
整体上，根据节点位置，可以分为四大类情况
- 删除节点为叶节点
- 删除节点只有左孩子，没有右孩子
- 删除节点只有右孩子，没有左孩子
- 删除节点既有左孩子，又有右孩子
下面我们逐个情况来讲解如何进行删除和再平衡
在此之前，我们先要搞清楚，怎么样才算平衡性修复成功
这个判断标准就是：根节点到所有NIL节点的黑色出现次数，和平衡之前相等
我们统一将被删除节点称为D节点，D节点兄弟为B节点，D节点父亲为P节点，B节点孩子分为LN和RN节点
1 D为叶节点
这种情况又分为D为红色，D为黑色两大类情况
1-1 D为红色
直接删除D节点即可
1-2 D为黑色
这又分为D在P左侧，以及D在P右侧的情况，我们只讲解D在左侧的情况，另一种情况处理方式是一样的
对于红黑树的任意叶节点，其最下面两层的结构，只可能是以下五种情况
由于D为黑色，且为叶节点，要保持平衡性，则P右侧必有一个黑色节点，且最多两层，只可能是以下五种情况
由于这个情况下包含太多子情景了，我们先讲234的情况
2 D有左孩子，没有右孩子
LC的值赋给D，删除LC
3 D有右孩子，没有左孩子
RC的值赋给D，删除RC
4 D有左孩子，也有右孩子
LC的值赋给D，问题转换为递归删除LC
下面我们回到前面的问题，再来讲解D为叶节点，且D为黑色的五种情况
1-2-1
1-2-2
1-2-3
1-2-4
1-2-5
红黑树代码实现
红黑树实现代码的核心是插入和删除后的再平衡
由于红黑树的情景实在是太多了，这里不再逐个实现，一般面试也不会让大家手动去实现红黑树
但是当大家拿到一张红黑树的图时，自己应当知道如何去删除某个节点并进行平衡修复
红黑树特性和应用
普通二叉查找树，查找、插入、删除操作，在最坏情况下复杂度是O(n)，最好情况下复杂度是O(logN)
而红黑树则可以保证，在最坏情况下复杂度为O(logN)，整体效率比普通二叉查找树高很多
红黑树在Java中的主要应用场景有HashSet和HashMap