红黑树的删除_红黑树揭秘

红黑树可能是一般数据结构书中代码逻辑最复杂的结构。多数材料都只是讲构建红黑树的步骤，并没有探究红黑树背后的思想。本文通过对红黑树背后逻辑的梳理，提供给大家一种理解红黑树的方法。首先我们先给出红黑树的定义，红黑树是棵空树或者具有以下性质的二叉搜索树：

结点只能是红色或者黑色。
根结点必须是黑色。
所有NULL结点都是黑色。所有NULL结点称为叶子结点，且认为颜色为黑。
一条路径上不能出现相邻的两个红色结点。
在任何递归子树内，根结点到叶子结点的所有路径上包含的相同数目的黑色结点。

前言

我们所见到的文字、数学公式以及代码等等都是符号。符号本身是种抽象，它的解释需要依赖大家共同的约定，此外好的符号容易引出直觉感受。比如 + 和 -，我们会习惯感受到增加和减少。对符号的解释依赖阅读者的个人经验，也体现出个人的思考深度。

在这儿我以为例来给出一种解释。此算式是等比数列求和，它的结果是。对于学过高中数学的同学来说非常简单。那我们换另外一个角度来看这个算式，现在有进制的数字,共位,其对应的十进制数字是。将乘以进制中的最大个位数, 此时中的每个就都变成了, 然后对其加，就会导致一连串的进位，变成,此时表示的十进制数是。整理下就是。

如果大家觉得这个不直观，那我们就取，此时的结果就显而易见。, 乘以后加，结果是。

举这个例子只是想说明符号的解释并不唯一，但是符合大家直觉的解释会简化大脑的思考量和加快反应速度，单纯的记忆只会增加大脑的负担。对于红黑树而言，同样如此，背诵其步骤无益于提升自己的思维，反而更加僵化。

红黑树

AVL树是一种平衡二叉树，但是在频繁插入和删除时，维护左右子数的高度平衡会频繁引起rebalance。为了减少rebalance的次数，可以在增加结点容量或者平衡(高度差)的定义上做考虑。比如说3叉树、4叉树上做插入和删除引起的rebalance就比2叉树平衡的次数要少的多，但是它们要经常分裂和合并结点。

红黑树对平衡二叉树的改进是往平衡定义这方向思考的，为结点增加了颜色也就增加了新的状态信息。那么存在一种对红黑树中红结点和黑结点的颜色比较容易的解释吗？答案是存在的。如果我们把红结点看成与其父结点共同组成一个结点(Algorithms, 4th edition, by Robert Sedgewick), 那么红色增大了这个结点的元素数量。那我们可以重新使用该观点来描述下红黑树：

红黑树是一种使用了2叉树结构来表示的平衡2-3-4叉搜索树，其中3叉和4叉结点需要如下表示。3叉有两种，4叉只有一种表示。此表示和红黑树的4个特性的描述是可以对应起来的。

整棵红黑树就是用这种方法表示的平衡2-3-4叉搜索树。

平衡树的方法：左旋右旋

作为搜索树必须保证元素间的相对顺序，不管是AVL还是红黑树为了实现平衡都依赖了两个操作——左旋和右旋。

左旋、右旋操作示意图

左旋和右旋如果不好区分的话，可以把执行操作的结点想象成扳手，扳手从左上角往下用力就左旋，从右上角往下用力就是右旋。左旋和右旋操作不会破坏搜索树的特性，左子树元素都比结点元素小，右子树元素都比结点元素大。

红黑树插入元素

红黑树的插入新元素时，为了不增加额外的高度，都是会把新插入的结点当成红结点来处理的。如果此时该结点插入时的父结点是黑色的，那就直接插入即可。此时并没有增加树高，而是将原有的2叉结点变成了3叉结点。

