数据结构之红黑树的 “奥秘“

news/2024/9/18 15:01:56/ 标签: 数据结构, java, 开发语言, 红黑树

目录：

一.红黑树概念

二. 红黑树的性质

三.红黑树的实现

四.红黑树验证 

五.AVL树和红黑树的比较

一.红黑树概念

1.红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何 一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近 平衡的。

二. 红黑树的性质:

1. 每个结点不是红色就是黑色

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的【没有2个连续的红色节点】

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点也就是（每条路径的黑色节点数相等）

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

总结性质：最长路径最多是最短路径的2倍.

总结性质推导：

三.红黑树的实现：

1.红黑树节点的定义 :

这里注意我们定义一个枚举来储存红黑树节点的颜色

java">public class RBTree {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 RBTreeNode root;
}

 

2.红黑树的插入:

这里我们要围绕红黑树上面的几条性质构建红黑树；但是红黑树是在二叉搜索树的基础上加上其平衡限制条件，所有我们构建时可以借鉴二叉搜索树方式。

步骤一：和二叉二叉搜索树一样找到要插入的节点；

步骤二：调整插入的节点让其满足红黑树的性质；

所有我们构建红黑树总共有三种情况

这里注意：插入节点默认为红色节点，推导如下：

3.构建红黑树的有三种情况:

3.1.情况一: cur为红，p为红，g为黑，u存在且为红:

图解：

代码：

java"> //开始调整颜色while (parent != null && parent.color == COLOR.RED) {RBTreeNode grandParent = parent.parent;/**情况一：** cur为红，p为红，g为黑，uncle存在且为红**  parent在grandParent左边，uncle在grandParent右边*/if (parent == grandParent.left) {RBTreeNode uncle = grandParent.right;if (uncle != null && uncle.color == COLOR.RED) {parent.color = COLOR.BLACK;uncle.color = COLOR.BLACK;grandParent.color = COLOR.RED;//预防grandParent的父亲为红色，就还有子树,继续向上修改cur = grandParent;parent = cur.parent;}

3.2.情况二: cur为红，p为红，g为黑，u不存在或者u为黑:

这里注意要先grandParent右旋，然后再调整颜色，parent改为 黑色，grandParent改为红色

 图解：

代码：

java">/** 情况二：
* cur为红，p为红，g为黑，uncle为黑色，或者uncle不存在
*
*  方法：
*  1.先右单旋
*  2.再改颜色*/
rotateRight(grandParent);
parent.color = COLOR.BLACK;
grandParent.color = COLOR.RED;

3.3.情况三: 调整过程中，cur为红，p为红，g为黑，u不存在/u为黑：

这里先左旋parent，再把parent 和 cur 的引用交换变为和情况二类似，再当作情况二处理（右旋改颜色，图片上笔误是右旋）

代码：

java">/*** 情况三：
* 先左单旋parent
* 再交换parent和cur的引用,变成情况二处理
*/
if (parent.right == cur) {
rotateLeft(parent);
RBTreeNode tmp = parent;
parent = cur;
cur = tmp;}//变成情况二

 

当parent == grandParent.right，和上面三种情况完全相反，为镜相关系。

插入全部代码如下：

