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

RBTree模拟实现

一、概念

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

性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的,则它的两个孩子结点必须是黑色的
4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点 NIL结点)

问题:

如何做到最长路径<=2*最短路径?

不能连续红色+root为黑+每条路径黑结点数相同。

AVL和RBT性能对比:搜索->io

搜索/查找时:同一量级

插入/删除:

AVL树,插入删除时,因为要控制严格平衡,会进行大量旋转操作。        

二、结点的定义

三、Insert

寻找插入位置

先查找要插入的位置,_root根节点颜色默认为BLACK。

插入新结点的颜色为RED。

这是为了满足性质4,如果新结点为BLACK,会影响所有路径,相当于其它路径的黑结点数都距离目标个数缺少1个。

新结点为RED,只用满足性质3不是连续红结点即可。

则只需调整其祖先结点,并关注uncle结点颜色即可。

1、uncle存在且为红

2、uncle不存在

3、uncle存在且为黑

4、代码实现

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else return false;}cur = new Node(kv);cur->_col = RED; if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}//每次新增newnode,要初始化它的_parent指针  三叉链cur->_parent = parent;//parent为红才需要调整while (parent && parent->_col == RED){Node* ppnode = parent->_parent;//1、uncle存在且为红//2、uncle不存在//3、uncle存在且为黑if (parent == ppnode->_left){Node* uncle = ppnode->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;ppnode->_col = RED;//继续向上调整cur = ppnode;parent = cur->_parent;//没有父亲则cur为根,直接变黑即可}else if (uncle == nullptr || (uncle && uncle->_col == BLACK)){//uncle不变色,2种情况可以合成一种if (cur == parent->_left){//     pp//   p 	  //cRotateR(ppnode);parent->_col = BLACK;ppnode->_col = RED;}else{//     pp//   p 	  //		cRotateL(parent);RotateR(ppnode);cur->_col = BLACK;ppnode->_col = RED;}break;//只要旋转完就break}	}else{Node* uncle = ppnode->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;ppnode->_col = RED;//继续向上调整cur = ppnode;parent = cur->_parent;//没有父亲则cur为根,直接变黑即可}else if (uncle == nullptr || uncle && uncle->_col == BLACK){//uncle不变色,2种情况可以合成一种if (cur == parent->_right){//     pp//   u    p 	  //			cRotateL(ppnode);ppnode->_col = RED;parent->_col = BLACK;}else{//     pp//   u	  p 	  //		cRotateR(parent);RotateL(ppnode);cur->_col = BLACK;ppnode->_col = RED;}break;//只要旋转完就break}}}_root->_col = BLACK;return true;}

四、IsBalance检验是否平衡

必须在满足是红黑树的条件下,检验其所有性质。

1、若简单的计算最长路径和最短路径,可能会出现连续RED的情况,不满足。

2、遍历所有路径,统计每条路径黑结点的个数,看是否都相同,遍历过程可以检查是否存在连续RED结点。

相关文章:

RBTree模拟实现

一、概念 概念&#xff1a;红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长出俩倍&a…...

AUTOSAR规范与ECU软件开发(实践篇)10.4、AP和CP

目录 1、AP和CP 1、AP和CP 自适应AUTOSAR平台(AP) 并不是传统经典AUTOSAR平台(CP) 的替代品, 不同的版本可同时存在于同一个车辆中, 两个ECU间可通过一些途径, 例如以太网, 将经典应用和自适应性应用进行无缝衔接。 简单而言, 两者的应用场景不太一样: 经典AUTOSAR平…...

css 命名规则

一个有规则的命名 会提高代码的可读性 一、命名规则说明&#xff1a; 1&#xff09;、所有的命名最好都小写 2&#xff09;、属性的值一定要用双引号(“”)括起来 3&#xff09;、给图片加上alt标签 4&#xff09;、尽量使用英文命名原则 5&#xff09;、尽量不缩写&#xff0…...

正中优配:旅游餐饮板块走高,曲江文旅涨停,西安旅游等拉升

旅行餐饮板块7日盘中拉升走高&#xff0c;截至发稿&#xff0c;曲江文旅涨停&#xff0c;西安旅行涨超5%&#xff0c;君亭酒店、华天酒店、国旅联合、宋城演演艺等均上扬。 中国旅行研究院数据显现&#xff0c;今年暑期国内旅行人数达18.39亿人次&#xff0c;占全年国内旅行出…...

世界青岛中国海洋大学金秋悦读《乡村振兴战略下传统村落文化旅游设计》2023新学年许少辉八一新书

世界青岛中国海洋大学金秋悦读《乡村振兴战略下传统村落文化旅游设计》2023新学年许少辉八一新书...

15 | Spark SQL 的 SQL API 操作

SQL API:Spark SQL 允许使用标准 SQL 语句来查询和分析数据。用户可以通过 SparkSession 执行 SQL 查询,并将结果返回为 DataFrame。这使得熟悉 SQL 的用户能够方便地使用 Spark SQL 进行数据处理。 示例 1: 基本查询 执行基本的 SQL 查询,选择数据中的特定列并过滤数据。…...

为什么工作流中围绕XML做EDI报文数据解析/生成?