因为红黑树中还有3叉结点和4叉结点，此时插入的新的红结点，可能将它们变成不规范的4叉结点以及5叉结点。不规范的4叉结点，则可以通过左旋右旋调整成规范的4叉结点，参考下图(3)(4),对于(3)先将其变成(4)再处理。对于5叉结点，必须将其拆分成一个2叉结点(为了不增加树高，此2叉结点标记为红色，方便与其父结点组合)，该2叉结点的子结点一个3叉和一个2叉。具体过程参考下图(1)(2)。

为了判断插入时的父结点是不是4叉结点，需要判断父结点的相邻结点是不是红色。如果父结点是左结点，就要检测右结点是不是红色。如果父结点是右结点，则需要检测左结点的颜色。这两个方向是对称，所以在此我们只讨论父结点是左结点的情况。p：parent， pp: parent of parent。

将待调整结点连上3叉和4叉结点的处理办法

红黑树删除元素

红黑树的删除的过程和二叉搜索树删除结点类似，都需要先找到待删除结点：如果待删除结点至少有一子结点为空，则删除此结点；如果待删除结点左右子结点都存在，找中序遍历中该结点的后继结点做替换，删除该后继结点。

待我们确定了该删除的结点后：如果该结点是红结点，因为删除此结点不影响树高，则可以直接删除。如果该结点是黑结点，其左右中非空的那个子结点是红结点，则可以将该子结点改成黑色，此时相当于把叶子的3叉结点改成了叶子的2叉结点，也不影响树高，则直接删除该结点。

除了以上两种情况外，直接删除该需要调整的黑结点会导致此结点为根的子树高度减1，不能维持平衡。故需要额外做调整，调整的基本方案：如果能从兄弟结点借来元素，就从兄弟处借来元素；如果兄弟元素数量不够借，则从父结点(3叉或4叉结点)拆分一个元素下来；如果父结点(2叉)不够拆分，则将该结点变成红色，组成3叉结点，作为新的待调整结点。

由于红黑树是平衡树，除根结点和叶子结点外，中间结点必然存在兄弟结点。由于从兄弟结点处借元素需要知道是左兄弟还是右兄弟，此时需要判断待调整结点是左结点还是右结点。左结点需要取右兄弟，右结点需要取左兄弟。因为对称关系，在下文描述时我只描述待调整结点是其父结点的左子结点的情况。

首先需要先将右兄弟放置到方便取到的地方，如果不方便取右兄弟，则需要按照下图进行调整。p: parent, s: sibling，x是待处理结点，以x为根的子树高度比s为根的子树少1。

如果兄弟结点不是父结点(此处指直接的2叉父结点)的子结点时，需要调整

那接下来，我们先讨论兄弟结点是2叉结点，没有额外元素借给待调整结点的情况。

兄弟结点s是2叉结点时，如果父结点是3叉或4叉，

则可以拆分下元素补足高度，否则必须要继续调整

如果兄弟结点是3叉或4叉，此时待调整结点可以从兄弟结点处借到元素(只给兄弟结点留一个元素)，维持原有树高，说明如下图：

兄弟结点是3叉或4叉时，可从兄弟结点处借到元素重新平衡。

以上是红黑树的插入和删除操作的逻辑性解释。需要注意的是红黑树的根结点必须是黑色。调整结束后记得维持此特性。

插入删除中的循环不变量

循环不变量(loop invariant)是种属性，它对保证算法的正确性有着至关重要的作用。它是在循环的每个迭代开始和结束时都必须保证的内容。对于红黑树的插入和删除，维持了如下三个循环不变量：

每个结点都是符合规定的2叉，3叉或4叉结点。
以每个结点为根的子树的左右子树高度都一样(黑结点路径长度)。
保证了搜索树的特性，每个结点的左子树元素都比结点元素小，右子树元素都比结点元素大。

总结

红黑树是一种以2叉树表示的平衡2-3-4叉搜索树，只不过3叉和4叉的表示形式被做了限定。插入和删除元素过程中，遵循必要的循环不变量保证了每次操作后依旧是棵红黑树。