红黑树（插入和删除原理）

男娘i 2023-06-19 15:27 48阅读 0赞

二叉查找树（BST）是一种父亲节点的值大于左孩子的值，而小于右孩子的值，查找效率是O(logn)，但是在插入方面，可能在某些情况下使整个树退化成链表。所以为了进一步实现优化，有了红黑树的数据结构。  
红黑树的特点：  
（1）在父亲节点和子节点的关系上，和BST树是一致的。  
（2）每个节点都有颜色标示  
（3）根节点是黑色  
（4）叶子节点为NULL，也必须是黑色  
（5）如果一个节点是红色，则两个孩子节点是黑色  
（6）对于每个节点，从该节点到所有后代叶子节点的路径上，均包含相同数目的黑色节点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]  
\[图片来源于网络，侵权立删\]

因为在删除或插入的时候，会进行局部的旋转或者变色（后面会说），来维持二叉查找树的特性，而不会使整个树退化成链表，红黑树根节点到任意子节点的最大距离不大于最小距离的二倍。

左旋转：假设在某个X节点上作左旋转，如图（假设Z不为NULL）：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 1]  
左旋转后，X的右孩子成为该子树新的根节点，X变成新的新根节点的左孩子，而Y的左孩子转换成了X的右孩子。  
左旋转流程图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 2]

*  伪代码

左旋转
    LEFT_REPORT(T, x)
        y = right[x] //获取x右孩子节点y
        right[x] = left[y] //将y的左孩子找到，作为x的右孩子
        if(right[x] != null)  //要是右孩子不是null
            parent[left[y]] = x ; //将右孩子的父亲节点设置成x
        parent[y] = parent[x] //将y的父亲节点设置成原来x的父亲节点
        if(parent[y] == null) //要是y父亲节点是空的话
            root[T] = y //将y作为当前根节点
        else if(x == left[parent[x]]) //要是X是左孩子
            left[parent[x]] = y //将y设置成x的父亲节点的左孩子，也就是使用y代替x之前的位置
        else //否则就是右孩子
            right[parent[x]] = y  //使用y替换x的位置
        left[y] = x //讲x设置成y的左孩子（因为是左旋转）
        parent[x] = y //将y设置成x的父亲

右旋转：即左旋转的逆过程。  
以上面第二个图为例子，以Y为根节点的树，左右旋转，会将其左孩子转换成根节点，而根节点Y会变成新的根节点的X的右孩子，最后X的右孩子转换成Y的左孩子。

*  右旋转

右旋转
    RIGHT_REPORT(T, x)
        x = left[y] //获取y的右孩子x
        left[y] = right[x]  //将x的右孩子作为y的左孩子
        if(right[x]) //要是x的右孩子不为null
            parent[right[x]] = left[y] //讲右孩子的父亲指针指向y
        parent[x] = parent[y] //让x的父亲指针指向根节点y的父亲节点
        if(parent[y] == null) //要是y的父亲节点是空，说明y就是根节点
            root[T] = x //讲x设置成树的根节点
        else if(y == left[parent[y]]) //x是其父亲节点左孩子
            left[parent[x]] = x //将y原来的父亲节点左指针指向x
        else 
            right[parent[x]] = x //使原来y的父亲节点的右指针指向x
        right[x] = y //将x的右指针指向y
        parent[y] = x //将y的父亲指针指向x

红黑树的插入操作，类似于于二叉搜索树的插入操作，只是在他的基础上进行了改进，先把节点按照二叉查找树的插入方式进行插入，在把该插入的节点标记为红色（因为从根节点到叶节点的黑节点数量要相等，所以暂时标记成红色），插入以后需要维持二叉搜索树的性质，所以就需要对部分子树进行重新着色或者旋转。使二叉树重新平衡。

将新的节点加到树中的过程就是不断比较，比根节点大往右走，小于根节点，往左走，一直走到大于当前根节点小于根节点的右子树。

完成左右和父亲指针的指向，为插入节点标记上红色。

插入节点以后，树是一颗BST树，但是会失去红黑树的一些性质，需要变色和旋转进行调整。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 3]  
插入总结为三种情况：

*  插入节点的父亲节点是红色，如图想在原先红黑树中插入Z节点，插入后，破坏了性质【红色节点的孩子节点全为黑色】  
    所以需要进行变色操作，将插入的节点的父亲节点和叔叔节点Y都涂成黑色。祖父节点7设置成红色。变化后：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 4]  
