红黑树(RBTree)

灰太狼 2023-06-22 03:21 6阅读 0赞

## 红黑树(RBTree) ##

> **红黑树：AVL树的变种，具有如下4个条件：**  
>   1、每一个结点是红色或黑色  
>   **2、根结点是黑色。**  
>   **`3、如果一个节点是红色，那么它的两个子节点必须是黑色。（不能出现两个相连的红色结点）`**  
>   **`4、从任意一个结点到一个null引用的每一条路径必须包括相同数目的黑色结点。`**

由于红黑树的特点得出结论：红黑树的高度最多是2log(N+1)，因此其查找操作的时间复杂度为对数操作。  
  在将新结点作为叶结点插入树中，**默认该结点为红色**。如果当前节点的父节点是黑色，那么直接插入完成；而若当前节点的父节点是红色，由于违反条件3，因此需要进行调色或旋转操作。

> **为什么该结点默认为红色而不是黑色？**

因为红黑树需要满足任意一个结点到一个null引用的每一条路径必须包括相同数目的黑色结点(条件4)，若新结点为黑色，那么会导致该路径上的黑色结点数目+1，不符合红黑树的条件。

> **为什么要使用红黑树？**

相比于二叉搜索树来讲，红黑树保证了树的平衡性，降低了树的高度，提高了树的查找性能，防止由于插入顺序(升/降序插入)导致二叉搜索树成为一条链表的情况。  
  相比于AVL树来讲，红黑树的旋转操作相对较少，操作相对简单。

> **红黑树的应用？**

在Java中，红黑树用于TreeMap，TreeSet中，以及当阈值达到8时，HashMap中的链表也会转换为红黑树来存储元素。

--------------------

说了这么多，接下来看一看红黑树的具体插入操作吧。由于二叉树是一个左右对称的结构，左右两边的操作大体相同，下面以左半边为例，右半边只给出代码即可。  
  当新结点插入红黑树时，由于红黑树也是二叉搜索树，因此根据大小找到其位置进行插入。此时会遇到两种情况。  
  1、该结点的父节点是黑色，直接插入即可，不需要做任何调整。  
  2、该节点的**父节点是红色**，由于红色结点的子节点必须是黑色，并且该新结点默认是红色，因此必须做出调色或旋转，而当父节点是红色时，又分了三种情况。  
   在详细看三种情况前，先解释一下当前节点，父节点，叔结点，祖父节点的关系。如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]  
  (小声bb一下，PowerPoint作图是真的舒服)  
   `在分析这部分结构时，一定要将当前节点及其父节点，祖父节点，叔结点抽象出来，不是说这些节点的下面没有其他子树了，而是只将这四个结点抽象出来！！！`  
   ①当前节点的**叔结点存在且为红色**。  
    这种情况最易解决，将父节点和叔结点变为黑色，祖父节点变为红色即可，依旧保证了从祖父节点往下的所有路径中的黑结点的个数不变，同时也满足红黑树的其他性质，具体图示如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 1]  
   ②当前节点的叔结点为黑色或不存在&&当前节点是其父节点的`左子节点`&&父节点是其祖父节点的`左子节点`。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 2]  
   对于这种情况来讲，肯定不能直接通过简单的调色就可以解决问题，因为如果将父节点调为黑色，祖父节点调为红色。以叔结点存在的情况举例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 3]  
   **`这里一定需要注意`**：由于是只对这四个结点进行的抽象，对于祖父节点来讲，原本祖父节点的左路径中(包括祖父节点)的黑色结点数为1，而右路径中的黑色结点数为2。这里看似并不符合红黑树，但**这是一种抽象，只抽象这四个结点，在当前节点/父节点的子树中肯定还有其他黑色结点存在使得这棵树满足红黑树的特点。**  
   这里又有一个疑问：当前节点不是新插入的叶结点，怎么可能还有其他子树？一定要记得，这里所讨论的情况并不单指才插入的情况，若某个节点的祖父节点被修改为红色，这样可能会导致祖父节点与祖父节点的父节点产生**两个红色结点相连**的情况。  
   上面的看不懂都无所谓，只需要记住下面这一段话：**`对于抽象出来的这四棵树，无论是采用调色还是自旋的方式，在调色/自旋前每个结点的状态是什么样，在调色/自旋后每个状态就必须是什么样。`**  
   解释一下这句话：调色/自旋前，对于祖父节点来讲，其左路径上黑色结点个数为1，而右路径黑色结点个数为2。只要在调色/自旋后，对于祖父节点，其做路径上黑色结点个数为1，其右路径黑色结点为2(与执行动作前一致)，那么就是正确的操作，该树就还是红黑树。

解释完这些再来看这种情况，当只进行调色操作后，对于祖父节点来讲，其左路径黑结点个数为1与调色前一样，而其右路径黑结点个数为1与调色前的2不一样，因此该树不再是一颗红黑树，也就说明，这种情况下单单调色是不能解决问题的，因此对于这种情况，需要采用单旋的方式。  
   **单旋**：将**祖父节点进行右单旋转**，再将其父节点作为新的祖父节点并染为黑色，而原本的祖父节点作为原本父节点的右子节点并染色为红色。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 4]  
   经过如上的单旋操作，操作结束后的树就满足了红黑树的所有要求（对于祖父节点来讲，依旧是左路径黑结点个数为1，右路径黑结点个数为2）

③当前节点的叔结点为黑色或不存在&&当前节点是其父节点的`右子节点`&&父节点是其祖父节点的`左子节点`。  
   这是最难的一种情况，进行单旋+调色依旧不能满足红黑树的性质。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 5]  
   由于此时的原祖父节点又和当前节点形成了两个红色结点相连，不符合红黑树的特点，因此采用双旋的策略。

**双旋**：先将原本的父节点进行左单旋转，再将原本的祖父节点进行右单旋转，最终将原本的父节点染为红色，原本的祖父节点染为黑色即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 6]  
   对父节点进行左旋操作后的结构就和②的情况一样了，再对其祖父节点进行右旋操作即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 7]

--------------------

自此，父节点是祖父节点的左子节点的三种情况讨论结束，剩下就是父节点是祖父节点的右子节点了，与左边情况完全相同，就不一一赘述。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191213174902694.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191213180818482.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191213175320175.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191213181237235.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/201912131906145.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191213184502472.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191213190315449.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20191213190741190.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA==,size_16,color_FFFFFF,t_70