红黑树详解

一、定义：

 R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

红黑树上每个结点内含五个域，color，key，left，right，p。如果相应的指针域没有，则设为NIL。

红黑树示意图如下：

图a

二、性质：

(1) 每个结点要么是红的要么是黑的；

(2) 根结点是黑的；

(3) 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的；

(4) 如果一个结点是红的，那么它的两个儿子都是黑的；

(5) 对于任意结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

注意：

1）特性(3)中的叶子节点，是只为空(NIL或null)的节点。

2) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

三、红黑树的操作：左旋、右旋、查询、插入、插入修复、删除、删除修复

红黑树可视化的网站：（https://www.cs.usfca.edu/~galles/visualization/RedBlack.html）

1、左旋：

图b

2、右旋：

图c

不同于顺时针跟逆时针变换这种方式去记忆，上面两个动态图特别方便记忆跟理解：

（1）左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点；

（2）而右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。

（3）即左旋就是往左变换，右旋就是往右变换。不管是左旋还是右旋，旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。

​　　举个例子，像上图是否平衡二叉树的图里面，左图在没插入前”19“节点前，该树还是平衡二叉树，但是在插入”19“后，导致了”15“的左右子树失去了”平衡“，所以此时可以将”15“节点进行左旋，让”15“自身把节点出让给”17“作为”17“的左树，使得”17“节点左右子树平衡，而”15“节点没有子树，左右也平衡了。如下图：

图d

自己尝试旋转以下示例

示例1 示例2

3、查询：类似于二分查找

4、插入：

4.1、插入步骤：将一个节点插入到红黑树中，需要执行3个步骤：

第一步: 将红黑树当作一颗二叉查找树，将节点插入。

第二步：将插入的节点着色为"红色"。

第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

要真正理解红黑树的插入，还得先理解二叉查找树的插入，如果要在二叉查找树中插入一个结点，首先要查找到结点要插入的位置，然后进行插入。假设插入的结点为z的话，插入的伪代码如下：

二叉树插入伪代码

假设插入的结点为z，红黑树的插入伪代码具体如下所示：

红黑树插入伪代码 红黑树插入修复伪代码

4.2、插入修复：

根据被插入节点的父节点的情况，分为三种情况来处理：

（1） 情况说明：被插入的节点是根节点。

    处理方法：直接把此节点涂为黑色。

（2） 情况说明：被插入的节点的父节点是黑色。

    处理方法：什么也不需要做。节点被插入后，仍然是红黑树。

（3） 情况说明：被插入的节点的父节点是红色。

        3.1）情况1：如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色；

        3.2）情况2：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子；

        3.3）情况3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子。

插入修复情况1：如果当前结点的父结点是红色的，且祖父结点的另一个子结点（叔叔结点）是红色

解决对策：将当前结点的父结点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结点，从新的当前节点重新开始算法。此时，插入修复情况1 就转换成了 插入修复情况2

此时父结点的父结点一定存在，否则插入前就已不是红黑树。与此同时，又分为父结点是祖父结点的左孩子还是右孩子，根据对称性，我们只要解开一个方向就可以了。这里只考虑父结点为祖父左孩子的情况。如下图所示（勘误：图中15节点应改为13，特此说明，下同）

插入情况1修复前 插入情况1修复后

插入修复情况2：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子。

解决对策：当前结点的父结点作为新的当前结点，以新当前结点为支点左旋。此时，插入修复情况2 就转换成了 插入修复情况3

插入情况2修复前 插入情况2修复后

插入修复情况3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子。

解决对策：父结点变为黑色，祖父结点变为红色，再以祖父结点为支点右旋。最后，把根结点涂为黑色，整颗红黑树便重新恢复了平衡。

插入情况3修复前 插入情况3修复后

经过上面情况3、情况4、情况5等3种插入修复情况的操作示意图，可以看出，后面的情况4、情况5都是针对情况3插入节点4以后，进行的一系列插入修复情况操作，不过，指向当前节点N指针一直在变化。所以，可以认为：整个下来，情况3、4、5就是一个完整的插入修复情况的操作流程。