java">public class RBTree {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 RBTreeNode root;//插入：public boolean insert(int val) {RBTreeNode node = new RBTreeNode(val);if (root == null) {root = node;//插入节点默认为红色所有，当root为空时，要把插入的节点变为黑色root.color = COLOR.BLACK;return true;}RBTreeNode cur = root;RBTreeNode parent = null;while (cur != null) {if (cur.val < val) {parent = cur;cur = cur.right;} else if (cur.val > val) {parent = cur;cur = cur.left;} else {return false;}}if (parent.val < val) {parent.right = node;} else {parent.left = node;}node.parent = parent;cur = node;//指向新插入的节点//开始调整颜色while (parent != null && parent.color == COLOR.RED) {RBTreeNode grandParent = parent.parent;/**情况一：** cur为红，p为红，g为黑，uncle存在且为红**  parent在grandParent左边，uncle在grandParent右边*/if (parent == grandParent.left) {RBTreeNode uncle = grandParent.right;if (uncle != null && uncle.color == COLOR.RED) {parent.color = COLOR.BLACK;uncle.color = COLOR.BLACK;grandParent.color = COLOR.RED;//预防grandParent的父亲为红色，就还有子树,继续向上修改cur = grandParent;parent = cur.parent;} else {/*** 情况三：* 先左单旋parent* 再交换parent和cur的引用,变成情况二处理*/if (parent.right == cur) {rotateLeft(parent);RBTreeNode tmp = parent;parent = cur;cur = tmp;}//变成情况二/** 情况二：* cur为红，p为红，g为黑，uncle为黑色，或者uncle不存在**  方法：*  1.先右单旋*  2.再改颜色*/rotateRight(grandParent);parent.color = COLOR.BLACK;grandParent.color = COLOR.RED;}} else {//下面情况和上面情况完全相反//parent == grandParent.rightRBTreeNode uncle = grandParent.left;if (uncle != null && uncle.color == COLOR.RED) {parent.color = COLOR.BLACK;uncle.color = COLOR.BLACK;grandParent.color = COLOR.RED;//预防grandParent的父亲为红色，就还有子树,继续向上修改cur = grandParent;parent = cur.parent;} else {if (parent.left == cur) {rotateRight(parent);RBTreeNode tmp = parent;parent = cur;cur = tmp;}//变成情况二rotateLeft(grandParent);parent.color = COLOR.BLACK;grandParent.color = COLOR.RED;}}}//当parent为空时，要把根节点变为黑色root.color = COLOR.BLACK;return true;}/*** 右单旋* @param parent*/private void rotateRight (RBTreeNode parent){RBTreeNode subL = parent.left;RBTreeNode subRL = subL.right;parent.left = subRL;subL.right = parent;//如果旋转的整棵树也是一个子树，记录下原来该树的父亲，后续修改RBTreeNode pParent = parent.parent;if (subRL != null) {subRL.parent = parent;}parent.parent = subL;//看看整棵树是否也是一个子树if (parent == root) {root = subL;root.parent = null;} else {//是子树就确定这棵树是左子树还是右子树if (pParent.left == parent) {pParent.left = subL;} else {pParent.right = subL;}}subL.parent = pParent;}/*** 左单旋* @param parent*/private void rotateLeft (RBTreeNode parent){RBTreeNode subR = parent.right;RBTreeNode subRL = subR.left;parent.right = subRL;subR.left = parent;RBTreeNode pParent = parent.parent;if (subRL != null) {subRL.parent = parent;}parent.parent = subR;//看看整棵树是否也是一个子树if (parent == root) {root = subR;root.parent = null;} else {//是子树就确定这棵树是左子树还是右子树if (pParent.left == parent) {pParent.left = subR;} else {pParent.right = subR;}}subR.parent = pParent;}
}

四.红黑树验证：

1.红黑树的检测分为两步：

