红黑树在C++的STL中很广泛，例如map和set都是用红黑树实现的，此外还大量应用在Linux系统中。所以有必要深入了解下。
定义
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树的基础上增加了以下要求：
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是NIL节点）。
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
插入
先把结点标记为红色，再按二叉查找树的方法插入，最后再根据红黑树的要求进行调整。 所以我们根据插入后被破坏的红黑树性质进行分情况讨论。
- 被插入节点是根结点直接涂黑
- 被插入节点的父根结点为黑色，那么插入后的新树仍然是一棵红黑树
- 被插入的节点的父节点是红色，那么我们调整的最终目标是将这两个红色层层上移动，最终通过旋转将其中一个红色移动到最顶端，然后将其涂黑（注意不节点移动，只是颜色自下而上传递）
Case 1 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。 (01) 将“父节点”设为黑色。 (02) 将“叔叔节点”设为黑色。 (03) 将“祖父节点”设为“红色”。 (04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。
Case 2 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子 (01) 将“父节点”作为“新的当前节点”。 (02) 以“新的当前节点”为支点进行左旋。
Case 3 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子 (01) 将“父节点”设为“黑色”。 (02) 将“祖父节点”设为“红色”。 (03) 以“祖父节点”为支点进行右旋。
为何将插入节点置为红色？ 选黑色不是不可以，调整嘛，最终总是能符合定义。首先我们插入操作对之前的红黑树造成的破坏只可能有2.4.5，当我们选择红色的时候永远不会违反性质5，所以置为红色比黑色要简单。
与AVL树比较
- 如果插入引起了树的不平衡，AVL和红黑树都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除引起树的不平衡时，最坏情况下，AVL需要维护从被删节点到根这条路径上所有节点的平衡性，因此需要旋转的量级O(logN)，而红黑最多只需3次旋转，只需要O(1)的复杂度。
- AVL的结构相较RB-Tree来说更为平衡，所以在插入和删除node更容易造成不平衡，因此在大量数据需要插入或者删除时红黑树效率更高。