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模拟实现
一、概念 概念:红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍&a…...
AUTOSAR规范与ECU软件开发(实践篇)10.4、AP和CP
目录 1、AP和CP 1、AP和CP 自适应AUTOSAR平台(AP) 并不是传统经典AUTOSAR平台(CP) 的替代品, 不同的版本可同时存在于同一个车辆中, 两个ECU间可通过一些途径, 例如以太网, 将经典应用和自适应性应用进行无缝衔接。 简单而言, 两者的应用场景不太一样: 经典AUTOSAR平…...
css 命名规则
一个有规则的命名 会提高代码的可读性 一、命名规则说明: 1)、所有的命名最好都小写 2)、属性的值一定要用双引号(“”)括起来 3)、给图片加上alt标签 4)、尽量使用英文命名原则 5)、尽量不缩写࿰…...
正中优配:旅游餐饮板块走高,曲江文旅涨停,西安旅游等拉升
旅行餐饮板块7日盘中拉升走高,截至发稿,曲江文旅涨停,西安旅行涨超5%,君亭酒店、华天酒店、国旅联合、宋城演演艺等均上扬。 中国旅行研究院数据显现,今年暑期国内旅行人数达18.39亿人次,占全年国内旅行出…...
世界青岛中国海洋大学金秋悦读《乡村振兴战略下传统村落文化旅游设计》2023新学年许少辉八一新书
世界青岛中国海洋大学金秋悦读《乡村振兴战略下传统村落文化旅游设计》2023新学年许少辉八一新书...
15 | Spark SQL 的 SQL API 操作
SQL API:Spark SQL 允许使用标准 SQL 语句来查询和分析数据。用户可以通过 SparkSession 执行 SQL 查询,并将结果返回为 DataFrame。这使得熟悉 SQL 的用户能够方便地使用 Spark SQL 进行数据处理。 示例 1: 基本查询 执行基本的 SQL 查询,选择数据中的特定列并过滤数据。…...
为什么工作流中围绕XML做EDI报文数据解析/生成?
经常有客户问起,为什么在处理EDI文件时不一次到位,而需要使用多个端口来分次进行处理呢,是不是想要多占用几个端口好多卖钱呀? 实际上,在一开始的知行EDI产品中,功能还没有这么完善,当时只支持…...
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 测试中的一个函数,用于重置测试环境。它通常与 initTestEnvironment 和 platformBrowserDynamicTesting 一起使用,以确保在多个测试套件之间正确清理和重置 Angular 测试环境。 这是 resetTestEnvironment 函数的形式…...
mfc 浮动窗口
参考 MFC模拟360悬浮窗加速球窗口...
【C++漂流记】函数的高级应用——函数默认参数、占位参数、重载
函数的高级应用,侧重介绍函数的默认参数、函数的占位参数、函数重载定义解释及使用。 文章目录 一、函数的默认参数二、函数的占位参数三、函数重载函数重载的注意事项 一、函数的默认参数 函数默认参数是指在函数声明时为参数提供一个默认值,这样在调…...
Java——》synchronized的原理
推荐链接: 总结——》【Java】 总结——》【Mysql】 总结——》【Redis】 总结——》【Kafka】 总结——》【Spring】 总结——》【SpringBoot】 总结——》【MyBatis、MyBatis-Plus】 总结——》【Linux】 总结——》【MongoD…...
CPU主频
CPU主频,也称为时钟频率,是指中央处理单元(CPU)的工作时钟的速度,通常以赫兹(Hz)为单位表示。它表示CPU每秒钟执行的时钟周期数。CPU主频是CPU性能的一个重要指标之一,但不是唯一的性…...
PHP8中查询数组中指定元素-PHP8知识详解
php是使用最广泛的web编程语言,数组是一个数据集合,数组是一种非常常用的数据类型。在操作数组时,有时我们需要查询数组中是否有某个指定元素。在实际的程序开发中,我们用到了下列方法来查询数组中指定的元素:使用arra…...
在Git中将本地分支推送到远程仓库
这里很明显 我git云端只有一个master分支 然后 我在本地创建了一个develop分支 然后 现在我想将他放在云端 首先 我们要执行 git checkout -b develop将本地切换到 develop 分支上 因为我这里已经选择的就是了 就不需要了 然后我们执行 git push origin develop这样 刷新云…...
【数据仓库基础(四)】数据仓库需求:基本需求和数据需求
文章目录 一. 基本需求1. 安全性2. 可访问性3. 自动化 三. 数据需求1. 准确性2.时效性3.历史可追溯性 从基本需求和数据需求两方面介绍对数据仓库系统的整体要求。 一. 基本需求 1. 安全性 数据仓库中含有机密和敏感的数据。为了能够使用这些数据&…...
C++类模板是一种通用的编程工具,可以创建可以适用于多种数据类型的类
C类模板是一种通用的编程工具,可以创建可以适用于多种数据类型的类。它们允许在类定义中使用参数,以便根据需要实例化具体的类。使用C类模板时,首先需要定义模板。模板定义的语法如下:cpp template <typename T> class MyCl…...
Vite和Webpack如何使用CDN包
为了精简打包输出的dist目录大小,我们可以引入CDN外部包的方式,来缩小打包的体积,加快打包速度。这里介绍Vite和Webpack中如何引入React CDN外部包。 一、Vite引入CDN包 1、安装插件 npm i vitejs/plugin-react-refresh vite-plugin-cdn-i…...
TOWE雷达光敏感应开关,让生活更智能、更安全
现代生活中,智能家居成为人们追求品质生活的必备之选。其中,照明控制的智能化已然成为一种趋势,传统的灯光开关需要人们手动操作,既不方便,有时候也会造成资源的过度浪费,而雷达光敏感应开关的出现…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