（要是插入的节点是父节点的右孩子，和上面的方法大同小异，相信聪明的你懂得！）  
然后再继续向上判断是否破坏了红黑树的性质。

*  Z的叔叔节点是黑色，并且插入节点是根节点的右孩子
 *  Z的叔叔节点是黑色，并且插入节点是根节点的左孩子

就情况2，如图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 5]  
这里需要将以parent\[z\]作为根节点左旋转，转换成情况3：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 6]  
将z节点变成黑色，再将z节点的父亲节点变成红色，最后以z的父节点为根进行右旋转。这样完成了红黑树的一次插入。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 7]  
由上面的插入步骤来看，实现插入的三种情况是有转换关系的，插入的时候，可以是第一种情况，然后再经过变色转换成第二种情况后，那么第二种情况通过旋转又可以达到第三种情况，第三种情况是再经过旋转就能又维护一个红黑树了。  
也可以是第二种情况，转换成第三种情况…这些过程通过z节点的动态变化来转化。

下面是三种情况解决过程的伪代码：

插入操作(在此操作之前有个插入操作，相当于BST插入节点的形式，比较简单)
    RB_INSERT_NODE
        while(color[parent[z]] == RED) //要是当前父亲节点颜色是红色
            if(parent[z] == left[parent[parent[z]]]) //当前节点的父亲节点是其上一辈节点的左孩子
                y=right[parent[parent[z]]] //记录下叔叔节点
            //情况1，z叔叔的颜色是红色
            if(color[y]==RED) //要是叔叔节点也是红色
                color[y] = BLACK
                color[parent[z]] = BLACK //将叔叔和父亲节点都变成黑色
                color[parent[parent[z]]] = RED //祖父节点的颜色变成红色
                z = parent[parent[z]] //将祖父节点的颜色通过z记录下来，这里重置了z的值！！！
            //第二种情况z是右孩子，叔叔节点是黑色
            else if(z == right[parent[z]])
                z=parent[z] //重新设置z为当前根节点
                LEFT_ROTATE(T,z) //进行一次坐旋转，进入第三种情况，注意左旋转使Z的位置重新变化！！！
            //第三种情况，z是左孩子，叔叔节点为黑色 
                color[parent[z]] = BLACK //将父亲节点设置成黑色
                color[parent[parent[z]]]=RED //祖父节点设置成红色
                //进行右旋转
                RIGHT_ROTATE(T, parent[parent[z]])    //注意右旋转使z的值重新变化！！！
            要是当前z节点的情况满足while循环条件，继续变色和旋转
        color[root] = BLACK //重新设置根节点颜色

*  删除操作

如果删除的节点是红色的，则树的性质不发生改变。要是黑色的话，则会导致红黑树的性质发生改变。  
删除节点主要可能破坏了以下性质：  
如果删除的节点y是黑色的  
1.如果y是原来的根节点，而y的一个红色孩子节点成为了新的根节点，  
2.如果x和parent\[y\]（此时parent\[x\]=parent\[y\]）都是红色，则违反了【红色节点的孩子节点都是黑色】这一性质（这里的x代表删除y以后，y位置的新节点）  
3.删除y将会导致先前包含y的路径上黑节点个数减少1，使得【根节点到任何叶子节点的路径上黑节点的个数相同】这一性质改变，改正这一问题的方法，可以将现在占有y原来位置的节点x可以视为包含一重额外的黑色，就是将包含（现在占有y位置的节点）x所有路径上的黑节点个数加1  
4.当黑色节点被删除时，将其黑色下推至其子节点，导致问题变成节点x即不是红也不是黑，从而导致【每个节点是黑色，或者红色】性质不成立。因为给x增加一种颜色，即节点x是双重黑色或者是红黑色。这样就分别给包含x的路径上黑节点的个数贡献2个或者1个，但是x的color仍然是RED（如果x是红黑色）或者BLACK（如果x是双重黑色）。一个节点额外的黑色反应在x指向他，而不是他的color属性。