经常有客户问起&#xff0c;为什么在处理EDI文件时不一次到位&#xff0c;而需要使用多个端口来分次进行处理呢&#xff0c;是不是想要多占用几个端口好多卖钱呀&#xff1f; 实际上&#xff0c;在一开始的知行EDI产品中&#xff0c;功能还没有这么完善&#xff0c;当时只支持…...

C++的运算符重载介绍

所谓重载,就是赋予新的含义。函数重载(Function Overloading)可以让一个函数名有多种功能,在不同情况下进行不同的操作。运算符重载(Operator Overloading)也是一个道理,同一个运算符可以有不同的功能。 实际上,我们已经在不知不觉中使用了运算符重载。例如,+号可以对…...

C++vector的使用

vector的使用 1.vector的介绍2.vector的使用3.Member functions3.1构造函数3.2拷贝构造3.3赋值运算符重载 4.iterator5.capacity6.Element access7.增删查改7.1增7.2删7.3查7.4改 1.vector的介绍 1.vector是表示可变大小数组的序列容器. 2.vector也采用连续空间存储元素&#x…...

angular测试API

1.resetTestEnvironment 是 Angular 测试中的一个函数&#xff0c;用于重置测试环境。它通常与 initTestEnvironment 和 platformBrowserDynamicTesting 一起使用&#xff0c;以确保在多个测试套件之间正确清理和重置 Angular 测试环境。 这是 resetTestEnvironment 函数的形式…...

mfc 浮动窗口

参考 MFC模拟360悬浮窗加速球窗口...

【C++漂流记】函数的高级应用——函数默认参数、占位参数、重载

函数的高级应用&#xff0c;侧重介绍函数的默认参数、函数的占位参数、函数重载定义解释及使用。 文章目录 一、函数的默认参数二、函数的占位参数三、函数重载函数重载的注意事项 一、函数的默认参数 函数默认参数是指在函数声明时为参数提供一个默认值&#xff0c;这样在调…...

Java——》synchronized的原理

推荐链接&#xff1a; 总结——》【Java】 总结——》【Mysql】 总结——》【Redis】 总结——》【Kafka】 总结——》【Spring】 总结——》【SpringBoot】 总结——》【MyBatis、MyBatis-Plus】 总结——》【Linux】 总结——》【MongoD…...

CPU主频

CPU主频&#xff0c;也称为时钟频率&#xff0c;是指中央处理单元&#xff08;CPU&#xff09;的工作时钟的速度&#xff0c;通常以赫兹&#xff08;Hz&#xff09;为单位表示。它表示CPU每秒钟执行的时钟周期数。CPU主频是CPU性能的一个重要指标之一&#xff0c;但不是唯一的性…...

PHP8中查询数组中指定元素-PHP8知识详解

php是使用最广泛的web编程语言&#xff0c;数组是一个数据集合&#xff0c;数组是一种非常常用的数据类型。在操作数组时&#xff0c;有时我们需要查询数组中是否有某个指定元素。在实际的程序开发中&#xff0c;我们用到了下列方法来查询数组中指定的元素&#xff1a;使用arra…...

在Git中将本地分支推送到远程仓库

这里很明显 我git云端只有一个master分支 然后 我在本地创建了一个develop分支 然后 现在我想将他放在云端 首先 我们要执行 git checkout -b develop将本地切换到 develop 分支上 因为我这里已经选择的就是了 就不需要了 然后我们执行 git push origin develop这样 刷新云…...

【数据仓库基础(四)】数据仓库需求:基本需求和数据需求

文章目录 一. 基本需求1. 安全性2. 可访问性3. 自动化 三. 数据需求1. 准确性2&#xff0e;时效性3&#xff0e;历史可追溯性 从基本需求和数据需求两方面介绍对数据仓库系统的整体要求。 一. 基本需求 1. 安全性 数据仓库中含有机密和敏感的数据。为了能够使用这些数据&…...

C++类模板是一种通用的编程工具,可以创建可以适用于多种数据类型的类

C类模板是一种通用的编程工具&#xff0c;可以创建可以适用于多种数据类型的类。它们允许在类定义中使用参数&#xff0c;以便根据需要实例化具体的类。使用C类模板时&#xff0c;首先需要定义模板。模板定义的语法如下&#xff1a;cpp template <typename T> class MyCl…...

Vite和Webpack如何使用CDN包

为了精简打包输出的dist目录大小&#xff0c;我们可以引入CDN外部包的方式&#xff0c;来缩小打包的体积&#xff0c;加快打包速度。这里介绍Vite和Webpack中如何引入React CDN外部包。 一、Vite引入CDN包 1、安装插件 npm i vitejs/plugin-react-refresh vite-plugin-cdn-i…...

TOWE雷达光敏感应开关,让生活更智能、更安全

现代生活中&#xff0c;智能家居成为人们追求品质生活的必备之选。其中&#xff0c;照明控制的智能化已然成为一种趋势&#xff0c;传统的灯光开关需要人们手动操作&#xff0c;既不方便&#xff0c;有时候也会造成资源的过度浪费&#xff0c;而雷达光敏感应开关的出现&#xf…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...