摘要

本节在前两节（树的旋转，2-3-4树）的基础上，讨论红黑树的性质及实现。

初识红黑树

简介

通过对2-3-4树的分析，我们认识到其直接实现比较复杂，时间开销可能会比普通BST更大。因而我们通过对普通BST增加一些信息，实现2-3-4树。这里采用的一种高效的方法，就是红黑树。基本思想是在每个结点中添加一个额外的颜色信息用来表示3-和4-结点。我们将链接看成两种不同的类型：红链接用于绑定3-和4-结点组成的小二叉树，黑链接用于绑定2-/3-/4-结点组成二叉树。如图：3-结点表示为由一个红链接连接的两个2-结点，4-结点表示为由两个红链接连接的三个2-结点。

在任何树中，每个节点（除了根节点）都有一个链接指向它，因而对节点着色等价于对链接着色。我们注意到：3-节点有两种表示形式，这个留给红黑树作为宽容度，根据情况选择合适的3-节点表示法。虽然我们可以使得3-结点向同一个方向偏斜，但没有充分理由支持我们这样做。

如果消除红黑树中的红链接，并合并被捆绑的结点，我们就可以得到一棵2-3-4树，如图：

可以看到，红黑树非常出色地表达出2-3-4树的结构。通过合并红节点，将得到相同的2-3-4树。
因而我们得到了红黑树的基本性质：1）BST的标准搜索过程不需修改就可以直接使用；2）红黑树直接与2-3-4树对应，因而只要维护这种对应关系，就可以实现平衡2-3-4树算法。
通过红黑树，我们得到了两种结构的优点：标准BST的简单搜索过程和2-3-4树简单的插入-再平衡过程。应当注意到，搜索过程不会检查结点颜色，因而平衡机制不会增加基本搜索的时间开销。

出于完备性考虑，我们抛开2-3-4树结构，再来分析红黑树，可以得到如下性质：
1）每个结点非红即黑；
2）根节点为黑；
3）所有NULL结点（叶节点）为黑；
4）红结点的两个子节点均为黑；
5）对于每个结点，从该节点到其子孙结点所有路径上，包含的黑结点数目相同。

2-3-4树节点分裂与红黑树的表示

见图就行了，没什么好讲的：

数据结构选讲-深入理解红黑树（Red Black Tree）