概要
这篇说下红黑树
其实，红黑树，对于我来说，比较重要的几点。
- 满足几个条件
- 基本思想
- 插入
- 删除
这些是很重要的。
满足的条件
红黑树需要满足什么条件呢？
应该有四个，如下：
- 节点非黑既红
- 根节点是黑色
- 叶子（NIL）结点是黑色
- 红色节点下面接两个黑色节点
- 从根节点到叶子结点路径上，黑色节点数量相同
基本思想
这个，除了上边四个条件；还要有2个操作，左旋和右旋。
有了这些条件，再加上左旋右旋操作，接下来看看红黑树的插入，删除。
操作
红黑树的插入
- 叔叔节点为红色的时候，修改三元组小帽子，改成红黑黑
- 叔叔节点为黑色的时候，参考 AVL 树的失衡情况，分成 L L , L R , R L , R R LL,LR,RL,RRLL,LR,RL,RR, 先参考 AVL 树的旋转调整策略，然后再修改三元组的颜色，有两种调整策略：红色上浮，红色下沉。
- 两大类情况，包含 8 种小情况
红黑树的删除
- 删除红色节点，不会对红黑树的平衡产生影响
- 度为1的黑色节点，唯一子孩子，一定是红色
- 删除度为1的黑色节点，不会产生删除调整
- 删除度为0的黑色节点，会产生一个双重黑的 NIL 节点
- 删除调整，就是为了干掉双重黑
删除调整：
- 双重黑节点的兄弟节点是黑色，兄弟节点下面的两个子节点也是黑色，父节点增加一重黑色，双重黑与兄弟节点，分别减少一重黑色。
- 兄弟节点是黑色，并且，兄弟节点中有红色子节点
- R（兄弟）R（右子节点），左旋，新根改成原根的颜色，将新根的两个子节点，改成黑色
- R（兄弟）L（左子节点），先小右旋，对调新根与原根的颜色，转成上一种情况
- LL 同理 RR
- LR 同理 RL
- 兄弟节点是红色，通过旋转，转变成兄弟节点是黑色的情况
遍历操作
树的遍历，都有前序，中序，后序三个操作。对于红黑树，插入，删除都是O(1)的时间复杂度。来看看代码。
代码C++
关于代码，网上版本比较多，不提供参考意见。可以看下ngx_rbtree.c，ngx_rbtree.h的实现。
小结
红黑树是一个比较复杂的数据结构。不过，还是要学习下的，可以参考下动画动画链接，这个里边有模拟插入删除的整个调整过程。有些时候看文字确实比较模糊，不容易学会儿。代码还是要看下的，可以配合一些动画。