步骤一： 检测其是否满足二叉搜索树(中序遍历是否为有序序列）

步骤二：检测其是否满足红黑树的性质 

 

步骤一： 检测其是否满足二叉搜索树(中序遍历是否为有序序列）：

代码：

java"> /**1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)* 中序遍历：* @param root*/public void inorder(RBTreeNode root){if(root == null){return;}inorder(root.left);System.out.print(root.val+ " ");inorder(root.right);}

步骤二：检测其是否满足红黑树的性质 :

java">//2.检测其是否满足红黑树的性质:public boolean isRBTree(){if(root == null){//空树也是红黑树return true;}if(root.color != COLOR.BLACK){System.out.println("违反了性质2：根节点不是黑色");return false;}RBTreeNode cur = root;//blackNum是事先计算好一边黑色节点的个数int blackNum = 0;while (cur != null){if (cur.color == COLOR.BLACK){blackNum++;}cur = cur.left;}//判断性质三有没有两个红色的节点 && 判断性质四：每条路径的黑色节点个数是否相等return checkRedColor(root) && checkBlackNum(root,blackNum,0);}/*** 判断性质三有没有两个红色的节点：* 思路：遍历当前二叉树节点如果是红色，则判断他的父亲节点是不是红色* @param root* @return*/private boolean checkRedColor(RBTreeNode root){if(root == null){return true;}if (root.color == COLOR.RED){RBTreeNode parent = root.parent;if (parent != null && parent.color == COLOR.RED){System.out.println("违反了性质三: 连续出现两个红色的节点");return false;}}return checkRedColor(root.left) && checkRedColor(root.right);}/***判断性质四：每条路径的黑色节点个数是否相等* @param root* @param blackNum:事先计算好黑色节点的个数* @param pathBlackNum：每次递归计算的黑色节点的个数* 思路：看 blackNum 和 pathBlackNum 的数量是否相等* @return*/private boolean checkBlackNum(RBTreeNode root,int blackNum, int pathBlackNum){if(root == null){return true;}if (root.color == COLOR.BLACK){pathBlackNum++;}//blackNum 和 pathBlackNum 的数量是否相等就不满足性质if (root.left == null && root.right == null){if(pathBlackNum != blackNum){System.out.println("违反了性质四：每条路径的黑色节点个数不相等了！");return false;}}return checkBlackNum(root.left,blackNum,pathBlackNum)&& checkBlackNum(root.right,blackNum,pathBlackNum);}

  

五.AVL树和红黑树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log2^n)，红黑树不追求绝对平衡，其只需保 证最长路径不超过最短路径的2倍(相对平衡)，相对而言，降低了插入和旋转的次数，所以红黑树在经常进行增删的结构中性能比 AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。 

 

补充：java集合框架中的：TreeMap、TreeSet底层使用的就是红黑树


http://www.ppmy.cn/news/1524597.html

相关文章

小阿轩yx-Zabbix企业级分布式监控环境部署

小阿轩yx-Zabbix企业级分布式监控环境部署

小阿轩yx-Zabbix企业级分布式监控环境部署 前言 “运筹帷幄之中&#xff0c;决胜千里之外”监控在 IT 运维中占据着重要地位&#xff0c;按比例说占 30% 也不为过在监控系统开源软件中有很多可选择的工具&#xff0c;但是真正符合要求的、能够真正解决业务问题的监控系统软件…
阅读更多...
如何阅读PyTorch文档及常见PyTorch错误

如何阅读PyTorch文档及常见PyTorch错误

如何阅读PyTorch文档及常见PyTorch错误 文章目录 如何阅读PyTorch文档及常见PyTorch错误阅读PyTorch文档示例常见Pytorch错误Tensor在不同设备上维度不匹配cuda内存不足张量类型不匹配 参考 PyTorch文档查看https://pytorch.org/docs/stable/ torch.nn -> 定义神经网络 torc…
阅读更多...
【C++】auto的解释

【C++】auto的解释

auto 是 C 中的类型推断关键字。它让编译器自动推导变量的类型。使用 auto 可以使代码更简洁&#xff0c;尤其在处理复杂类型时特别有用。 auto 提高了代码的灵活性和可读性&#xff0c;特别是在类型复杂或需要保持一致性的情况下。 主要用法&#xff1a; 1.自动推导类型: …
阅读更多...
手写call、apply、bind

手写call、apply、bind

一、手写call const person {name:zhangsan} function foo(numA,numB){console.log(this)console.log(numA,numB)return numA numB }// 手写call Function.prototype.mycall function(thisArg,...args){ // 手写callconst key Symbol(key) // 唯一标识符thisArg[key] thi…
阅读更多...
小程序的右侧抽屉开关动画手写效果

小程序的右侧抽屉开关动画手写效果

<template><view><button click"openDrawer">打开抽屉</button><view v-if"showDrawer" class"drawer" :style"{ backgroundColor: bgColor }" click"closeDrawer"><view class"draw…
阅读更多...
docker 重启容器且修改服务映射端口

docker 重启容器且修改服务映射端口

要重启 Docker 容器并修改服务的映射端口，可以按照以下步骤进行操作： 1. 停止当前运行的容器 如果你想重新配置端口，通常需要先停止当前运行的容器。你可以使用以下命令停止容器： docker stop <container_name_or_id>2. 删除现有容器 为了修改端口映射，你需要删…
阅读更多...
AI应用 | 超好玩的“汉语新解“ - 文末有Prompt

AI应用 | 超好玩的“汉语新解“ - 文末有Prompt

最近群里玩“汉语新解”的文字卡片贼多 感觉很新颖 本来AI是无法生成固定的图的 但是使用html格式&#xff0c;来生成固定图片的想法还是很不错的 看看效果 使用很简单 把提示词喂给Ai即可 随便一个大模型都可以&#xff0c;比如ChatGPT、通义千问、kimi等等 提示词(Prompt)如下…
阅读更多...
关于linux里的df命令以及inode、数据块-stat链接数以及关于awk文本处理命令中内置函数sub、gsub、sprintf

关于linux里的df命令以及inode、数据块-stat链接数以及关于awk文本处理命令中内置函数sub、gsub、sprintf

一、关于linux里的df命令以及inode、数据块-stat链接数 Linux中df命令用于显示目前在Linux系统上的文件系统的磁盘使用情况统计&#xff0c;平常这个命令也用得很多&#xff0c;但一般就是使用df -h查看各个分区的空间使用情况&#xff0c;除此外也可以使用df查看当前linux系统…
阅读更多...
多张GPU卡

多张GPU卡

from transformers import pipeline from accelerate import init_empty_weights, infer_auto_device_map from transformers import AutoModelForCausalLM, AutoTokenizer 初始化加速器 from accelerate import Accelerator accelerator Accelerator() 加载模型和 tokeni…
阅读更多...
OpenCVSharp直方图和傅里叶变换介绍

OpenCVSharp直方图和傅里叶变换介绍

文章目录 1. 直方图计算2. 傅里叶变换3. 直方图均衡化4. 傅里叶逆变换5. 直方图匹配1. 直方图计算 直方图是图像处理中常用的工具，用于表示图像中像素值的分布情况。OpenCVSharp 提供了 Cv2.CalcHist 方法来计算图像的直方图。 详细介绍   直方图计算可以帮助我们了解图像的…
阅读更多...
菜鸟入门Docker

菜鸟入门Docker

初始Docker Docker的概念 Docker的用途 DOcke的安装 Docker架构 配置Docker镜像加速器 Docker常用命令 Docker服务相关的命令。 Docker镜像相关的命令 Docker容器相关的命令 容器的数据卷 数据卷的概念和作用 配置数据卷 Docker应用部署 Docker部署mysql Docker…
阅读更多...
Java怎么把多个对象的list的数据合并

Java怎么把多个对象的list的数据合并

1.示例一&#xff1a;创建几个包含Person对象的List&#xff0c;并将它们合并成一个新的List 在Java中&#xff0c;将多个对象的List合并通常涉及到遍历这些List并将它们的元素添加到一个新的List中。这里&#xff0c;我将给出一个详细的代码示例&#xff0c;该示例将展示如何…
阅读更多...
项目管理：如何确保目标的实现？

项目管理：如何确保目标的实现？

李华作为项目经理&#xff0c;正引领团队研发一款的智能系统。面对项目的复杂性和紧迫性&#xff0c;李华决定引入进度猫这一项目管理工具&#xff0c;以确保项目目标的顺利实现。 1、明确目标与愿景 在项目启动之初&#xff0c;李华组织了一次全面的项目规划会议。 会上&am…
阅读更多...
React 项目中使用 axios 进行 HTTP 请求时，封装 get、put、post 等请求方法

React 项目中使用 axios 进行 HTTP 请求时，封装 get、put、post 等请求方法

在 React 项目中使用 axios 进行 HTTP 请求时&#xff0c;你可以封装 get、put、post 等请求方法&#xff0c;使代码更简洁、复用性更高。尤其是对于 GET 请求&#xff0c;需要将对象参数解析并拼接到 URL 中。 以下是封装 axios 请求的一个简单示例&#xff0c;包括如何处理 …
阅读更多...
laravel 11 区分多模块的token

laravel 11 区分多模块的token

数据表&#xff1a;用户表&#xff08;users&#xff09;、管理员表&#xff08;admin_user&#xff09;&#xff0c; 配置bootstrap/app.php guards > [web > [driver > session,provider > admin_users,],home > [driver > sanctum,provider > users,]…
阅读更多...
Sentence-BERT实现文本匹配【CoSENT损失】

Sentence-BERT实现文本匹配【CoSENT损失】

引言 还是基于Sentence-BERT架构&#xff0c;或者说Bi-Encoder架构&#xff0c;但是本文使用的是苏神提出的CoSENT损失函数1。 点击来都是缘分&#xff0c;之前过时的方法可以不细看&#xff0c;别的文章可以不收藏&#xff0c;现在是最流行的方法&#xff0c;这篇文章建议收藏…
阅读更多...
App推广新姿势：Xinstall带你玩转安装页面拉起功能！

App推广新姿势：Xinstall带你玩转安装页面拉起功能！

在移动互联网时代&#xff0c;App已经成为我们生活中不可或缺的一部分。然而&#xff0c;随着App数量的不断增加&#xff0c;如何让自己的App在众多竞争者中脱颖而出&#xff0c;成为推广者面临的一大难题。今天&#xff0c;我们就来聊聊一个神奇的解决方案——Xinstall&#x…
阅读更多...
项目日志——日志器模块一部缓冲区的设计、实现、测试

项目日志——日志器模块一部缓冲区的设计、实现、测试

文章目录 异步缓冲区模块模块设计缓冲区设计单个缓冲区 实现测试 异步缓冲区模块 模块设计 异步日志器的思想是为了避免业务线程因为写日志的过程时间较长而长时间阻塞 异步日志器的工作就是把业务输出的日志内容放入内存缓冲区中&#xff0c;使用专门的线程进行日志写入 这…
阅读更多...
C2免杀--手工shellcode编译，shellcode免杀思路

C2免杀--手工shellcode编译，shellcode免杀思路

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文主要整理C2免杀中 shellcode代码免杀的相关部分 shellcode概念 我们也不啰嗦&#xff0c;我直接直观的描述一下他。 他就是一串机器能运行的代码&#xff0c;但是他不是正统的python&#xff0c;c&#xff…
阅读更多...
vulhub spring 远程命令执行漏洞（CVE-2022-22963）

vulhub spring 远程命令执行漏洞（CVE-2022-22963）

1.打开环境 进入环境所在的文件夹 docker-compose up -d 一键启动容器 2.浏览器访问环境 3.抓包 http://192.168.10.233:8080/functionRouter进行抓包 抓包修改请求方式 4.修改请求体内容 spring.cloud.function.routing-expression: T(java.lang.Runtime).getRuntime().e…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站