【C++ 】红黑树

1.1 红黑树的概念

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

在这里插入图片描述

2. 红黑树的性质

在这里插入图片描述

// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{RBTreeNode(const ValueType& data = ValueType(),Color color = RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNode<ValueType>* _pLeft;   // 节点的左孩子RBTreeNode<ValueType>* _pRight;  // 节点的右孩子RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转,为了实现简单给
出该字段)ValueType _data;            // 节点的值域Color _color;               // 节点的颜色
};

3. 红黑树结构

为了后续实现关联式容器简单,红黑树的实现中增加一个头结点,因为跟节点必须为黑色,为了
与根节点进行区分,将头结点给成黑色,并且让头结点的 pParent 域指向红黑树的根节点,pLeft
域指向红黑树中最小的节点,_pRight域指向红黑树中最大的节点,如下:

在这里插入图片描述

4. 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

  1. 按照二叉搜索的树规则插入新节点
template<class ValueType>
class RBTree
{//……bool Insert(const ValueType& data){PNode& pRoot = GetRoot();if (nullptr == pRoot){pRoot = new Node(data, BLACK);// 根的双亲为头节点pRoot->_pParent = _pHead;_pHead->_pParent = pRoot;}else{// 1. 按照二叉搜索的树方式插入新节点// 2. 检测新节点插入后,红黑树的性质是否造到破坏,//   若满足直接退出,否则对红黑树进行旋转着色处理}// 根节点的颜色可能被修改,将其改回黑色pRoot->_color = BLACK;_pHead->_pLeft = LeftMost();_pHead->_pRight = RightMost();return true;}
private:PNode& GetRoot(){ return _pHead->_pParent;}// 获取红黑树中最小节点,即最左侧节点PNode LeftMost();// 获取红黑树中最大节点,即最右侧节点PNode RightMost();
private:PNode _pHead;

在这里插入图片描述
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/326415.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

RabbitMQ的用途

RabbitMQ主要有四个用途&#xff0c;分别是应用解耦、异步提速、削峰填谷、消息分发。详情讲解如下&#xff1a; RabbitMQ介绍、解耦、提速、削峰、分发 详解、RabbitMQ安装 可视化界面讲解 1.应用解耦&#xff1a;提高系统容错性和可维护性 2.异步提速&#xff1a;提升用户体验…

自动驾驶系统中的数据闭环:挑战与前景

目录 自动驾驶概况 1.1自动驾驶分级 1.2自动驾驶国内发展 ​1.3自动驾驶架构模型 数据闭环的意义 2.1 搜集corner case的数据 2.2 提高模型的泛化能力 2.3 驱动算法迭代 数据闭环落地的痛点及对策 3.1 数据采集和使用的合规性问题 3.2 数据确权问题 3.3 数据采集…

101_Linux文件挂载系统相关

一、文件系统简介 传统的磁盘与文件系统应用中,一个分区就只能够被格式化成为一个文件系统,所以我们可以说一个文件系统就是一个硬盘分区。 随着新技术的出现如LMM与软件磁盘阵列software raid),这些技术可以将一个分区格式化为多个文件系统(例如LWM),也能够将多个分区合成一…

第十二讲:指针(4)

第十二讲&#xff1a;指针&#xff08;4&#xff09; 1.回调函数1.1什么是回调函数1.2深入理解并使用回调函数1.2.1简单写法1.2.2优化 2.qsort函数详解2.1函数简单介绍2.3qsort函数使用举例2.3.1qsort函数排序整形数据2.3.2qsort函数排序结构数据 3.qsort函数的模拟实现3.1冒泡…

免费PDF批量加密工具

最近在找PDF批量加密的软件来着&#xff0c;发现很多都是需要收费的&#xff0c;当然如果平时工作需要用的比较多&#xff0c;支持一下还是ok的&#xff0c;但是多数人还是偶尔用一下所以没有必要买。 工作用的话&#xff0c;一般企业文件、个人隐私资料、重要合同...所有重要文…

嘎嘎好用的虚拟键盘第二弹之中文输入法

之前还在为不用研究输入中文而暗自窃喜 这不新需求就来了&#xff08;新需求不会迟到 它只是在路上飞一会儿&#xff09; 找到了个博主分享的代码 是好使的 前端-xyq 已经和原作者申请转载了 感谢~~ 原作者地址&#xff1a;https://www.cnblogs.com/linjiangxian/p/16223681.h…

OpenAI推出DALL·E 3识别器、媒体管理器

5月8日&#xff0c;OpenAI在官网宣布&#xff0c;将推出面向其文生图模型DALLE 3 的内容识别器&#xff0c;以及一个媒体管理器。 随着ChatGPT、DALLE 3等生成式AI产品被大量应用在实际业务中&#xff0c;人们越来越难分辨AI和人类创建内容的区别&#xff0c;这个识别器可以帮…

