红黑树的插入和删除自平衡基础知识

清疚 2023-07-24 08:43 55阅读 0赞

#### 背景 ####

1.  参考文档 [30张图带你彻底理解红黑树][30]

#### 过程 ####

*  **插入自平衡的7种情况记录**

1.  红黑树为空树。把插入节点作为根节点，并把节点设置为黑色。
2.  插入节点的Key已存在。更新当前结点的值为插入节点的值。
3.  插入节点的**父节点为黑节点**。直接插入。
4.  插入节点的**父亲节点是红节点**的时候，**一共有4种情况**。a,叔叔节点存在且为红色。b,叔叔节点存在是黑色或者不存在。
    
    如果是a情况（插入的时候有**两种**插入的情况，但是都一样处理），不用旋转，只需要变更父亲节点和祖父节点的颜色，并且**把祖父节点设置成插入的节点，继续判断**。
    
    如果是b情况，就需要旋转，为什么需要旋转，是因为出现某些子树的节点多了，因此需要旋转。  
    **是祖父节点的左子树。** **记住标准的一个，插入节点是父亲节点的左子树**。对父亲节点和祖父节点进行变色，并右旋祖父节点。
    
    **是祖父节点的右子树。** 插入节点是父亲节点的右子树，需要先左旋父亲节点，变成“标准模式”。然后，对父亲节点和祖父节点进行变色，并右旋祖父节点。

*  **删除自平衡的9种情况记录**

1.  有哪些情形？  
    a) 若删除节点无子节点，直接删除。  
    b) 若删除节点只有一个子节点，用子节点替换删除节点。  
    c) 若删除节点有两个子节点，有后续节点（大于删除节点的最小节点）替换删除节点。
2.  对于上述情形c有9种情况：理解前提条件（删除操作删除的节点可以看作删除替代节点，而替代节点最后总是在树末。）
    
    **如果替换节点是红色的**，则不影响树的平衡，因此在树的末端找到替代节点，把替代节点的颜色设置为删除节点的颜色即可。
    
    **如果替换节点是黑色的**，则一定会影响树的平衡。
    
        是父亲节点的左子节点
        
        	兄弟节点是红节点 （变形到下面的三种情况中的某一种）
        
        	兄弟节点是黑节点
        		a,右子节点是红节点，左子节点任意颜色（标准模式）
        		b,右子节点是黑节点，左子节点为红节点（目标是变成标准模式b--->a）
        		c,子节点都为黑节点（变成b或者a，如果变成b的话，还需要在变形到a标准模式即可）
        
        
        是父亲节点的右子节点
        
        	兄弟节点是红节点（变形到下面三种情况中的某一种）
        
        	兄弟节点是黑节点
        		a,左子结点是红结点，右子结点任意颜色(标准模式)
        		b,左子结点是黑结点，右子结点为红结点（目标是变成标准模式b--->a）
        		c,子结点都为黑结点（变成b或者a，如果变成b的话，还需要在变形到a标准模式即可）

#### 小结 ####

1.  **插入规律**：核心就是，旋转的时机是什么？旋转方向分析过程：如果右旋转，则左子树节点多了。如果左旋转，则右子树节点多了。无论左旋还是右旋，都是旋转点，往下拉扯，儿子节点往上拉扯。记住标准模式，有时候需要旋转父亲节点，转化成标准模式
2.  **什么是标准模式？**  
    这是自定义的。  
    a) 祖父的左子树，父亲依然是左节点，插入的节点依然是左节点插入。
    
    b) 祖父的右子树，父亲依然是右节点，插入的节点依然是右节点插入。
3.  **什么时候旋转？**  
    a) 必须把当前节点插入情况，先转化为标准模式，这个时候，不变色，只是旋转父亲节点即可。旋转可以理解为拉扯，左旋就是把旋转点往一边拉扯。
    
    b) 红黑树某个分支的层高或者叫深度比另一个分支高2了，这个时候需要旋转。先变父亲节点色，再变祖父节点色，把祖父节点当成旋转点，然后往节点少的一个分支拉扯即可。
4.  操作：变色 + 拉扯（旋转）
5.  不用记忆具体的操作细节。而是想，出现某种情况的时候，是变色还是拉扯（旋转）。
6.  删除结论。删除操作可以看成**删除替代节点**。先找到删除节点的替代节点。然后，分析替代节点是什么颜色即可。如果替代节点是红色的，不影响红黑树平衡，但是颜色会被设置成删除节点的颜色。
7.  后续通过结合HashMap源码对红黑树的实践过程，反过来理解红黑树理论知识，会发现，理论知识是一样的，但是实现的细节或者说是小技巧是不一样的，理解起来反而更加清晰。

[30]: https://www.jianshu.com/p/e136ec79235c