彻底弄懂红黑树_红黑树 红节点只有一个子节点

彻底弄懂红黑树

概述

我们知道二叉搜索树在一些特定的情况下会退化成链表，比如插入有序的数据的时候。为了解决这个问题，可以使用AVL树。AVL树是一个平衡二叉树，其左右子节点的高度差不大于1，这样子的话，就可以尽量地减少树的高度，以得到稳定的查询效率，但是为了维持平衡二叉树，需要频繁地进行树的左右旋转。那么是否有一种数据结构能够兼顾防止树的退化和查询效率呢，有，它就是红黑树。
我们知道红黑树有如下特征：

• 每个节点要么是红色，要么是黑色
• 根节点为黑色
• 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
• 如果一个节点是红色，那么它的子节点一定是黑色。也就是不可能出现红色节点相连。
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。也就是黑色平衡。

那么这些特征是如何推导出来的？

从2-3-4树开始讲起

要讲清楚红黑树，要从2-3-4树开始讲起。首先我们需要知道红黑树等价于2-3-4树。
2-3-4树是一颗满二叉树，它拥有3种节点。

• 2节点：拥有1个值，2个子节点
• 3节点：拥有2个值，3个子节点
• 4节点：拥有3个值，4个子节点

2-3-4树如下图所示，多个方块连在一起代表的是一个节点。例如，2和4其实是在一个节点内，这个节点是3节点，拥有2个值和3个子节点。

2-3-4树跟红黑树有一些对应的结构，需要进行记忆。

• 2节点转化为红黑树的1个黑色节点
• 3节点转化为红黑树的1黑1红两个节点，有两种结构，都是上黑下红。
• 4节点转化为红黑树的1黑2红三个节点

现在我们插入1到5来模拟下，2-3-4树以及红黑树分别的样子。

1. 插入1，作为树的根节点，对应的红黑树是一个节点，颜色为黑色。
   

2. 插入2，2比1大，所以2为1的右子树。
   

3. 插入3
   

4. 插入4
   

5. 插入5
   

我们可以观察出规律，虽然节点在不断地增加，但是其实也就3种情况，也就是下图所示，那红黑树的5个特征也不难从这些变换中总结出来。无论2-3-4树的2节点、3节点还是4节点，在转换成红黑树对应结构时都有一个黑色节点，而2-3-4树又是满二叉树，所以不能推导出，红黑树上黑色平衡的特征。

插入操作

红黑树的插入操作分为两步，第一步插入节点，跟二叉搜索树的插入节点是相同的；第二步，插入后的调整操作，困难点在于插入后的调整，使插入后的红黑树依旧是一个满足特征的红黑树。
下图是插入操作的思维导图。

下面我们模拟插入操作，左侧为对应的2-3-4树，右侧为红黑树。红黑树新增的节点都为红色。

1. 插入1，当前树为空树，插入节点为根节点，因为是根节点所需需要设置颜色为黑色。
   

2. 插入2，因为2大于1，所以2作为1的右节点，插入节点的父亲为黑色，插入后不违背红黑树的特征，所以不需要调整。
   

3. 插入3，因为3大于2，所以3作为2的右子节点插入，此时我们发现2和3节点都是红色，这个是违背红黑树的特征的，所以需要进行调整，我们将插入节点的父亲便成黑色，插入节点的爷爷节点变成红色，并将爷爷节点进行左旋，便可以得到新的红黑树。
   

4. 插入4，因为4大于3，所以【4】作为【3】的右节点。此时【3】和【4】相连，且都是红色节点，不符合红黑树的特征，所以要进行调整。对于2-3-4树，一个节点最多拥有3个值，如果节点已经超过了3个值，还要继续加入，就要分裂。
   
   
   我们观察左边的2-3-4树，将其转换成红黑树，不正是我们调整的最终目标吗。如下图所示，【1】和【2】节点都是2节点，将会被转换成黑色的节点。【34】节点是3节点，转换的结构是上黑下红，最终如右图所示。正是满足要求的红黑树。
   
   要将左边的树调整为右边的树，正是当前插入节点的父节点为红色，且叔叔节点也为红色，所以将父亲节点和叔叔节点都变成黑色，完成了调整。
   

5. 插入5，因为5大于4，所以作为4节点的右子节点，此时4和5节点都是红色，需要调整。如下图所示：
   
   将左边的2-3-4树转换成红黑树，可以得到调整后的结果。1和2都是2节点，设置为黑色。【345】是4节点，中间的值在上面为黑色节点，左右的值作为左右子节点，为红色。
   
   这里得出调整规则：
   

6. 插入6，6大于5，作为5的右子节点。对于2-3-4树来说，因为【345】是4节点，再加入一个6节点，它就必须要分裂。将【345】中的4分裂出去，4会和上层的2合并，得到最终的结果。对于红黑树，5和6节点都是红色，不满足红黑树规定，所以需要调整。
   
   
   将2-3-4树转换成红黑树，得到了红黑树调整的最后结果。【24】和【56】节点是3节点，转变为上黑下红的结构，【1】和【3】是2节点，变为黑色。
   
   所以我们得出调整规律，当插入节点的父亲节点为红色，且叔叔节点也为红色时，将叔叔节点和父亲节点都变为黑色，将爷爷节点变成红色。并将爷爷节点改为新的调整节点。继续往上调整。这里因为【4】节点的父亲为黑色，所以调整完成。之所以要网上调整，可以通过观察2-3-4树得出结论，因为分裂出去的【4】节点又跟【2】节点合并了，所以必然会导致树结构的改变。
   

