当前位置: 首页 > 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/也正常,…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...