NSSCTF | [LitCTF 2023]我Flag呢?

这道题没啥好说的&#xff0c;题目标签为源码泄露&#xff0c;我们直接CtrlU查看网页源码就能在最后找到flag 本题完

如何用微信小程序实现远程控制4路控制器/断路器

如何用微信小程序实现远程控制4路控制器/断路器呢&#xff1f; 本文描述了使用微信小程序调用HTTP接口&#xff0c;实现控制4路控制器/断路器&#xff0c;支持4路输出&#xff0c;均可独立控制&#xff0c;可接入各种电器。 可选用产品&#xff1a;可根据实际场景需求&#xf…

draw.io 网页版二次开发(1):源码下载和环境搭建

目录 一 说明 二 源码地址以及下载 三 开发环境搭建 1. 前端工程地址 2. 配置开发环境 &#xff08;1&#xff09;安装 node.js &#xff08;2&#xff09;安装 serve 服务器 3. 运行 四 最后 一 说明 应公司项目要求&#xff0c;需要对draw.io进行二次开发&…

福建医疗器械展/2024厦门国际医疗器械展览会重磅来袭

2024中国&#xff08;厦门&#xff09;国际医疗器械展览会 时 间&#xff1a;2024年11月1-3日 November 1-3, 2024 地 点&#xff1a;厦门国际会展中心 Xiamen International Conference & Exhibition Center ​ ◆组织机构 主办单位&#xff1a; 中国技术市场协会医…

Mysql-用户变量的声明与使用

#声明变量 #1.标识符不能以数字开头 #2.只能使用_或$符号&#xff0c;不能使用其他符号 #3.不能使用系统关键字 setuserName刘德华; select userName:刘青云;#将赋值与查询结合 #查询变量、使用变量&#xff0c;匿名的时候建议加上as select userName as 读取到的userName变量…

TriCore:Interrupt 2

今天继续来看看 IR 模块。 名词缩写 缩写全称说明IRInterrupt Router SRService Request 包括&#xff1a; 1. External Resource 2. Internal Resource 3.SW&#xff08;Software&#xff09; SPService Privoder 包括&#xff1a; 1. CPU 2. DMA SRNService Request NodeS…

【linux-IMX6ULL-uboot初次编译及烧录

目录 1. uboot基本概念1. 1 uboot的编译 3. uboot的烧录2. uboot的烧录结果 第一次不进行原理性的探究&#xff0c;也不关注源码内容&#xff0c;只是进行一个直观的了解&#xff0c;对uboot进行初次编译并进烧录到IMX6ULL板卡中 1. uboot基本概念 U-Boot&#xff08;Universa…

java项目之智慧图书管理系统设计与实现(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的智慧图书管理系统设计与实现。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 智慧图书管理…

GT2712-STBD 三菱触摸屏12.1寸型

GT2712-STBD 三菱触摸屏12.1寸型 GT2712-STBD参数说明&#xff1a;12.1型, SVGA, TFT彩色液晶屏 65536色, 黑色边框, 电源DC24V。 一、三菱触摸屏GT2712-STBD性能规格&#xff1a; [显示部*1*2] . 显示软元件:TFT彩色液晶屏 . GT2712-STBD画面尺寸:12.1寸 . GT2712-STBD…

六级翻译笔记

理解加表达 除了专有名词不能自己理解翻译&#xff0c;其它都可以 时态一般唯一 题目里出现有翻译为 客观存在&#xff1a; there be 单词结尾加er和ee的区别&#xff1a;er是主动&#xff0c;ee是被动 中文句子没有被动&#xff0c;也可以英文翻译为被动 中文的状语可以不是…

使用AudioCraft(MusicGen)生成音乐

AudioCraft 是一个 PyTorch 库,用于音频生成的深度学习研究。AudioCraft 包含两个先进的AI生成模型:AudioGen和MusicGen,它们共同致力于生成高质量的音频内容。 MusicGen是一个简单且可控的音乐生成模型。它利用Meta提供的20K小时授权音乐进行训练,能够根据文本描述或已有…

web后端——netbeans ide +jsp+servlet开发学习总结

目录 jsp基础 netbeans开发工具问题访问网页失败,404,not found 等?HTTP Status 405 - HTTP method POST is not supported......netbeans 提示无法启动GlassFish Server 4.1.1:服务器未运行时, HTTP 或 HTTPS 监听程序端口已被占用404 问题netbeans中项目中有多个html文件,如…

嵌入式RTOS面试题目

用过哪些嵌入式操作系统&#xff1f;使⽤RTOS和裸机代码开发有什么区别&#xff08;优缺点&#xff09;&#xff1f; 之前的⼀个项⽬是采⽤裸机代码开发的&#xff0c;写起来还⾏&#xff0c;通过状态机来管理业务逻辑和各种外设。 但是随着外设的增加&#xff0c;任务之间的…