删除操作

删除操作比红黑树的插入操作逻辑更加复杂一些。思维导图如下所示：

首先需要明白前继节点和后续节点的概念，前继节点和后继节点都是针对某个节点而言的。

• 前继节点：某个节点的前继节点是小于此节点的最大节点。
• 后继节点：某个节点的后继节点就是大于此节点的最小节点。

如下图所示，针对于节点【2】而言，前继节点是节点【1】，后继节点是节点【3】：

红黑树中对于节点的删除操作操作，都可以转换为删除其后继节点，或者前继节点。
红黑树上的删除，若删除的是上层的节点，例如上图中的节点【2】，因为删除了黑色，导致了黑色失衡，所以肯定要进行调整，感觉情况很多，是不是很麻烦。有一种办法，就是将删除节点这个操作转变为删除后继节点（或前继节点，后面都以后继节点论述，但要知道后继节点和前继节点都是可以的），这样子，删除操作不就变成了对于红黑树上叶子节点或者叶子节点上一层的操作了吗（对应到2-3-4树上，就是2-3-4树的叶子节点）。

我们将后继节点的值赋予删除节点，将后继节点删除。这棵树依旧保持了有序，只不过此时需要做一些调整。

所以红黑树上节点的删除都可以转移为删除树上的最底层的节点，对应于2-3-4树的叶子节点，因为2-3-4树的叶子节点分别有可能是2节点、3节点和4节点。所以我们知道，可能会出现3种情况。如下图所示：

• 第一种情况，删除节点是2-3-4树的4节点，以上图的【789】节点为例，对应到红黑树上的结构是黑色【8】节点在上，红色的【7】节点和【9】节点在下面。若删除红色节点【7】或【9】，直接删除即可，因为没有影响红黑树的特征。若删除黑色【8】节点，因为有左右子节点，所以可以转换为删除红色【9】节点。将【9】节点的值赋予节点【8】，并将红色节点9删除。
  

• 第二种情况，删除2-3-4树的3节点，以【3|3.5】节点为例，对应到红黑树就是上面黑色的【3】节点和下面红色的【3.5】节点。若删除红色的【3.5】节点，直接删除即可，若删除黑色的【3】节点，可以用【3.5】节点去替代【3】节点，因为删除黑色影响了黑色平衡，所以需要用【3.5】节点需要变成黑色。
  

我们发现了一个规律，删除红色节点都是可以直接删除的，因为删除红色节点不会影响红黑树的平衡。
若删除拥有子节点的节点，可以用子节点来替代删除节点，依旧可以保持黑色平衡。

• 第三种情况，删除2-3-4树的2节点，以节点【1】为例，这种情况是比较复杂的，因为它没有子节点来代替删除节点的位置，那么是否可以调整父亲节点和兄弟节点来使重新平衡呢。所以根据兄弟节点的类型，又有三种子情况。

  • 兄弟节点是4节点，意味着兄弟节点有2个子节点，所以可以让父亲节点代替删除节点的位置，兄弟节点代替父亲节点的位置，兄弟节点的子节点代替兄弟节点的位置。如下图所示，删除节点【3】，父亲节点【4】进行一个左旋操作，并将父亲节点的颜色变为黑色，兄弟节点变为父亲节点的颜色，兄弟节点的右子节点变成黑色：
    

  • 兄弟节点是3节点，意味着兄弟节点有1个子节点，依旧可以让父亲节点代替删除节点的位置，兄弟节点代替父亲节点的位置，兄弟节点的子节点代替兄弟节点的位置，使最终删除完节点后，依旧是平衡的。
    

  • 兄弟节点是2节点，这种情况比较复杂，意味着不能从父亲节点和兄弟节点进行调整，进而使树再平衡。既然不能借，那能不能让兄弟节点也变成红色，这样子对于父亲节点的两个子树来说，不也是黑色平衡的吗。然后再尝试将父亲节点变成黑色。如果父亲节点使红色，变成黑色之后，整颗树又再平衡了。但是如果父亲节点使红色呢？那尝试将叔叔节点也变成红色，尝试将曾祖节点从红色变成黑色，如果曾祖节点本来就使黑色，再往上递归。思想就是，我少了一个黑色，你们也少一个黑色，大家就平衡了。如下图所示：
    

总结

至此，红黑树的推导过程介绍得差不多了，我们知道了红黑树是等价于2-3-4树的，所以红黑树拥有了2-3-4树的特征，但是又使用了二叉树的操作。知道了红黑树的原理之后，下一篇文章，我们介绍如何编写红黑树的代码，大家也可以先看看Java种红黑树的实现TreeMap，最后我们来张动图来演示红黑树的新增和删除。