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

embedded/2024/10/30 16:34:54/

1. 红黑树的介绍

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

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

2. 节点的定义

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

java">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;}
}

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

java">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. 红黑树的验证

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

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

java">    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);}

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

java">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);
}

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

java">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.ppmy.cn/embedded/133650.html

相关文章

手机照片怎么转换成jpg格式?分享6种图片格式转换方法

照片已成为我们记录生活的重要方式。然而,不同设备和应用生成的图片格式各异,有时我们需要将照片转换成JPG格式以便更广泛地分享和使用。很多小伙伴不清楚该怎样将照片的格式进行转换,尤其是在手机上,不用担心,下面给大…

Excel 单元格小数点精确位数机制

在 Excel 中,单元格的 .Value2 属性是用来表示数字或日期值的,它是 Excel 内部的数值存储方式,不包含货币或日期的格式信息。**对于小数位的支持,Excel 的内部精度可以达到 15 位有效数字**,这包括整数和小数部分。 因…

C++学习:类和对象(一)

一、面向过程与面向对象编程 1. 什么是面向过程编程? 面向过程编程(Procedural Programming)是一种以过程(或函数)为中心的编程范式。程序被视为一系列按顺序执行的步骤,主要通过函数对数据进行操作 特点…

虚拟机 Email 恢复专用工具:Virtual Machine Email Recovery

天津鸿萌科贸发展有限公司从事数据安全服务二十余年,致力于为各领域客户提供专业的数据恢复、数据备份解决方案与服务,并针对企业面临的数据安全风险,提供专业的相关数据安全培训。 天津鸿萌科贸发展有限公司是 SysTools 系列数据恢复、取证及…

蓝桥杯基本操作和运算

文章目录 1.基本运算2.循环--进制转换/最大公约数2.1进制转换2.2求解最大公约数 3.数组与字符串4.常用的API5.快速读写模版 蓝桥杯基本操作和运算 10-22号正式开始准备蓝桥杯的比赛,准备参加这个大学B组的Java的赛项 1.基本运算 首先就是基本的输入输出&#xff1…

Dockfile打包带tdengine驱动的tomcat镜像基于官方tomcat容器

之前写过一篇:Dockfile打包带tdengine驱动的tomcat自定义镜像_如何创建一个包含tdengine客户端的docker镜像-CSDN博客 上面这篇是基于centos容器镜像制作的,这篇改用tomcat容器制作。 Dockfile内容如下 # 使用官方的 Tomcat 8 镜像作为基础镜像&#…

windows 驱动实例分析系列: NDIS 6.0的Filter 驱动改造(三)

数据包的发送 NDIS数据包的发送是一件非常麻烦的事情,当然,在应用层,使用socket库感觉不到这一点,但是在内核中,内核主要实现是的七层结构中的下面4层,并且Filter驱动和协议驱动不一样,它完全就…

XCode16.0 Command PhaseScriptExecution failed with a nonzero exit code 的错误

环境 : XCode 16.0 pod --version 1.15.2把ENABLE_USER_SCRIPT_SANDBOXING 设置为NO OK 如果pod的版本<1.14.3 试一试修改这里