C++后端开发数据结构与算法篇：彻底搞懂红黑树

传奇木讷的鱼

1.红黑树有以下五个性质：

1.根节点为黑色
2.节点为红色或者黑色
3.每个叶子节点NIL为黑色
4.节点为红色，则两个孩子都为黑色(即每条路径上不能有连续两个红色)
5.任意一个节点到其所有子孙节点的NIL的路径上包含相同数目的黑色节点
2.插入操作

首先以二叉查找树的插入方式插入新的节点(插入的节点都是叶子节点处)，并将其涂为红色。然后再进行调整使其满足红黑树的五个性质。
新插入节点先涂为红色的原因：因为插入一个红色节点比插入一个黑色节点违背的性质要 少，这就会减少我们调整二叉树的次数。如果插入黑色节点 ，则必然会违反第5条性质；如果插入为红色节点，则只有一半的机会违反第4条性质，而且违反第4条性质比违反第5条性质比较起来，前者修正要方便一线。
下图为示例图：
N为新插入节点
P为插入节点的父亲节点
U为插入节点的叔父节点
R为根节点
G为祖先节点


2.1插入分为以下三种情况：

2.1.1新节点没有父节点(即插入根节点)
操作：将节点涂为红色插入根节点处，并改为黑色(使其符合性质1根节点为黑色)


2.1.2新节点N的父亲节点为黑色
此时不需要调整


2.1.3新节点N的父亲节点为红色
因为红黑树不允许有两个连续红色节点，所以要根据叔父节点的颜色来进行调整
2.2新节点的叔父节点为红色
将新节点的父亲结点和叔父节点涂为黑色，并将祖先节点G涂为红色，这样保证从G到任何NIL路径所包含的黑色节点数目与原来保持一致。由于把G变成了红色，如果G的父亲也为红色，则会违反性质导致连续两个红色节点，所以需要检查G是否违反红黑树性质。


2.3新节点的叔父节点为黑色
2.3.1若新插入节点为父节点的左孩子：

将父节点P涂为黑色，祖先节点G涂为红色，然后对祖先节点进行一次右旋


2.3.2若新插入节点为父节点的右孩子：

对父节点P进行一次左旋，问题转化为了左孩子情况。


3.删除操作

根据被删除节点D是否有NIL分类：
1.被删除节点D的两个孩子都是NIL
1.1被删除节点D为红色


1.2被删除节点D为黑色
D节点的兄弟节点B是否有NIL进行分情况：
1.2.1兄弟节点B两个孩子都为NIL
将P节点涂为黑色，将兄弟节点B涂为红色


半黑半红节点表示该节点既可能为红色，也可能为黑色。如果原来为红色，这样修改后路径上黑色节点数目跟修改前一样；如果原来为黑色，那么删除D后该路径上的黑色节点数目会少一个，所以还需要检查经过P节点的路径上黑色节点的数目减少是否影响了红黑树的性质。
1.2.2兄弟节点B有一个孩子为NIL，一个孩子不为NIL
这个不为NIL的孩子一定是红色的，不然会违反性质5(路径上黑色节点数目相同)。
当孩子为右孩子时：


当孩子为左孩子时：


1.2.3被删除节点D的兄弟节点B两孩子都不为NIL
若B为黑色，则两孩子一定为红色：


若B为红色，则两孩子一定都为黑色


2.被删除节点D两个孩子都不为NIL
按照二叉查找树删除节点的方法找到D的后继节点S，交换D和S的内容（颜色保持不变），被删除节点变为S，如果S有不为NIL的节点，那么继续用S的后继节点替换S，直到被删除节点的两个孩子都为NIL，问题转化为被删除节点D的两个孩子都为NIL的情况。
3.被删除节点D有一个孩子不是NIL
这个孩子节点一定为红色，(若为黑色，则违反性质5)。


相关视频推荐：
C++后端开发学习地址：https://ke.qq.com/course/417774?flowToken=1043850
需要C/C++ Linux服务器开发学习资料加群909332607获取（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享


原文链接：https://blog.csdn.net/inspiredbh/article/details/60474958?spm
原文作者：理想二旬