13 红黑树
二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 O(logn)。
二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于
log2n的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到O(n)。
为了解决这个复杂度退化的问题，需要设计一种平衡二叉查找树。
0.1. 平衡二叉查找树定义
平衡二叉树的定义：二叉树中任意一个节点的左右子树的高度相差不能大于1。
从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。
最先被发明的平衡二叉查找树是AVL树，它严格符合平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。
但是很多平衡二叉查找树并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1），比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。
发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。所以，平衡二叉查找树中“平衡”的意思，是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
0.2. 红黑树
平衡二叉查找树其实有很多，比如：
- Splay Tree（伸展树）
- Treap（树堆）等，
但是提到平衡二叉查找树，基本都是红黑树，甚至默认平衡二叉查找树就是红黑树。
红黑树的英文是“Red-Black Tree”，简称 R-B Tree，它是一种不严格的平衡二叉查找树。红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：
- 根节点是黑色的
- 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据(简化代码而设置的要求)
- 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
0.2.1. 近似平衡的红黑树
平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以：
- “平衡”的意思可以等价为性能不退化
- “近似平衡”就等价为性能不会退化的太严重