刚看完网易公开课上算法导论中的平衡搜索树，传送门，讲的真的炒鸡好，这里就稍微总结一下。
另一方面，视频是英文板书，在一些地方讲述有点慢，这时候就凸显了文章的优势了。
红黑树性质
红黑树的性质判定红黑树的充要条件，性质见下：
- 每个节点不是红色就是黑色。
- 根节点和叶子节点必须为黑色。
- 每个红色节点的父亲节点必须为黑色节点。
- 对于每个节点，在它到每一个子树的叶子节点的所有路径中，所经过的黑色节点数量相同。并定义这个数量为黑高(black height)。
补充一条推论，由性质3易得，一颗红黑树的红色节点不会超过总节点数的一半。
而对于第2条性质，我们一般会使最后指向的空节点染色成黑色即可。
红黑树的树高
先说结论，红黑树的树高 height 不会超过 $ 2log_2{(n+1)} $，即 $ height \leq 2 log_2{(n+1)} $。
证明如下：
将所有红色节点合并到其父亲节点，同时使该节点的孩子节点也合并成为其父亲节点的孩子节点。
这时候我们会得到一棵特别的树，它也是一棵平衡搜索树，称为2-3-4树。（建议在纸上画画）
2-3-4树有如下两条性质：
- 对于每个非叶子节点，它的孩子节点数量范围为[2,4]
- 对于每个叶子节点，它的深度都相同。
我们设由红黑树所得的2-3-4树的树高为 h'，其叶子节点的数量为 leaf_num。可得不等式
$$ 2^{h’} \leq leaf_num \leq 4^{h’} $$
进而推导出 $ h’ \leq log_2{leaf_num} $
就剩下我们的leaf_num了，其实leaf_num和红黑树的叶子节点的数量是一样的，而一棵树的叶子节点的数量是这棵树的非叶子节点数量 + 1，这是显而易见的。而在我们的红黑树中，非叶子节点数量就是我们插入的元素数量 $ n $。
将其代入得$ h’ \leq log_2{(n+1)} $
最后再联系到我们最开始的目标，红黑树的树高height，因为我们只合并了红色节点，根据红黑树性质3的推论可得
$$ 2height \geq h’ $$
因此，$ height \leq 2log_2{(n+1)} $ 得证。
红黑树的查询
因为树高是在 log 级别，所以只要按照二叉搜索树的查找方法来即可。
复杂度上限为一个树高，即一个 log 。
红黑树的插入
省去引入与例子，直接讲解法。
首先插入时按照二叉搜索树的方法插入，将其染色为红色，这样不会影响树高，易修复，但可能会破坏性质3。
现在假设插入节点 x与其父亲节点p[x]都为红色，即破坏了性质3。
其修复步骤主要分2种情况，这里将之称为两个主要情况：
- 父亲节点是祖父节点的左孩子
- 父亲节点是祖父节点的右孩子
这两种主要情况下又分为三种次要情况，这里以上述主要情况1的条件下分类讨论：
- 祖父节点的右孩子
p[p[x]].right，即叔叔(uncle)节点也为红色。此时让父亲节点和叔叔节点都染色成黑色，祖父节点染色成红色，将当前节点变更到祖父节点，进入下一个循环。 - 叔叔(uncle)节点为黑色，当前节点
x为父亲节点p[x]的右孩子。此时将父亲节点左旋，使得进入情况3。 - 叔叔(uncle)节点为黑色，当前节点
x为父亲节点p[x]的左孩子。可由情况2旋转得来。此时将祖父节点右旋并重新染色。染色方案为，新的祖父节点为黑色，新的父亲节点和新的叔叔节点为红色。退出循环。
而对于主要情况2，只要对主要情况1的3种次要情况做类似操作即可，唯一不同的就是方向反一下。
即 “左”–> “右”，“右”–> “左”。
红黑树的删除
视频没讲，有点晚了，明天看，并且补上C++代码实现。