红黑树（Red Black Tree） 是一种自平衡二叉查找树。一种特化的AVL树，在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 它可以在O(log n)时间内做查找，插入和删除。
它的每个结点都被“着色”为红色或者黑色，这些结点的颜色被用来检测树的平衡性。
- C++ STL的map和set
- java 中 HashMap、TreeMap 的底层实现，当HashMap中元素大于8个时，HashMap底层存储实现改为红黑树，以提高元素搜索速度。 关于 HashMap 实现解析参考 这里
- 广泛应用Linux 的进程管理、内存管理，设备驱动及虚拟内存跟踪
- epoll的的的实现采用红黑树组织管理的的的sockfd，以支持快速的增删改查
- Nginx的的的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器
- 每个节点非红即黑
- 根节点是黑的
- 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的
- 如果一个节点是红的，那么它的两儿子都是黑的
- 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点
- 每条路径都包含相同的黑节点
在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）；通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍；
因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树）。相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。
也就是说，红黑树牺牲掉一定的平衡性（牺牲查找性能），换来了 插入，删除操作时 更少的旋转次数带来的开销。
- 红黑树多用在内部排序，即全放在内存中的
- B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构； 这也是为什么 mysql索引使用b+树而不使用红黑树
为什么使用 红黑树 而不是 B+ 树呢？原因如下：
- 没有范围查找, 不需要 B+
- 不需要多路平衡树，使用二路平衡，实现简单，且红黑树能兼顾 查找，删除操作的性能