简单介绍完二叉查找树与平衡树之后，我们现在来审察平衡树中一种特殊的平衡方式，那便是红黑树。

Intro

红黑树¹（Red-Black Tree，简称RBT） 之所以叫红黑树是因为其节点具有红与黑两种颜色，可以视为“被染色”和“未染色”两种状态。
红黑树通过控制红黑两种节点的排列来保证其平衡，为此，一棵红黑树满足以下特征：

1. 节点为红色或黑色；
2. 红色的节点的所有儿子的颜色必须是黑色，即从每个叶子到根的所有路径上不能有两个连续的红色节点；
3. 从任一节点到其子树中的每个叶子的所有简单路径上都包含相同数目的黑色节点（黑高平衡）。

这保证了从根节点到任意叶子的最长路径（红黑交替）不会超过最短路径（全黑）的二倍，从而保证了树的平衡性。

如图所示便是一棵红黑树，满足以上各项性质。

References

¹. OI-Wiki 章节 左偏红黑树-红黑树 ↩

². 13 Red Black Trees Bilibili: av14050857 2017-09-01 ↩

³. 「JDK源码剖析之红黑树TreeMap」子空kosora+七月在线 Bilibili: av23890827 2018-05-25 ↩