红黑树的介绍和实现

1. 红黑树

1.1 红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

1.2 红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的(没有连续的红色结点)
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(每条路径都包含相同数量的黑色结点)
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

答案是：根据第3点和第4点。最短路径是：全黑。最长路径是：一黑一红间隔。

1.3 红黑树节点的定义

1.4 红黑树的插入

如果我们插入一个新结点，把它设置成红色还是黑色？
如果我们新增的是红色，可能会破坏规则3。新增黑色，一定会破坏规则4。维护规则4比较难，我们去新增的设置红色比较好。

插入和前面AVL树类似，只需要把颜色设置一下就行了。

但是新节点插入后，红黑树的性质是否造到破坏？
因为新节点的默认颜色是红色，如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整。

但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。a，b，c，d，e都是子树。

情况一: cur为红，p为红，g为黑，u存在且为红

cur和p均为红，违反了性质三，此处能否将p直接改为黑？
不能，原因是直接改变黑，那么两边的黑色结点数量不同了。

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

为什么要把g给设置成红色呢？
这颗树可能是局部子树，这样会保存局部子树的黑色结点数量不变。

这种情况，p，u是g的左和右没有关系，cur是p的左右也没有关系。只变色，不旋转。

代码实现：

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑，并且g，p，cur都在同一边。

u不存在：

u存在且为黑：


解决方式：p为g的左孩子，cur为p的左孩子，则进行右单旋转。相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转。
p、g变色–p变黑，g变红。

代码实现：

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑，但是g，p，cur不在同一边。

u不存在：

u存在且为黑：

变色后：

解决方式：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，然后对g进行右单旋转。相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，然后对g进行左单旋转。
cur、g变色–cur变黑，g变红。

代码实现：


情况二和情况三，旋转+变色以后，这颗子树不违反红黑树规则，比插入前，黑色结点的数量不变。不会影响上层，就结束。

1.5 红黑树的验证

验证红黑树，我们需要检测其是否满足红黑树的性质。在红黑树的性质中，主要验证性质三和性质四。

验证性质三：遇到红色结点，检查父亲。
验证性质四：先以一条路径为基准，于其它条路径的黑色结点数量作比较。

代码如下：

验证如下：

1.6 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是一样的，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。