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

【红黑树】红黑树插入操作相关的细节和疑难拆解分析

本文就红黑树的插入操作进行细致到每一个小步骤的解析。

1,成员变量

本红黑树使用了三叉链结构,使用的时候尤其要记得处理指向父亲的指针。

为何在节点的构造函数中,默认节点的颜色为红色?

因为考虑到红黑树的性质(对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点),所以设置为红色是最为合理方便的,如果插入的时候会有连续的红色节点,再做调整也很方便。

但是如果默认为黑节点,就要做调整保证每个路径上的黑节点相同,相比之下会很麻烦。

2,Insert函数的实现(分为各个细节讨论)

2,1插入时,红黑树是否为空树

考虑到此情况,要先判断红黑树是否为空树。

若是,进行相关操作后return

若不是,向下进行

2,2若不是空树,迭代到树的底部,并插入节点

不必担心parent的空指针解引用问题,由于不是空树,所以parent一定不会为nullptr。

2,3插入节点后,控制平衡

理论基础:

理论:(我们先约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点)

情况一: cur为红,p为红,g为黑,u存在且为红

如下图:

此图是个抽象图,代表着多种情况,带省略号的长方形表示一个未知的树。

解决方法:

将p,u改为黑,g改为红,然后把g当成cur,继续向上调整

如果g是根节点,调整完成后,需要将g改为黑色(其实只要在调整操作的最后将_root的颜色置为黑色就行,不必在每种情况下特殊处理)

如果g是子树,g一定有双亲,且g的双亲如果是红色,需要继续向上调整。

——————————————————————————————————————

情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑,且为单旋情况

如下图:

如下图:

解决方法:

p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,

p为g的右孩子,cur为p的右孩子,则进行左单旋转

p、g变色--p变黑,g变红

旋转函数:

1,左单旋

解释:

要实现一个操作,往往有多种方法,函数的设计也有多种。

本人选择将旋转函数参数统一设置为要处理的两个节点中处于上方的节点。

如图:

于是,写出代码实现如下:

cur是node的右子节点,parent是node的父节点。

要特别注意,此时使用的是三叉链结构,在链接节点的同时,一定不要忘记对_parent进行处理

在对_parent进行处理时,当然也要注意_parenrt是否存在,所以我们还要判断node是否为根节点,再进行相关操作。

2,右单旋

分析同上,不在赘述。

如下图:

代码实现:

————————————————————————————————————————

在插播了左单旋和右单旋的实现后,继续回来讨论第三种情况

情况三:cur为红,p为红,g为黑,u不存在/u存在且为黑,且需要双旋

有了以上基础,此处直接上图。

解决方法:

p为g的左孩子,cur为p的右孩子,则针对p做左单旋转,再对g做右单旋转;相反,

p为g的右孩子,cur为p的左孩子,则针对p做右单旋转,再对g做左单旋转。

将cur置为黑色,g置为红色

代码实现:

复用左单旋和右单旋即可。

代码实现:

解释:

整个循环结束的条件是parent不存在或者parent为黑色

并且不必担心祖父是否存在,因为如果parent && parent->_col == RED的话,

祖父节点一定存在,并且为黑色,因为parent为红色节点,不可能是根节点。

如果是第一种情况的话,是需要迭代调整的:要将g的位置变为cur,继续向上检查。

而第二三种情况则不需要,因为旋转了之后,没有对上层产生影响,所以可以在调整之后直接跳出

循环结束后,将_root置为黑色,保证结构即可。

相关文章:

【红黑树】红黑树插入操作相关的细节和疑难拆解分析

