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

2

主题

7

帖子

10

积分

新手上路

Rank: 1

积分
10
发表于 2023-3-10 19:02:53 | 显示全部楼层
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
原文作者:理想二旬
回复

举报 使用道具

您需要登录后才可以回帖 登录 | 立即注册
快速回复 返回顶部 返回列表