5、删除：

5.1、删除：

补充说明下二叉树结点删除的几种情况，待删除的节点按照儿子的个数可以分为三种：

1、没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。

2、只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。

3、有两个儿子。这是最麻烦的情况，因为你删除节点之后，还要保证满足搜索二叉树的结构。其实也比较容易，我们可以选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置，就可以保证结构的不变。当然，你要记得调整子树，毕竟又出现了节点删除。习惯上大家选择左儿子中的最大元素，其实选择右儿子的最小元素也一样，没有任何差别，只是人们习惯从左向右。这里咱们也选择左儿子的最大元素，将它放到待删结点的位置。左儿子的最大元素其实很好找，只要顺着左儿子不断的去搜索右子树就可以了，直到找到一个没有右子树的结点。那就是最大的了。

二叉查找树的删除代码如下所示：

二叉树删除伪代码

红黑树的删除和删除修复伪代码：

红黑树删除伪代码 红黑树删除修复伪代码

“上面的修复情况看起来有些复杂，下面我们用一个分析技巧：我们从被删节点后来顶替它的那个节点开始调整，并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢，我们不是把红黑树的节点加上除红与黑的另一种颜色，这里只是一种假设，我们认为我们当前指向它，因此空有额外一种黑色，可以认为它的黑色是从它的父节点被删除后继承给它的，它现在可以容纳两种颜色，如果它原来是红色，那么现在是红+黑，如果原来是黑色，那么它现在的颜色是黑+黑。有了这重额外的黑色，原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了，做法还是尽量向根移动和穷举所有可能性。"--saturnman。

5.2、删除修复：分为以下几种情况

（1） 情况说明：当前节点是红+黑色。

    处理方法：直接把当前节点染成黑色，结束此时红黑树性质全部恢复。

（2） 情况说明：当前节点是黑+黑且是根节点。

    处理方法：什么都不做，结束。

（3） 情况说明：x是“黑+黑”节点，且x不是根。

        3.1）情况1：当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)；

        3.2）情况2：当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色；

        3.3）情况3：当前节点颜色是黑+黑，兄弟节点是黑色，兄弟的左子是红色，右子是黑色；

        3.4）情况4：当前节点颜色是黑-黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。

删除修复情况1：当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。

解决对策：把父节点染成红色，把兄弟结点染成黑色，之后重新进入算法（我们只讨论当前节点是其父节点左孩子时的情况）。此变换后原红黑树性质5不变，而把问题转化为兄弟节点为黑色的情况(注：变化前，原本就未违反性质5，只是为了把问题转化为兄弟节点为黑色的情况)。

删除情况1修复前 删除情况1修复后

删除修复情况2：当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色。

解决对策：把当前节点和兄弟节点中抽取一重黑色追加到父节点上，把父节点当成新的当前节点，重新进入算法。

删除修复情况2修复前 删除修复情况2修复后

删除修复情况3：当前节点颜色是黑+黑，兄弟节点是黑色，兄弟的左子是红色，右子是黑色。

解决对策：把兄弟结点染红，兄弟左子节点染黑，之后再在兄弟节点为支点解右旋，之后重新进入算法。此是把当前的情况转化为情况4。

删除修复情况3修复前 删除修复情况3修复后

删除修复情况4：当前节点颜色是黑-黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。

解决对策：把兄弟节点染成当前节点父节点的颜色，把当前节点父节点染成黑色，兄弟节点右子染成黑色，之后以当前节点的父节点为支点进行左旋，此时算法结束，红黑树所有性质调整正确。

删除修复情况4修复前 删除修复情况4修复后

上述删除修复的情况1~4都只是树的局部，并非树的整体全部，且删除修复情况3、4在经过上面的调整后，调整还没结束（还得继续调整直至重新恢复平衡，只是图并没有画出来）