//删除节点(前面操作和二叉查找树的删除差不多) 
    RD_DELETE(T, z)
        if(left[z] == null || right[z] == null)
            y = z  //左孩子或者右孩子为空
        else y = tree-sucessor(z) //否则的话，y就等于某个具体的孩子节点
        if(left[y] != null)
            x = left[y]  //使y的左指针指向x 
        else x = right[y]
        parent[x] = parent[y] //使x的父节点指针指向y 
        if(parent[y] == null) 
            root[T] = x //将x设置成新的根节点
        else if(y == left[parent[y]])
            left[parent[y]] = x 
        else right[parent[y]] = x 
        if(y!=z) 
            key[z] = key[y]
            y.left = z.left
            y.left.p = y 
            y.color = z.color
        if(color[y] == black)
            RB_DELETE_FIXUP(T,x) //用来恢复红黑树的性质
        return y

下面是恢复红黑树性质的过程了！  
如果删除的节点是红色的话，红黑树的性质还是保持着，不用做修正操作。  
要是删除的是黑色节点，则导致包含该删除节点的所有路径少一个黑色节点，需要作修正操作。（要是删除的是整棵树唯一的黑色子节点，还是不用调整）  
我们从替换被删除节点的节点z开始，由于删除节点导致少了一个黑色节点，我们可以认为z有双重颜色（多余的那个颜色是一种假设），其中一个颜色是自带的颜色，另一个颜色是从父亲节点继承下来。要是z节点的自身颜色是黑色，则删除其父亲节点后，他的颜色就变成了【黑黑】，否则就是【红黑】，这样是为了保持性质【从根节点开始到任意每个叶子节点都经过相同数目的黑色节点】不变。然后我们回复其他性质。

有以下情况：  
1）当前节点z是红+黑色  
解法：直接把当前节点染成黑色，此时红黑树性质全部恢复  
2）要是当前节点是黑+黑色且是根节点，什么都不做，结束  
3）当前节点是黑+黑色且兄弟节点为红色（此时父亲节点和兄弟节点的子节点全为黑）  
如下图：这种情况，w必须要有黑色子节点，所以改变w以及parent\[z\]的颜色，并对parent\[z\]做一次左旋转。现在x的新兄弟节点是旋转之前w的某个子节点，其颜色是黑色，转换后性质没发生变化，并将兄弟节点变成黑色。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 8]  
实现伪代码：

RD_DELETE_FIX(T,z)
        while(z != root && color[z] == black)
            if(z == left[parent[z]]) //这里只考虑左子树，右子树的话同样的道理
                w = right[parent[z]]
                if(color[w] == RED) 
                    color[parent[z]] = RED
                    LEFT_ROTATE(T, parent[z])   
                    w = right[parent[x]]

4）当前节点是黑加黑，并且兄弟是黑色且兄弟节点两个子节点全为黑色。  
解决：因为w是黑色的，所以从z和w上去掉一重黑色，使得x只有一重黑色，而w为红色，为了补偿从z和w上去掉的一重黑色，在原来是红色或者黑色的parent\[z\]上新增一重额外的黑色，通过将parent\[z\]作为新节点z，来重复while循环。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 9]  
即调用RB\_INSERT\_FIXUP(T, z)

if(color[left[w]] == black && color[right[w]] == black)
    	color[w] = RED
    	z = parent[z]

5）z的兄弟节点w是黑色，w的左孩子节点是红色，右孩子节点是黑色

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 10]  
可以交换w的左孩子和w的颜色，再进行右旋转。现在z的新兄弟节点w是一个有着红色有孩子的黑色节点

else if(color[right[w]] == BLACK) 
    	color[left[w]] = BLACK
    	color[w] = red
    	right_rotate(T, w)
    	w = right[parent[z]]

6）z的兄弟节点w是黑色，且w的右孩子节点是红色的（也类似于经过上面一步转化的结果）。  
解决：将w节点的颜色设置成parent\[z\]节点的颜色，parent\[z\]节点的颜色设置成黑色，w的右孩子right\[w\]设置成黑色，以parent\[z\]作为根节点进行左旋转。完成删除工作。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 11]

color[w] = color[left[w]]
    color]parent[z]] = BLACK
    color[right[w]] = BLACK
    LEFT_ROTATE(T, parent[z])
    x = root(T)

参考文章：

https://blog.csdn.net/chenhanzhun/article/details/38405041  
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md  
http://www.cnblogs.com/Anker/archive/2013/01/30/2882773.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191207131228387.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191211172824590.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191207225029688.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2019120723032493.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191207231342166.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191208001654369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191210192309157.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20191208102655855.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20191208143945330.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20191208144025362.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20191208144101757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20191208144342662.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70