红黑树结构及算法实现

以你之姓@ 2023-07-10 15:51 30阅读 0赞

# 红黑树结构 #

红黑数(Red-black tree)是一种自动平衡的二叉查找树，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70]  
红黑数首先需要满足的条件是一棵二叉查找树，在此基础上增加其自己的规则。

#### 二叉查找树的规则 ####

1.  若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
2.  若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
3.  任意节点的左、右子树也分别为二叉查找树
4.  没有键值相等的节点

#### 红黑树的规则 ####

1.  节点是红色或黑色。
2.  根节点是黑色。
3.  每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
4.  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树与AVL树更加通用，因为AVL查找快但插入慢，红黑树查找插入都挺好。

# 红黑树算法实现 #

#### 旋转算法 ####

注意：A、B、C都是可能有子节点的。

**左旋**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 1]  
**右旋**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 2]

#### 插入算法 ####

总体的步骤如下：

1.  第一步: 将红黑树当作一颗二叉查找树，将节点插入。
2.  第二步：将插入的节点着色为"红色"。
3.  **第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树**。

插入节点为红色的原因是：将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。

调整的步骤：

1.  如果插入的是根节点，直接把此节点涂为黑色。
2.  如果被插入的节点的父节点是黑色，什么也不需要做。
3.  如果被插入的节点的父节点是红色，如果叔叔节点也是红色，将父节点与叔叔节点变为黑色，祖父节点变为红色，以祖父节点为当前节点，继续调整。
4.  如果被插入的节点的父节点是红色，叔叔节点是黑色。分为四种情况。

情况如下：

1.  当前节点是父亲的左孩子，父亲是祖父的左孩子（Left-Left），处理思路：a.将祖父节点右旋;b.交换父节点和祖父节点的颜色。
2.  当前节点是父亲的右孩子，父亲是祖父的左孩子（Right-Left），处理思路：a.将父节点左旋，并将父节点作为当前节点; b.然后再使用Left Left情形
3.  当前节点是父亲的右孩子，父亲是祖父的右孩子（Right-Right），处理思路：a.将祖父节点左旋;b.交换父节点和祖父节点的颜色
4.  当前节点是父亲的左孩子，父亲是祖父的右孩子（Left-Right），处理思路：a.将父节点右旋，并将父节点作为当前节点; b.然后再使用Right Right情形

#### 插入算法调整过程示例 ####

**调整红黑树三种情况**

1.  被插入的节点是根节点：直接把此节点涂为黑色。
2.  被插入的节点的父节点是黑色：什么也不需要做。节点被插入后，仍然是红黑树。
3.  **被插入的节点的父节点是红色：需要进行调整。**

**父节点是红色的两种情况**

1.  当前节点的父节点是红色，且当前节点的叔叔节点也是红色。
2.  当前节点的父节点是红色，但当前节点的叔叔节点是黑色。

对于第1种：叔叔节点也是红色，步骤如下：

1.  将“父节点”、“叔叔节点”设为黑色。
2.  将“祖父节点”设为“红色”。
3.  将“祖父节点”设为“当前节点”(新插入的节点)，之后继续对“当前节点”进行操作。

如下图，新插入节点为35，还需对祖父节点60继续操作进行。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 3]  
**父节点是红色，叔叔节点是黑色**

分为四种情况：

对于第2种：叔叔节点是黑色，且当前节点是其父节点的右孩子，步骤如下：

1.  将“父节点”作为“新的当前节点”。
2.  以“新的当前节点”为支点进行左旋。（支点相当于上面左旋图片的A节点）
3.  继续检查并调整。

如下图，由上一步，我们需对节点60进行操作  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 4]

对于第3种：叔叔节点是黑色，且当前节点是其父节点的左孩子，步骤如下：

1.  将“父节点”设为“黑色”。
2.  将“祖父节点”设为“红色”。
3.  以“祖父节点”为支点进行右旋。（支点相当于上面右旋图片的A节点）
4.  继续检查并调整。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 5]

#### 删除算法 ####

https://www.jianshu.com/p/84416644c080  
删除总体步骤如下：

1.  第一步：将红黑树当作一颗二叉查找树，将节点删除。
2.  如果被删除节点是叶子节点，且为红色，那就直接删掉。
3.  如果被删除节点是叶子节点，且为黑色，这时需要调整，删掉节点，用nil节点代替它，对nil节点进行平衡操作（详细见下）。
4.  如果被删除的节点只有一个叶子节点，那它一定是一个黑色节点，且其子节点为红色（红黑树的特性决定）。此时用删除节点的子节点接到父节点，且将子节点颜色涂黑，保证黑色数量。
5.  有两个子节点时，找到删除节点的右子树的最小节点（后继节点），然后替换删除结点。将后继节点原先的位置作为当前节点，因为后继节点一定是一个叶子节点或者是只有一棵子树，情形转至为2、3、4处理。

对于第3种情形，需要进行平衡操作，我们将

