当前位置: 首页 > news >正文

没有对象来和我手撕红黑树吧

1. 红黑树的介绍

红黑树也是一种自平衡的二叉搜索树,在每一个节点增加了一个存储位来表示节点的颜色,可以是红色也可以是黑色,通过约束颜色来维持树的平衡,具有以下的性质:

  1. 每个节点不是红色就是黑色
  2. 根节点为黑色
  3. 如果一个节点为红色,那么它的两个孩子节点为黑色(一条路径上不能有两个连续的红色节点)
  4. 对于每个节点,从该节点及其所有后代所在的叶子节点的简单路径上,均包含相同数目的黑色节点
  5. 每一个叶子节点都是黑色的

2. 节点的定义

这里节点除了包含节点的值,左子树,右子树和父亲节点的引用外,还需要添加颜色的属性

static class RBTreeNode {public RBTreeNode left;public RBTreeNode right;public RBTreeNode parent;public int val;public COLOR color;public RBTreeNode(int val) {this.val = val;//新创建的节点默认是红色的this.color = COLOR.RED;}
}

颜色只有红色和黑色,可以使用枚举类来定义节点的颜色

public enum COLOR {RED,BLACK
}

节点默认创建为红色的原因:如果节点是黑色,那么插入时就会增加该路径黑色节点的个数,其他路径都需要增加黑色节点,节点是红色的话就不会影响黑色节点的个数,如果上一个节点也是红色,只需要向上调整节点的颜色即可

3. 插入

在寻找插入到哪个位置时,也是和二叉搜索树一样的,(需要注意的是,第一次插入之后需要手动的把 root 节点的颜色修改为黑色)当找到插入的位置之后,可以分为一下几种情况

3.1. p 是左子树

  1. cur 为红色, p 为红色,g 为黑色,u 存在且为红色

两个红色不能连在一起,此时就必须把 p 修改为黑色,然后为了保持黑色是相同的, u 也需要修改为黑色

这个时候就会有一个问题,如果 g 是一个黑色节点的子树,那么这时修改 p , u 就会增加黑色节点的数目,就需要把 g 改为红色,假如 g 就是根节点的话,还是需要把 g 改回黑色,所以说最后处理完之后,无论 g 当前是红色还是黑色,都手动的改为黑色

那如果 g 的父亲节点本身就是红色的话,证明它一定是有父亲节点的,然后按照上面的方式调整之后继续向上调整即可

  1. cur 为红色且是左节点,p 为红色,g 为黑色,u 不存在或者是黑色

如果 u 不存在,那么 cur 一定是新插入的节点,原来的肯定是不能有两个连续的红色节点的

当 u 存在且为黑色的时候

这种情况在调整的过程中会出现

对于这种情况的解决方案就是,先右旋 p ,再调整颜色

  1. cur 为红且是右节点,p 为红,g 为黑,u 不存在或 u 为黑

这种情况也应该是调整过程中出现的

此时对 p 进行一个左旋,然后交换 cur 和 p 的引用,就变成了第二种情况,继续按照第二种的情况调整就好

3.2. p 是右子树

然后就是 p 是右子树的情况,也是和上面一样的三种情况:

  1. cur 为红色, p 为红色,g 为黑色,u 存在且为红色

这种情况和上面的是一样的

  1. cur 为红色且是右节点,p 为红色,g 为黑色,u 不存在或者是黑色

只不过这次是需要右旋的,其余步骤还是和之前一样

  1. cur 为红且是左节点,p 为红,g 为黑,u 不存在或 u 为黑

当以上所有的情况都考虑完之后,还需要手动的把 root 节点的颜色改为黑色

4. 红黑树的验证

验证的话主要就是验证有没有两个红色节点相连和每条路径的黑色节点数量是否相等

先来看红色节点是否相连:只需要在遍历的过程中遇到红色节点之后,去看它的父亲节点是否是红色的即可,然后递归执行

    private boolean checkRedColor(RBTreeNode root){if(root == null) return true;if(root.color == COLOR.RED){RBTreeNode parent = root.parent;if(parent.color == COLOR.RED){System.out.println("两个红色节点连续了");return false;}}return checkRedColor(root.left) && checkRedColor(root.right);}

判断每条路径黑色节点的数量是否相同:首先求出一条路径的黑色节点的数量,然后再遍历每条路径,同时统计路径上的黑色节点的个数,和开始计算的出的黑色节点个数对比,如果不相同那么就不满足红黑树的性质

private boolean checkBlackNum(RBTreeNode root,int pathBlackNum,int blackNum){if(root == null) return true;if(root.color == COLOR.BLACK){pathBlackNum++;}if(root.left == null && root.right == null){if(pathBlackNum != blackNum){System.out.println("黑色节点不符合要求");return false;}}return checkBlackNum(root.left,pathBlackNum,blackNum)&&checkBlackNum(root.right,pathBlackNum,blackNum);
}

最后把这两种情况都结合起来,同时还需要判断根节点的颜色是否是黑色

public boolean isRBTree(){if(root == null) return true;//根节点必须为黑色if(root.color != COLOR.BLACK) return false;//存储当前红黑树中的黑色节点个数int blackNum = 0;RBTreeNode cur = root;while(cur!=null){if(cur.color == COLOR.BLACK){blackNum++;}cur = cur.left;}//检查是否存在两个连续的红色节点和每条路径的黑色节点是否相同return checkRedColor(root) && checkBlackNum(root, 0, blackNum);
}

http://www.mrgr.cn/news/61782.html

相关文章:

  • java基础面试题二面向对象
  • 浏览器HTTP缓存解读(HTTP Status:200 304)
  • 基于java+SpringBoot+Vue的教师工作量管理系统设计与实现
  • 如何在Linux系统中使用Nginx作为Web服务器
  • k8s的配置和存储(ConfigMap、Secret、Hostpath、EmptyDir以及NFS的服务使用)
  • [vulnhub]Kioptrix: Level 1.2 (#3)
  • keepalived+脚本抢占模式和非抢占模式
  • ComfyUI 轻松实现二次元线稿上色,快速生成精美动漫图像(附工作流)
  • 直播美颜SDK平台开发指南:美颜API的应用与性能提升方案详解
  • 图解Redis 07 | HyperLogLog数据类型的原理及应用场景
  • 供需指标(Supply and Demand ),供给与需求,寻找支撑压力位神器 MT4免费公式!
  • DICOM标准:深入详解DICOM数据模型,理解DICOM数据模型
  • SAP系统与快递100系统集成案例
  • Helm全链路精通:从入门到实战,Kubernetes应用管理新高度
  • 机器学习中回归任务、分类任务常用的算法
  • CSP/信奥赛C++刷题训练:经典前缀和例题(4):洛谷P3662:Why Did the Cow Cross the Road II S
  • 技术星河中的璀璨灯塔 —— 青云交的非凡成长之路
  • 2024网鼎杯青龙组Web+Misc部分WP
  • 群控系统服务端开发模式-应用开发-业务架构逻辑开发Base开发总结
  • 【测试】——接口测试入门
  • 双十一狂欢节有哪些数码好物值得入手,盘点五款入手不亏的好物!
  • 从0开始搭建一个生产级SpringBoot2.0.X项目(二)SpringBoot应用连接数据库集成mybatis-plus
  • 计算结构力学:多自由度振动系统
  • 研究线性模型训练中损失变化的规律和最优学习率的影响
  • 2024 Rust现代实用教程:1.3获取rust的库国内源以及windows下的操作
  • Infinity-MM数据集:一个包含 4000 万个样本的开源视觉语言模型的大规模多模态指令数据集。