红黑树原理

我会带着你远行 2023-10-01 20:58 36阅读 0赞

## 算法 -> 添加 ##

### 1)添加节点为根节点（添加的元素为红节点，但是根节点需要为黑节点） ###

添加后变色 红变黑

### 2)添加节点的父节点为黑节点 ###

直接添加

### 3)添加节点的父节点和叔父节点都为红节点 ###

【父节点（变黑）和叔父节点（变黑）】
    		【祖父节点（变红） -> 自我修正】

### 4)添加节点的父节点为红节点 叔父节点为黑节点 ###

添加节点为父节点左节点 父节点为祖父节点的左节点
    		【以父节点为参照物 右旋】
    		【父节点（变黑）和祖父节点（变红）分别变色】

### 5)添加节点的父节点为红节点 叔父节点为黑节点 ###

添加节点为父节点右节点 父节点为祖父节点的右节点
    		【以父节点为参照物 左旋】
    		【父节点（变黑）和祖父节点（变红）分别变色】

### 6)添加节点的父节点为红节点 叔父节点为黑节点 ###

父节点为祖父节点的右节点	添加节点为父节点左节点 
    		【以子节点为参照物 右旋】
    		【以子节点为参照物 左旋】
    		【子节点（变黑）和祖父节点（变红）分别变色】

### 7)添加节点的父节点为红节点 叔父节点为黑节点 ###

添加节点为父节点右节点 父节点为祖父节点的左节点
    		【以子节点为参照物 左旋】
    		【以子节点为参照物 右旋】
    		【子节点（变黑）和祖父节点（变红）分别变色】

[练习连接][Link 1]

### 举列子： ###

1,7，9,20,50,18,17,10，100；

### 图解： ###

![在这里插入图片描述][cccf7feab0cf447b816a7158bfafce29.png]

![在这里插入图片描述][ce9961e97f60404cbd0daa30757064cc.png]  
![在这里插入图片描述][c11416cbd7fe4aaab6f034d3bfd78163.png]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_9_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_9_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_12_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_13_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_14_color_FFFFFF_t_70_g_se_x_16]

End》》》》  
当你的才华还撑不起你的野心的时候，  
你就应该静下心来学习。

[Link 1]: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[cccf7feab0cf447b816a7158bfafce29.png]: https://img-blog.csdnimg.cn/cccf7feab0cf447b816a7158bfafce29.png
[ce9961e97f60404cbd0daa30757064cc.png]: https://img-blog.csdnimg.cn/ce9961e97f60404cbd0daa30757064cc.png
[c11416cbd7fe4aaab6f034d3bfd78163.png]: https://img-blog.csdnimg.cn/c11416cbd7fe4aaab6f034d3bfd78163.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_9_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f04e620930834d6a921e5f8ee65172d4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAUmVjZW50bHkg56Wd56Wd,size_9,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_9_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/1f201f7790084aefa737dfd85cf14010.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAUmVjZW50bHkg56Wd56Wd,size_9,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_12_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/cb1a317a824d46dc8faf8e42cfd658f5.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAUmVjZW50bHkg56Wd56Wd,size_12,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1680aeafec61492f8efb25a6ccfe8d63.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAUmVjZW50bHkg56Wd56Wd,size_13,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAUmVjZW50bHkg56Wd56Wd_size_14_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f5b4984668994ccfbb4c4ea96ca02461.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAUmVjZW50bHkg56Wd56Wd,size_14,color_FFFFFF,t_70,g_se,x_16