数据结构 —— 红黑树：图解插入示例

比眉伴天荒 2021-11-04 14:40 335阅读 0赞

### 文章目录 ###

*   *  1、说明
     *  2、插入过程
     *  3、最终结果

看本文的前提是必须懂得红黑树的原理，可以参考：https://blog.csdn.net/xiaojin21cen/article/details/98727164

## 1、说明 ##

将下列数

12、1、9、2、0、11、7、19、4、15、18、5、14、13、10、16、6、3、8、17

20个数，插入到红黑树中。

## 2、插入过程 ##

（1）插入12  
![在这里插入图片描述][20190808152548997.jpg]

说明：插入的节点若是根节点，则直接将其设置为黑色

（2）插入1

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

说明：插入的节点若不是根节点，则将其设置为红色

（3）插入9

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 1]

操作：

*  父点1 左旋
 *  祖父节点12 右旋
 *  交换节点9 和12 颜色。

（4）插入2  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 2]

操作：

*  交换节点1、12、9 交换颜色；
 *  因为9为根结点，故将9 设为黑色。

（5）插入0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 3]  
父节点为黑色，故不做任何变化。

（6）插入11  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 4]  
父节点为黑色，故不做任何变化。

（7）插入7  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 5]  
操作：

*  节点0、2 设为黑色，节点1、7 设为红色；

（8）插入19  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 6]

父节点为黑色，故不做任何变化。

（9）插入4

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 7]

操作：

*  节点7 右旋
 *  节点2 左旋
 *  节点2、4、7 交换颜色

（10）插入15  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 8]  
操作：

*  节点11、19设为黑色，节点12设为红色。（父叔同红，红加黑）

（11）插入18

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 9]

操作：

*  节点15 左旋
 *  节点19 右旋
 *  节点18 设为黑色、15、19设为红色 （父叔同红，黑加红）

（12）插入5

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 10]

操作：

*  节点2、7设为黑色，节点5、4设为红色。（红加黑）
 *  将节点4 的父节点1、12设为黑色，祖节点9设为 红色（红加黑）
 *  因为9 为根节点，故将9设为红色。

（13）插入14

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 11]

操作：

*  节点15、19设为黑色，节点18设为红色。（父叔同红，红加黑）

（14）插入13

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 12]

操作：

*  节点15 右旋；
 *  节点14 设为黑色，节点15 设为红色。（黑加红）

（15）插入10

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 13]

父节点为黑色，故不做任何变化。

（16）插入16

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 14]

操作1：

*  节点13、15 设为黑色，节点14 设为红色；（父叔同红，红加黑）

操作2：

节点14 为当前节点，14、18同为红色，故需要左右旋。操作如下：

*  节点18 右旋
 *  节点12 左旋
 *  交换12、14的颜色 （黑加红）

（17）插入6

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 15]

操作：

*  节点5 左旋
 *  节点7 右旋
 *  6、7 交换颜色（黑加红）

（18）插入3

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 16]

父节点为黑色，故不做任何变化。

（19）插入8

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 17]

操作1：

*  节点距5、7设为红色、6 设为黑色；

操作2：  
节点6 为当前节点。

*  祖父节点1 左旋

（20）插入17  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 18]

操作1：

*  节点17的祖父节点15左旋
 *  交换15、16的颜色

## 3、最终结果 ##

插入完毕，最后的结果是  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 19]

[20190808152548997.jpg]: /images/20211104/98dc65a8cf9a4472b5f458636c99d766.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70]: /images/20211104/2d82cee594124842b25590b24bdbeccb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 1]: /images/20211104/ca98eb52bd4843b6b564bd214dcbea20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 2]: /images/20211104/8daf682e07db421da1aa015052ae6bb4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 3]: /images/20211104/b9f12979db094b949f90ff3db33122b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 4]: /images/20211104/2a8895fff27b40a099d01dbbeb0c2205.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 5]: /images/20211104/15cfd5f9295b4b9b8205b88c37122a2e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 6]: /images/20211104/84c804e2a50c4246b63a3b821c11b85c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 7]: /images/20211104/c8ed2ee3150e42088f339060e8e25e2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 8]: /images/20211104/b5a832bfbc3f42b0959d1438e44bfa0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 9]: /images/20211104/0f28ed97fc874375b6732c649f98bde9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 10]: /images/20211104/25dd40c6287e4580866ce582d8312990.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 11]: /images/20211104/d081152e1bf34b859c3a5be6894a7330.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 12]: /images/20211104/ceac3306444a423296d144b01464a31e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 13]: /images/20211104/a37f58ff69b0480e9cd66d6b8c58e8e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 14]: /images/20211104/7bf46ff76c0a47e49bbfb9448a85776e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 15]: /images/20211104/1933e65322644a939f4c4cb26d4d0fc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 16]: /images/20211104/89ea1e0f175e424fb57799e4d4892e6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 17]: /images/20211104/b3a9cd4254324bdaa8d4ac8b8d26b87b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 18]: /images/20211104/65e05c5cd6ac40aab917de4c06936fca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 19]: /images/20211104/c34f333521604125a2da59f4e4b2edca.png