雅乐网

红黑树也是一种平衡二叉树，但并不像AVL那样严格。红黑树有一些等价的表述，其中比较流行的就是给结点染上红色或黑色。下面是一棵红黑树。

一棵红黑树示例，图片来自维基百科

红黑树满足4条性质：

1. 根结点是黑色的（如果不是空树）

2. 外部结点是黑色的（外部结点是把NULL指针看做指向一个代表NULL的结点）

3. 红色结点只能有黑色的孩子（从树根到外部结点路径上不会有连续的红结点）

4. 外部结点到树根的路径中包含相同数目的黑色结点。

红黑树 = 4阶B-树

红黑树的4个性质

先来分析红黑树的性质。

性质1：树根为黑色。

性质2：外部结点是黑色的。

看性质3：红色结点只有黑色孩子。即从根到叶路径中不会有连续的2个红结点。

性质3的逆否命题是：如果一个结点是红色结点，它不会有红色父亲。那么它只可能有黑色父亲，结合性质1：树根为黑，有红结点必有父亲。所以，红结点必有黑色父亲。

性质4：外部结点到树根的路径中包含相同数目的黑色结点。这也叫做红黑树的黑高度。这可以让人想到B-树，B-树的叶节点都在同一层次。如果只看黑结点，这和B-树非常符合。

B树的超级节点

再回忆一下B-树的超级节点

通过上面性质的分析，红色结点必有黑父亲，而每条路径中黑结点数目一致。如果把所有的红结点都和它的黑父亲结合，形成超级结点，就得到了所有叶结点深度一致的B-树。所有情况一共4种：

1. 左右孩子都为黑 这时候没有红孩子可以提升 超级节点只有黑色结点

2. 左孩子为红

3. 右孩子为红

4. 左右孩子都为红

下面是一个示例

可以看出转换后的超级结点，最多3个元素，其中黑结点在中间，红结点在两边。

也有可能一个黑结点一个红结点，或者只有一个黑结点。

最少有1个结点，2个分支；最多3个结点，4个分支，这正好就是4阶B-树。

高度

由于B树高度为O(logn)，红黑树最多也只是对应B树的2倍，因此其高度也是O(logn)。

红黑树的平衡也可以这样看：从根节点到外部结点的路径中黑结点数目相等。而红结点不能连续，最多也只是与黑结点相同，所以不同的路径结点个数不会相差很多。

插入

插入时先按照一般搜索二叉树的方法，插入元素作为叶子，并设置为红色。

插入的新结点记为x ，它的父节点记为p ，它的祖父结点记为g，祖父节点的另一个孩子节点记为u（Uncle）。

从拓扑结构来说，g、p、x的连接有4种情况：左左，左右，右左，右右。

右右、右左 可以看做 左左、左右的对称情况，因此下面分析左左和左右情况。

但是修复双红缺陷时，却是从颜色来考虑的。

1. p黑

当插入结点的父节点p是黑结点时，由于新插入x为红色，红黑树的4条性质均未破坏。

当p为红色时，由于出现了连续的红结点，红黑树的性质不再满足，这称为双红缺陷。

此时根据黑结点的另一个结点u是红或黑，可以分为2种情况（关系到对应B-树超级结点是否上溢）：

2.1 p红u黑

此时提升变换后的B树超级结点个数满足要求，只是顺序不是红黑红，在B-树看来只需要改变颜色即可。还原后，红黑树的拓扑结构和颜色都会发生变化。

下面再给出左右的例子：

因此，这种情况不管拓扑结构是4种中的哪种，只需要把x p g按中序遍历顺序，把4个子树也按照中序遍历顺序，用3+4重构的方法连接起来即可。

2.2 p红u红

这种情况合并超级结点后有4个结点，5个分支，B-树发生上溢。

和上一个情况相反，这里B树发送了拓扑变化（分裂），但对应红黑树只是改变了颜色，拓扑结构没有变化。

g结点变为红色以后，相当于g的父节点插入了一个红结点，这时g的父节点再次面临与 p结点插入后出现的问题相同的问题，这相当于把问题节点p提高了2层。这种问题有时可以一直持续到树根。

下面是左右结构

删除

先使用二叉搜索树的 removeAt(x) 来删除x，并得到x的替代结点r 。

回忆一下removeAt(x)函数面临的3种情况：

x没有左孩子时，用右孩子r代替x

x没有右孩子时，用左孩子r代替x

x既有左孩子，又有右孩子，则取x的中序后继r=succ(x)，交换x和r的值，再删除r。r又可以看做要删的x 。这时x没有左孩子，用右孩子r代替x。

之后，removeAt函数返回实际被删除结点的替代者，_hot指向其父亲结点。

不管哪种情况，在删除时，x由它的一个孩子r代替，而另一个孩子（记为w）为空。

删除后，红黑树的性质1和2仍然满足，但3和4就不一定了。这要取决于x和r的颜色。

当x和r有一个是红结点时，T1和T2的相对于x的黑深度原先是1，之后我们只要把r染为黑色，就可以保持黑深度不变，从而红黑树的性质得以满足。

当x和r都是黑色的时候，删除x导致T4黑高度降低，我们称出现了双黑缺陷。此时考虑x的父节点p，x的兄弟节点s ，以及s的某个孩子t。

之所以考虑这些节点的颜色，是和B树删除时下溢的 情况类似的：

要删除结点x，则B-树中超级节点x发生下溢。而s如果为黑，则x有兄弟结点；若s有一个t为红，则s超级节点至少2个结点，可以借出；若s的孩子都为黑，则s不可以借出。若s为红，对应其他情况。

1. s为黑，t为红

结果是t、s、p和T1、T2、T3、T4进行了一次3+4重构。若t，s，p按照中序顺序命名为a，b，c，则a、c染黑，s为原先p的颜色。

2. s为黑 s的两个孩子均为黑

这时候s只有一个结点，不可以借给x删除后的结点，此时需要合并。要从p所属的超级节点中拿出一个作为粘合剂。

这时要讨论p的颜色。如果p是红色，则p所在的超级节点有多余1个结点，合并后下溢不会上升。如果p为黑色，p所在超级节点只有1个结点，会导致下溢向上传播。

2.1 s为黑 s的两个孩子均为黑 p为红

由于p是红色，p的左右至少1个黑色结点，因此p下降后，原先p所在的结点不会继续下溢。

2.2 s为黑 s的两个孩子均为黑 p为黑

这种情况基本步骤和2.1相同，只不过完成后p所在节点会继续下溢。这可以看做p结点的父节点被删除。

 3. s为红

这时的思路是转化为前两种情况

进行旋转后，x的兄弟结点t是黑色，故可以转入上两种情况。因p为红色，故不会转入2.2

总结

参考资料

数据结构（C++语言版）（第3版）/邓俊辉