数据结构之旅：红黑树如何驱动 Set 和 Map

一、红黑树

1、定义

        红黑树是一种二叉搜索树，在每个节点上增加一个存储位表示结点的颜色(红色或者黑色)。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保不会有一条路径比其他路径长出两倍，因而这种树是一种接近平衡的。和AVL（平衡二叉搜索树）区别就是不需要严格计算并控制平衡因子使得左右子树之间的高度差不超过1的繁琐过程。

2、满足条件

（1）根节点是黑色。

（2）每个结点不是黑色就是红色

（3）对于每个结点，从该结点到其所有后代叶子结点的简单路径上均包含相同数目的黑色结点。

（4）每个叶子结点都是黑色的（这里的叶子结点和前面不同指的是空结点）。

定理：红黑树中最长路径中的结点的个数不会超过最短路径结点个数的两倍。

3、实现原理

（1）要保证插入结点一定是红色结点，否则会导致结点路径黑色结点个数增加，进而导致其他结点路径的黑色结点数目也要跟着变化。

（2）情景一：插入结点父结点为黑色，则直接插入即可，无需其他处理。

（3）情景二：插入结点cur、cur的父结点p和叔叔结点u均为红色(c,p,u均红)。

这种情况只需要颜色变更即可，首先将g变红，p,u变黑，然后如果g为根节点则直接将g变黑即可，如果g不是根节点，则需要将c结点变为cur结点,g,p,u按照相同规则更新，然后按照上述方法继续调整，直到父节点为黑色或者g为根节点。

（4）情景三：插入结点的父结点p为红色，并且叔叔结点u为黑色或者不存在的情况。

a、当叔叔结点存在且为黑色的情况：其中cur为p的左节点，并且p为g的左节点。下面图中的cur肯定不是插入结点，如果是插入结点的话，原来的二叉树就不满足红黑树的要求了，因此cur是因为下面结点更新颜色而导致变红的（原来是黑色）。

处理方法:将原来红黑树以g为中心向右旋转，然后进行颜色更新（p变黑，g变红）。

b、当叔叔结点不存在的情况：其中cur为p的左节点，并且p为g的左节点。这里的cur和上面不同的是，cur可以为当前插入结点，处理方法和上面一样。

c、当cur结点为parent结点的右结点，并且p为g的左节点。这里的cur不是插入结点原因和a一样。处理方法：首先要以parent为中心向左旋转，然后再以g为中心向右旋转，最后将cur变为黑色，然后g变为红色。

d、当叔叔结点不存在的情况：c结点为p结点的右结点，并且p为g的左节点。处理方式和方案c一样。

另外当p为g的右节点时，和上面一样仍然有四种情况，处理方式：在旋转过程中方向相反即可。