红黑树（Red-black tree）
简述
红黑树同AVL树一样也是一种自平衡二叉搜索树，不同于AVL树是高度平衡树，红黑树属于近似平衡树。
所谓近似平衡就是对平衡的要求相对宽松，不像AVL树那么严格。红黑数的平衡标准是：任一节点的左右子树的高度差小于两倍。
判断一颗二叉搜索树是否是红黑树的条件如下:
- 每个节点非黑即红
- 根节点必须是黑色
- 每个叶子节点必须是黑色，即NIL节点或空节点必须是黑色
- 不能出现连续的红色节点，即不能有两个相邻的红色节点
- 任一节点到其每个叶子节点的所有路径都包含相关数目的黑色节点
其中，最后两点可确保红黑树的平衡标准始终得以满足，证明过程略。
复杂度
时间复杂度
由于红黑树也是近似平衡树，所以其查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。
空间复杂度
红黑树的空间复杂度只与节点个数相关，因此为O(n)。
对比AVL数
红黑树与AVL树的比较：
- AVL树的查找速度更快，因为AVL有更为严格的平衡标准
- 红黑树提供了更快的插入和删除的操作，因为红黑树的平衡标准更为宽松，所以旋转操作更少。
- 红黑树对额外空间的消耗更小。AVL树的每一个节点需要存储一个平衡因子或高度值，只是需要一个整型，而红黑树只需要一个bit位用于标识节点的颜色属性，非红即黑。
综上， 红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入或删除操作更少的旋转操作，整体来说性能优于AVL树。
注：红黑树和AVL树在数据量较小时的性能相近，但是在百万或千万级的数据量时，二者的性能差异会比较明显。
使用场景
鉴于红黑树在插入和删除的性能更佳，因此广泛用于实现插入或删除操作较为频繁的数据结构，如C++的STL中map和set等。