本文就红黑树的插入操作进行细致到每一个小步骤的解析。1,成员变量本红黑树使用了三叉链结构,使用的时候尤其要记得处理指向父亲的指针。为何在节点的构造函数中,默认节点的颜色为红色?因为考虑到红黑树的性质(对于每个…...

字符串匹配--strstr函数的模拟实现思路和代码

一,strstr函数 原型: const char * strstr ( const char * str1, const char * str2 );char * strstr ( char * str1, const char * str2 ); strstr是一个字符串匹配函数,在str1中去寻找str2,如果找到,返回str2在…...

【ArcGIS Pro二次开发】(7):地图(Map)的基本操作

地图是ArcGIS Pro中的基础起点,也是大多数工程的基础。主要用于显示表示空间数据的图层。 一、地图(Map)的基本操作示例 1、获取当前地图 var map MapView.Active.Map; 2、获取一级图层 var lys map.Layers; 用于获取地图中的单一图层,以及图层组…...

python 自动化测试 pytest 的使用

pytest 是一款以python为开发语言的第三方测试,主要特点如下: 比自带的 unittest 更简洁高效,兼容 unittest框架 支持参数化 可以更精确的控制要测试的测试用例 丰富的插件,已有300多个各种各样的插件,也可自定义扩…...

闭包(回顾)

概念作用保护作用保存作用优缺点命名空间 概念 闭包(closure)指有权访问另一个函数作用域中变量的函数 — Javacript高级程序设计 p309 简单理解,一个作用域可以访问另一个函数内部的私有变量 // 其中 test就是一个闭包 function fn(){var num 10function test …...

利用好这两个方法,服务型企业缺成本票不再难解决!

现代服务业属于人才密集型和技术型类别,其中囊括了不少技术,知识,智力服务等产业:信息技术,文化创意,营销策划,广告设计,以及咨询,商务和法律服务。 在金税三期完善之前…...

前端面试编程题(异步调度,Promise实现、占用空间大小、渲染虚拟节点、实现for of)

目录 异步调度问题 题目一 答案 题目二 答案 递归输出 题目一 答案 Promise相关 题目一 答案 占用空间大小 题目一 答案 渲染虚拟节点 题目一 答案 实现for of 题目一 答案 异步调度问题 题目一 1.实现一个带并发限制的异步调度Scheduler,保证同…...

复旦团队发布国内首个模型MOSS 类ChatGPT

复旦团队发布国内首个模型MOSS 类ChatGPT 首先看到这个标题,还有这个名字,我是正经(zhen jing)的 (bu shi 流浪地球?550W?不了解的可以把550W倒过来写,就懂了 看到新闻里的一些图…...

5.35 综合案例2.0 -称重数据上传云端

综合案例2.0 - 称重数据上传云端案例说明连线功能实现1.阿里云平台连接代码应用开发3.1新建‘普通项目’3.2关联产品和设备3.3新建‘移动应用’3.4添加组件3.5配置组件信息3.6保存预览案例说明 使用hx711串口模块称重,结合IOT studio制作手机APP远程控制并采集物体重量。 hx7…...

如何让人机对话更自然?

来源:投稿 作者:顾相欢 编辑:学姐 AAAI-2022|定制对话的人设和知识背景 原文标题: Call for Customized Conversation: Customized Conversation Grounding Persona and Knowledge 原文链接: https://arxiv.org/ab…...

Python每日一练(20230224)

目录 1. 列表奇偶拆分 ★ 2. 二叉树的后序遍历 ★★ 3. 接雨水 ★★★ 附录 二叉树 特点 性质 特殊二叉树 满二叉树 完全二叉树 完全二叉树性质 二叉树的遍历 1. 列表奇偶拆分 【问题描述】 输入一个列表,包含若干个整数(允许为空&#xff…...

【Linux】-- Shell的运行原理、Linux当中的权限

目录 Shell的运行原理 Linux权限的概念 su命令 权限 文件访问权限的相关设置方法 chmod指令 chown指令 chgrp指令 sudo命令 文件的常见问题 umask 粘滞位 关于权限的总结 Shell的运行原理 Shell运行原理 —— 外壳程序。 Linux严格意义上说的是一个操作系统&…...

MOS管选型参数:VGS(th)

MOS管选型参数:VGS(th) VGS(th):开启电压(阀值电压)。当外加栅极控制电压 VGS 超过 VGS(th) 时,漏区和源区的表面反型层形成了连接的沟道。应用中,常将漏极短…...

二.线性表之顺序表

文章目录前言一.顺序表的概念及结构二.顺序表的接口实现1.顺序表的动态存储2.顺序表的初始化3.顺序表尾插#封装:扩容函数4.顺序表尾删5.顺序表头插6.顺序表头删7.顺序表查找8.顺序表在pos位置插入x9.顺序表删除pos位置的值10.顺序表销毁11.顺序表打印三.源1.Seqlist…...

ElasticSearch - SpringBoot整合ElasticSearch实现文档的增删改

文章目录1. ElasticSearch和kibana的安装和配置2. SpringBoot 项目环境搭建3. 创建索引4. 索引文档5. 更新文档6. 删除文档https://www.elastic.co/guide/en/elasticsearch/reference/current/search-your-data.htmlhttps://www.elastic.co/guide/cn/elasticsearch/guide/curre…...

JavaScript 库

文章目录JavaScript 库JavaScript 框架(库)jQueryPrototypeMooTools其他框架CDN -内容分发网络引用 jQuery使用框架JavaScript 库 JavaScript 库 - jQuery、Prototype、MooTools。 JavaScript 框架(库) JavaScript 高级程序设计…...

云解析DNS为什么要配置默认线路?

传统解析技术不会判断访客IP,而是会随机选择一个IP返回给访问者,这样就有可能造成移动用户访问电信服务器IP,北京用户访问深圳服务器IP这种跨域跨网访问的情况,产生非常大的延迟,带来很不好的访问体验。 而云解析DNS会…...

Linux命令之awk

awk是一个有强大的文本格式化能力的linux命令,早期是在Unix上实现的,linux后来也可以使用了,我们在Linux上使用的awk是gawk(GNU awk的意思) 语法 awk [option] 模式{动作} file option表示awk的可选参数,可…...

实战-缓存数据一致+binlog初始+cannel监听+数据迁移,数据一致性架构设计

前言 一. 解决缓存不命中(高并发操作击穿打挂DB的风险) 当并发量打的时候,当我们的缓存过期时,就算到数据库的比例偏小的时候,我们的请求时比较大的。那也会存在数据库崩掉的情况。解决方案想法如下(总体…...

nginx配置中proxy_pass反向代理502的bug

记录一个坑人的bug, 我今天在一台新的liunx上运行nginx来进行反向代理时候,发现怎么测都是502 我把配置全部删了从头开始配置,发现80端口正常,80端口index.html正常,反向代理转向http://127.0.0.1/也正常,…...

云计算——弹性云计算器(ECS)

弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...