数据结构===红黑树

概要

这篇说下红黑树

其实，红黑树，对于我来说，比较重要的几点。

1. 满足几个条件
2. 基本思想
3. 插入
4. 删除

这些是很重要的。

满足的条件

红黑树需要满足什么条件呢？

应该有四个，如下：

1. 节点非黑既红
2. 根节点是黑色
3. 叶子（NIL）结点是黑色
4. 红色节点下面接两个黑色节点
5. 从根节点到叶子结点路径上，黑色节点数量相同

基本思想

这个，除了上边四个条件；还要有2个操作，左旋和右旋。

有了这些条件，再加上左旋右旋操作，接下来看看红黑树的插入，删除。

操作

红黑树的插入

1. 叔叔节点为红色的时候，修改三元组小帽子，改成红黑黑
2. 叔叔节点为黑色的时候，参考 AVL 树的失衡情况，分成 L L , L R , R L , R R LL,LR,RL,RRLL,LR,RL,RR, 先参考 AVL 树的旋转调整策略，然后再修改三元组的颜色，有两种调整策略：红色上浮，红色下沉。
3. 两大类情况，包含 8 种小情况

红黑树的删除

1. 删除红色节点，不会对红黑树的平衡产生影响
2. 度为1的黑色节点，唯一子孩子，一定是红色
3. 删除度为1的黑色节点，不会产生删除调整
4. 删除度为0的黑色节点，会产生一个双重黑的 NIL 节点
5. 删除调整，就是为了干掉双重黑

删除调整：

1. 双重黑节点的兄弟节点是黑色，兄弟节点下面的两个子节点也是黑色，父节点增加一重黑色，双重黑与兄弟节点，分别减少一重黑色。
   
2. 兄弟节点是黑色，并且，兄弟节点中有红色子节点

1. R（兄弟）R（右子节点），左旋，新根改成原根的颜色，将新根的两个子节点，改成黑色
2. R（兄弟）L（左子节点），先小右旋，对调新根与原根的颜色，转成上一种情况
3. LL 同理 RR
4. LR 同理 RL

3. 兄弟节点是红色，通过旋转，转变成兄弟节点是黑色的情况
   

遍历操作

树的遍历，都有前序，中序，后序三个操作。对于红黑树，插入，删除都是O(1)的时间复杂度。来看看代码。

代码C++

关于代码，网上版本比较多，不提供参考意见。可以看下ngx_rbtree.c，ngx_rbtree.h的实现。

小结

红黑树是一个比较复杂的数据结构。不过，还是要学习下的，可以参考下动画动画链接，这个里边有模拟插入删除的整个调整过程。有些时候看文字确实比较模糊，不容易学会儿。代码还是要看下的，可以配合一些动画。