红黑树

**红黑树（Red Black Tree）**是一种自平衡二叉查找树。

• 在 1972 年由 Rudolf Bayer 发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树是一种 特化的 AVL 树，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

• 左右子树高差有可能大于 1，因此不是严格意义上的 AVL

红黑树复杂但是高效，可以在 $O(log n)$ 时间内做查找，插入和删除

特征

红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。

在 BST 的硬性要求中添加入以下五个要求：

1. 结点是红色或黑色。
2. 根结点是黑色。
3. 所有叶子都是黑色。（叶子是 NIL 结点）
4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。