1. 红黑树的概念

红黑树：是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保 没有一条路径会比其他路径长出两倍 (最短路径 * 2 >= 最长路径)，因而是接近平衡的。

---

2. 红黑树的性质

🍎① 每个结点不是红色就是黑色

🍎② 根节点是黑色的

🍎③ 如果一个节点是红色的，则它的两个孩子结点是黑色的

🍎④ 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点

🍎⑤ 每个叶子结点都是黑色的(注意：❗这里的叶子结点不是我们平常所说的二叉树的叶子结点，此处的叶子结点指的是空结点）；