1.  当前节点（nil）是根节点，不用操作。
2.  当前节点（nil）的兄弟节点是黑色，如果兄弟节点的子节点全是黑色，父亲节点是红色：交换父亲节点与兄弟节点颜色，平衡结束。
3.  当前节点（nil）的兄弟节点是黑色，如果兄弟节点的子节点全是黑色，父亲节点是黑色：将兄弟节点涂为红色，对父亲节点当做当前节点，继续操作。
4.  当前节点（nil）的兄弟节点是黑色，如果兄弟节点的子节点不全是黑色，兄弟节点在左边，其左子树为红色：以父亲节点右旋，交换父亲节点与兄弟节点颜色，将兄弟节点的左子树涂为黑色，平衡结束。
5.  当前节点（nil）的兄弟节点是黑色，如果兄弟节点的子节点不全是黑色，兄弟节点在右边，其右子树为红色：以父亲节点右旋，交换父亲节点与兄弟节点颜色，将兄弟节点的右子树涂为黑色，平衡结束。
6.  当前节点（nil）的兄弟节点是黑色，如果兄弟节点的子节点不全是黑色，兄弟节点在左边，其左子树为黑色：以兄弟节点左旋，交换兄弟节点与兄弟节点右子树颜色，转换为第4中情形。
7.  当前节点（nil）的兄弟节点是黑色，如果兄弟节点的子节点不全是黑色，兄弟节点在右边，其右子树为黑色：以兄弟节点右旋，交换兄弟节点与兄弟节点左子树颜色，转换为第5中情形。
8.  当前节点（nil）的兄弟节点是红色，如果兄弟节点在左边，以父节点右旋，交换父亲节点与兄弟节点颜色，转换为兄弟节点为黑色的情况。
9.  当前节点（nil）的兄弟节点是红色，如果兄弟节点在右边，以父节点左旋，交换父亲节点与兄弟节点颜色，转换为兄弟节点为黑色的情况。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 7]  
**第一步删除有如下情况：**

1.  被删除节点没有儿子，即为叶节点，直接将该节点删除。
2.  被删除节点只有一个儿子，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
3.  如果被删除节点左右都有孩子，先找到删除节点的右子树的最小节点（后继节点），然后替换删除结点。

具体情况如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 8]

**第二步调整树有如下情况**

1.  节点是红色，不需要调整，只要把替换结点的颜色设为删除的结点的颜色即可重新平衡。
2.  节点是黑色，需要旋转着色

原文链接：  
https://blog.csdn.net/yy\_0733/article/details/95164590  
https://www.jianshu.com/p/7b38abfc3298?utm\_source=oschina-app  
https://www.cnblogs.com/nananana/p/10434549.html

## 红黑树操作示例 ##

**第1次**.对在空的红黑树中插入第一个元素时，插入红色节点，由于违反第二条规定，做变色操作，变为黑色节点,如下图所示。  
![在这里插入图片描述][20200303183712415.png]

**第2次**继续插入两个子节点，不需要任何变色操作，如下图所示。  
![在这里插入图片描述][20200303183757522.png]

**第3次**给节点B插入左子节点D，插入后由于新节点的父节点B和叔叔C节点（祖父节点的另一个子节点）也都是红色，违反了第三条，最简单的办法就是将其父节点B和叔叔节点C变为黑色，如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 9]

**第4次**给节点D插入左子节点E，插入后首先插入节点E为红色，其父节点D为红色，且新插入的E是其父节点D的左子节点，解决办法是，首先将其父节点D变为黑色，祖父节点B变为红色，然后以祖父节点B为支点向右旋转，如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 10]  
**第5次**给节点B插入右子节点F，其父节点B和叔叔节点E均为红色，将父节点B和叔叔节点E变为黑色并将其祖父节点D变成红色，如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 11]

**第6次**多插入几个节点便于后面观察，如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 12]

**第7次**给G插入左子节点K，其父节点和叔叔节点均为红色，所以将父节点和叔叔节点变为黑色且祖父节点变为红色，如下图从1变成2。这样B和D都是红色又会冲突，此时将B看作是新插入的节点，B的父节点为红色，叔叔节点为黑色，且B是其父节点的右子节点，以D为支点向左旋转，如下图3变成4(蓝色箭头代表转移的位置并不是代表连接到该节点上)。接下来D和B都是红色依然冲突，将D看着是新插入的节点，其父节点B为红色，叔叔节点C为黑色，且是其父节点B的左子节点，所以将其父节点B变为黑色，祖父节点A变为红色，并以A节点为支点向右旋转，如下图5变成6再变成7，这样整个红黑树就平衡了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 15]

操作参考：https://blog.csdn.net/duduhonghong/article/details/83860904  
部分参考：https://www.cnblogs.com/2sheep2simple/p/10780560.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200303182148238.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200308105820286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200308105828411.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200308113329384.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200308113406286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020030811374118.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200320105418129.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200320105407625.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200308115328800.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[20200303183712415.png]: https://img-blog.csdnimg.cn/20200303183712415.png
[20200303183757522.png]: https://img-blog.csdnimg.cn/20200303183757522.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200303183809122.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200303183929484.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200303184002924.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200303184102689.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200303184150192.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200303184201549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200303184134876.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70