【数&C++】图解红黑树 — 插入节点

Bertha 。 2023-02-19 01:26 21阅读 0赞

#### 1. 什么是红黑树 ####

*  红黑树，是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或Black。
 *  通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而接近平衡。

**【性质】**

1.  每个节点不是红色就是黑色；
2.  根节点是黑色的 ；
3.  树中不会出现连续的红节点；
4.  每条路径上黑色节点的数量都是相等的；
5.  叶子节点指的是空节点。

#### 2. 插入 ####

1.  按照二叉搜索树规则插入新节点；
2.  检测新节点插入后，红黑树的性质是否遭到破环。

【红黑树插入的是红节点】

1.  如果父亲是黑色，没有破坏性质，结束
2.  如果父亲是红色，破坏了性质3，祖父一定是黑色，关键看叔叔(三种情况)。

【约定】

*  cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点；
    
     *  情况一：cur为红，p为红，g为黑，u存在且为红；
     *  情况二：cur为红，p为红，g为黑，u不存在/存在为黑 -> 单旋；
     *  情况三：cur为红，p为红，g为黑，u不存在/存在为黑 -> 双旋。

【分析情况时以父为左，叔叔为右】

*  父为左，叔叔为右
    
    1.  情况一：变色、更新；
    2.  情况二：右单旋、变色；
    3.  情况三：先左单旋(变化后成情况二)、再右单旋、变色。
 *  父为右，叔叔为左
    
    1.  情况一：变色、更新；
    2.  情况二：左单旋、变色；
    3.  情况三：先右单旋(变化后成情况二)、再左单旋、变色。

【图解：以父为左，叔叔为右分析】

*  情况1  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70]
 *  情况2![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 1]
 *  情况3![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200618200738539.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200618200833967.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200618200905164.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70