b站动画演示 链接
为什么提出红黑树
解决 平衡二叉树AVL 的缺点，详见 链接
平衡二叉树AVL VS 红黑树：
平衡二叉树追求绝对平衡，条件比较苛刻，每次插入、删除新节点后，可能需要大量旋转，会导致性能变差。
所以当程序需要频繁的插入和删除操作时，不会使用 平衡二叉树AVL红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，每次插入、删除要简单很多，不需要那么多的旋转就能达到平衡
红黑树性质
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- 如果一个节点是红色的，则其子节点必须是黑色的。
- 从一个节点（包括根结点），到该节点的子孙节点（NIL或NULL）的所有路径上，包含相同数目的黑节点。[这里指到叶子节点的路径]
- 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
例子
上图是一颗典型的红黑树：
树中的每个结点的颜色要么是黑色，要么是红色；
根结点
6为黑色结点；树中不存在两个相邻的红色结点，比如结点
15为红色结点，其父亲节点6与两个孩子结点就一定是黑色，而不能是红色；从结点到其后代的 NUll结点 的每条路径上具有相同数目的黑色结点
比如根结点6到其左子树的NULL结点 包含 三个黑色结点，到其右子树所有的NULL结点也包含 三个黑色结点。
进一步解释
从根节点查找：
- 根结点 6 到 NULL结点 a 的路径 6→2→a 上的黑色结点为 3 个
- 从根结点 6 到结点 c 的路径 6→15→10→9→c 中包含的黑色结点个数也是 3 个
- 同理从根结点 6 到其他所有 NULL结点 的黑色结点数都是 3 。
从红色节点 15 查找：
- 从红色结点 15 到NULL结点 d 的路径 15→18→g 包含 2 个黑色结点
- 到NULL结点 c 的路径 15→10→9→c 也包含黑色结点 2 个
- 从结点 15 到其所有后代的 NULL结点的 黑色结点数目都是 2 。
红黑树是如何保持平衡的
下面举一个简单但是很经典的例子，包含3个结点的单链是不可能出现在红黑树当中的。 关于这一点，我们可以自己绘制一条单链，然后尝试为其着色，然后判断是否是一颗红黑树证明这一点。
从上图中可以发现，将根结点 9 涂黑色，其他结点分四种情况着色，结果都不满足红黑树的性质要求。唯一的办法就是调整树的高度，下面提供两种可行的设计方案：
红黑树的黑高（可略）
在一颗红黑树中，从某个结点 x 出发（不包含该结点）到达一个叶结点的任意一条简单路径上包含的黑色结点的数目称为 黑高（Black Height) ，记为 bh(x) 。
例子
计算结点 6 的黑高，从结点 6 到结点 c 的路径是
6→15→10→9→c，其中黑色结点为 6、10、c ，但是在计算黑高时，并不包含结点本身，所以从结点 6 到结点 c 的路径上的黑色结点个数为 2 ，那么 bh(6)=2 ；从结点 15 到结点 c 的路径为
15→10→9→c，其中黑色结点为 10、c ，所以从结点 15 到结点 c 的路径上黑色结点数目为 2 ，bh(15)=2 。
黑高相关公式
bh >= h/2
解释：
bh：黑高h：表示从根结点 6 到其最远的叶结点 9 所包含的结点数目 4
结论：
Number of nodes from a node to its farthest descendant leaf is no more than twice as the number of nodes to the nearest descendant leaf.
从一个结点到其最远的后代叶结点的顶点数目不会超过从该结点到其最近的叶结点的结点数目的两倍。
红黑树的高度公式
红黑树的高度 h <= 2log2(n+1)
证明：第一步
先将下图中的所有 红色结点合并到其黑色父结点：
合并后的结果：
合并产生了一颗 2-3-4 树，这棵树中的结点，有2、3 或者 4 个孩子结点。有相同的深度 2，这里记为 h'
公式：
h' < log2(n+1)
证明：第二步
在将红色节点填回来，恢复成红黑树，如下：
根据 性质3，即使一个黑色节点 对应 一个红色节点，高度最多 乘以2，得到 高度公式如下：
h < 2log2(n+1)
红黑树查找复杂度
根据 数据结构：二叉搜索树的查找时间复杂度 得出下面结论：
对于一颗有 n 个结点的红黑树而言，不论查找、删除、查找和最大值、最小值等等的时间复杂度都是 O(logn)
红黑树的使用场景
- java 中使用到红黑树的有 TreeSet 和 JDK1.8 的 HashMap
- linux中进程的调度
参考
https://blog.csdn.net/qfc8930858/article/details/89856274
https://blog.csdn.net/ff_simon/article/details/101055134
https://zhuanlan.zhihu.com/p/143585797