算法与数据结构(5): 红黑树

红黑树（red-black tree）是一种二叉搜索树，其每个结点上增加了一个存储位来表示结点的颜色（红或黑）。通过对任何一条从根到叶子的简单路径上的各个结点的颜色进行约束，红黑树确保没有一条路径会比其它路径长出2倍，因而近似于平衡。

红黑树中进行搜索、插入、删除操作的时间复杂度均为。

红黑树具备的性质：

• 每个结点的颜色或是黑色或是红色。
• 根结点的颜色是黑色的。
• 每个叶节点（NIL）是黑色的。
• 红色结点的孩子都是黑色结点。
• 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数量的黑色结点。

下图展示的便是一个红黑树的示例：