Red Black Trees，在最坏情况下的时间复杂度仍为 。
- 根节点必须为黑色
- 新插入的子节点先默认为红色，后续根据情况重涂
- 每个叶子到根的所有路径上不能有两个连续的红色节点
- 红色节点的父节点和子节点都必须是黑色
结点的删除
待补充
树的性质
树中每个结点包含5 个属性：color、key、left、right 和 p（父节点指针）
- 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
为了便于处理红黑树代码中的边界条件，使用一个哨兵 来代表 。
- A sentinel is a dummy object that allows us to simplify boundary conditions
从某个结点 出发（不含该结点）到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高 (black-height)，记为 。
- 根据颜色性质，从该结点出发的所有下降到其叶结点的简单路径的黑结点个数都相同。即红黑树的黑高即为其根结点的黑高。
- 设 为树的高度，从根到叶结点（不包括根结点）的任何一条简单路径上都至少有一半的结点为黑色。
因此，根的黑高至少为 ，于是有
