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

C++模拟实现红黑树

目录

介绍----什么是红黑树

 甲鱼的臀部----规定

分析思考

绘图解析+代码实现

节点部分

插入部分+分步解析

●父亲在祖父的左,叔叔在祖父的右:

●父亲在祖父的右,叔叔在祖父的左:

测试部分

整体代码


介绍----什么是红黑树

红黑树基于二叉搜索树,它和AVL树一样避免了二叉搜索树中极端场景单边树的情况,保证了检索的效率。红黑树允许最长路径是最短路径的二倍,相较于AVL树而言是近似于平衡的状态,但是减少了旋转的次数。

 甲鱼的臀部----规定

●每个节点都有颜色,不是红色就是黑色。

●根节点一定是黑色的。

●不能连续出现两个红色的节点。

●每条路径上的黑色节点数量相同。

●每个空节点都是黑色的。

●最多允许一条路径上的节点是另一条路径上节点的二倍。

分析思考

节点默认颜色应该选红色还是黑色,为什么?

答:插入红色可能会出现连续的红色节点,插入黑色会改变当前路径上的黑色节点数。选择默认插入节点为红色的原因是插入后的影响会小一些,当父节点是黑色时不用调整。相反的,黑色节点的插入一定会违反红黑树的规则。

满足上述特性为什么能保证最长路径不会超过最短路径的2倍?

答:这里要关注红黑树的两个特性,红色节点的孩子节点一定是黑色,每条路径的黑色节点树相同。也就说最长路径是红色节点和黑色交替,最短路径是全黑节点。这样一来,最长路径和最短路径间的差距就控制在了规定范围内。

绘图解析+代码实现

节点部分

三叉链结构分别指向左右孩子和父亲节点,数据方面存储键值对,除此之外还需要一个记录节点颜色的变量。

enum Color
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;Color _color;RBTreeNode(pair<K, V> kv, Color color = RED):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(color){}
};

插入部分+分步解析

红黑树是二叉搜索树,插入节点的规则和二叉搜索的特点一样:

   typedef RBTreeNode<K,V> Node;bool inster(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}//插入节点的位置cur = new Node(kv);cur->_color = RED;if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//节点插入后,需要检查红黑树的特性有没有被破坏掉//......}

上述我们谈论过新节点的颜色默认为红色的原因,那么接下来的插入如果新节点插入后其父节点的颜色是黑色,那么直接插入即可。如果其父节点的颜色为红色,那么就出现了两个红色节点出现的情况,此时就需要进行调整:

 

关注:红黑树的处理方法重点关注这样的几个节点:cur(新增节点)、parent(父亲节点)、uncle(叔叔节点)、grandfather(祖父节点)。

当节点的插入违反了红黑树“龟腚”时,对应不同的情况分别处理:

●父亲在祖父的左,叔叔在祖父的右:

情况1:cur为红,parent红色,叔叔节点存在且是红色,祖父是黑色;

 

如上图所示,情况1的处理方法就是将父亲和叔叔的节点变为黑色,祖父的节点变为红色。对于祖父为什么要变红是基于这样的考虑,我们当前的处理很可能只是在子树当中,如果祖父节点保持黑色不变,对于子树这两条路径而言,增加了黑色节点,这样一来就“拆东墙补了西墙”,又违反了另一条规则。如果祖父节点是根节点,改为红色当然是不合理的,我们在最后做下强制处理即可。

注意:这种情况可能是局部的处理,当祖父节点变红且不是根节点时,可能会破坏规则,所以针对情况1需要继续向上查找,也就是将祖父节点看成新增节点,祖父的父亲看做新增节点的父节点,继续向上更新检查树结构。

                if (uncle && uncle->_color == RED){//情况1,叔叔节点存在,且是红色的parent->_color = uncle->_color = BLACK;grandfater->_color = RED;//更新cur和parent的位置cur = grandfater;parent = cur->_parent;}

情况2:cur为红(插入或者调整后和父亲祖父为一条直线),parent红色,叔叔不存在或者叔叔是黑色,祖父是红色。

当叔叔不存在时:这种情况较好分析,新节点插入后左边高,左边高度超过右边的2倍,进行一次右单旋,祖父变成红色,父亲变为黑色,这颗树调整完毕,不管它是不是子树都不会向上影响。

叔叔存在且为黑色,观察下图,每条路径上的黑色节点数量不相等,所以cur的位置应该是从黑色调整为的红色。

注意:这里不要受图示的影响,感觉uncle路径上的黑节点好像是多一个。调整前后的每条路径数量都是相等的,想象小三角中有着不同的结构就可以了。

叔叔的存在与否只是分析的过程不同,它们的代码处理方式是一样的: 

                    //在一条线上if (parent->_left == cur){//情况2,叔叔节点不存在或者存在是黑色的//右单旋RotaR(grandfater);parent->_color = BLACK;grandfater->_color = RED;}

 

情况3:cur为红(插入或者调整后和父亲祖父为线一条折),parent红色,叔叔不存在或者叔叔是黑色,祖父是红色。

uncle不存在:

 uncle存在:

                      if(cur == parent->_left){//情况3,叔叔节点存在是黑色的,在一条折线上RotaL(parent);RotaR(grandfater);cur->_color = BLACK;grandfater->_color = RED;}

●父亲在祖父的右,叔叔在祖父的左:

处理大思路和上述一致,只是叔叔和父亲交换了位置,不在画图分析,列举处理要点:
情况1:叔叔存在且为红色,叔叔和父亲变黑,祖父变红。向上继续查找。

                if (uncle && uncle->_color == RED){//情况1,叔叔存在且是红色parent->_color = uncle->_color = BLACK;grandfater->_color = RED;//继续向上更新cur = grandfater;parent = cur->_parent;}

情况2:叔叔不存在或者存在为黑色,cur的位置和父亲祖父是一条直线,右边高,以祖父为轴点左单旋。祖父变红,父亲变黑。

                   //在右边插入if (parent->_right == cur){//进行一个左单旋RotaL(grandfater);//父亲的颜色变成黑色parent->_color = BLACK;//祖父的的颜色变成红色grandfater->_color = RED;}

情况3:叔叔不存在或者存在为黑色,cur的位置和父亲祖父是一条折线,先以父亲为轴右单旋,以祖父为轴点左单旋祖父变红,cur变黑。

                    if(cur == parent->_left)//左边插入{//右单旋RotaR(parent);//左单旋RotaL(grandfater);//改变颜色grandfater->_color = RED;cur->_color = BLACK;}

测试部分

因为红黑树是二叉搜索树,在测试时很可能会有隐式的错误,比较难发现,所以需要下面的测试接口对红黑树的特性进行检查,检查是否有连续的红色节点出现,每条路径上的黑色节点是否相等

bool check(Node* root,int num,int BLACKNUM){if (root == nullptr){if (num != BLACKNUM){cout << "某条路径上的黑色节点和其他路径不相等" << endl;return false;}return true;}if (root->_color == RED && root->_parent->_color == RED){cout << "连续出现两个红色节点" << endl;return false;}if (root->_color == BLACK){num++;}return check(root->_left, num, BLACKNUM)&&check(root->_right, num, BLACKNUM);}bool IsBalance(){if (_root == nullptr){return false;}//根节点的颜色一定要是黑色if (_root->_color != BLACK){return false;}Node* ret = _root;int _blacknum = 0;while (ret){if (ret->_color == BLACK){_blacknum++;}ret = ret->_left;}return check(_root,0,_blacknum);}

整体代码

#include <time.h>
enum Color
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;Color _color;RBTreeNode(pair<K, V> kv, Color color = RED):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(color){}
};template <class K,class V>
class RBTee
{
public:typedef RBTreeNode<K,V> Node;bool inster(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}//插入节点的位置cur = new Node(kv);cur->_color = RED;if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//插入的节点默认是红色的while (parent && parent->_color == RED){Node* grandfater = parent->_parent;if (parent == grandfater->_left){Node* uncle = grandfater->_right;if (uncle && uncle->_color == RED){//情况1,叔叔节点存在,且是红色的parent->_color = uncle->_color = BLACK;grandfater->_color = RED;//更新cur和parent的位置cur = grandfater;parent = cur->_parent;}else {//左边新增if (parent->_left == cur){//情况2,叔叔节点存在是黑色的,在一条线上//右单旋RotaR(grandfater);parent->_color = BLACK;grandfater->_color = RED;}//右边新增else{//情况3,叔叔节点存在是黑色的,在一条折线上RotaL(parent);RotaR(grandfater);cur->_color = BLACK;grandfater->_color = RED;}//树进行了旋转调整,已经平衡,跳出循环break;}}else //parent在grandfater的右边{Node* uncle = grandfater->_left;if (uncle && uncle->_color == RED){//情况1,叔叔存在且是黑色parent->_color = uncle->_color = BLACK;grandfater->_color = RED;//继续向上更新cur = grandfater;parent = cur->_parent;}else//uncle的颜色是黑色{//在右边插入if (parent->_right == cur){//进行一个左单旋RotaL(grandfater);//父亲的颜色变成黑色parent->_color = BLACK;//祖父的的颜色变成红色grandfater->_color = RED;}else//左边插入{//右单旋RotaR(parent);//左单旋RotaL(grandfater);//改变颜色grandfater->_color = RED;cur->_color = BLACK;}break;}}}_root->_color = BLACK;return true;}void Inorder(){_Inorder(_root);}bool check(Node* root,int num,int BLACKNUM){if (root == nullptr){if (num != BLACKNUM){cout << "某条路径上的黑色节点和其他路径不相等" << endl;return false;}return true;}if (root->_color == RED && root->_parent->_color == RED){cout << "连续出现两个红色节点" << endl;return false;}if (root->_color == BLACK){num++;}return check(root->_left, num, BLACKNUM)&&check(root->_right, num, BLACKNUM);}bool IsBalance(){if (_root == nullptr){return false;}//根节点的颜色一定要是黑色if (_root->_color != BLACK){return false;}Node* ret = _root;int _blacknum = 0;while (ret){if (ret->_color == BLACK){_blacknum++;}ret = ret->_left;}return check(_root,0,_blacknum);}
private:void _Inorder(Node* root){if (root == nullptr){return ;}_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.first << endl;_Inorder(root->_right);}void RotaL(Node* pparent){Node* subR = pparent->_right;Node* subRL = subR->_left;pparent->_right = subRL;if (subRL){subRL->_parent = pparent;}Node* pNode = pparent->_parent;pparent->_parent = subR;subR->_left = pparent;if (pNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (pNode->_left == pparent){pNode->_left = subR;}else if (pNode->_right == pparent){pNode->_right = subR;}subR->_parent = pNode;}}void RotaR(Node* pparent){Node* subL = pparent->_left;Node* subLR = subL->_right;pparent->_left = subLR;if (subLR != nullptr){subLR->_parent = pparent;}Node* pNode = pparent->_parent;subL->_right = pparent;pparent->_parent = subL;if (pNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (pNode->_left == pparent){pNode->_left = subL;}else{pNode->_right = subL;}subL->_parent = pNode;}}private:Node* _root = nullptr;
};

相关文章:

C++模拟实现红黑树

目录 介绍----什么是红黑树 甲鱼的臀部----规定 分析思考 绘图解析代码实现 节点部分 插入部分分步解析 ●父亲在祖父的左&#xff0c;叔叔在祖父的右&#xff1a; ●父亲在祖父的右&#xff0c;叔叔在祖父的左&#xff1a; 测试部分 整体代码 介绍----什么是红黑树 红…...

HTTPS协议之SSL/TLS详解(下)

目录 前言&#xff1a; SSL/TLS详解 HTTP协议传输安全性分析 对称加密 非对称加密 证书 小结&#xff1a; 前言&#xff1a; 在网络世界中&#xff0c;存在着运营商劫持和一些黑客的攻击。如果明文传输数据是很危险的操作&#xff0c;因为我们不清楚中间传输过程中就被哪…...

OLE对象是什么?为什么要在CAD图形中插入OLE对象?

OLE对象是什么&#xff1f;OLE对象的意思是指对象连接与嵌入。那为什么要在CAD图形中插入OLE对象&#xff1f;一般情况下&#xff0c;在CAD图形中插入OLE对象&#xff0c;是为了将不同应用程序的数据合并到一个文档中。本节内容小编就来给大家分享一下在CAD图形中插入OLE对象的…...

【微信小程序】-- 自定义组件 -- 数据、方法和属性(三十三)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…...

【Spring 深入学习】AOP的前世今生之代理模式

AOP的前世今生之代理模式1. 概述 什么是代理模式呢&#xff1f;&#xff1f;&#xff1f; 在不修改原有代码 或是 无法修改原有代码的情况下&#xff0c;增强对象功能&#xff0c;替代原来的对象去完成功能&#xff0c;从而达成了拓展的目的。 先给大家看下 JavaScript中实现方…...

操作系统复试

2017软学 给出操作系统的定义&#xff0c;分别从资源管理&#xff0c;任务调度&#xff0c;用户接口等三个方面论述操作系统的职能 操作系统是位于硬件层之上、所有其他系统软件层之下的一个系统软件&#xff0c;使得管理系统中的各种软件和硬件资源得以充分利用&#xff0c;方…...

藏经阁(五)温湿度传感器 SHT3x-DIS 手册 解析

文章目录芯片特性芯片内部框图芯片引脚定义芯片温湿度范围芯片寄存器以及时序讲解信号转换公式芯片特性 湿度和温度传感器完全校准&#xff0c;线性化温度补偿数字输出供电电压范围宽&#xff0c;从2.4 V到5.5 VI2C接口通讯速度可达1MHz和两个用户可选地址典型精度 2% RH和 0.…...

PCB焊盘设计基本原则

SMT的组装质量与PCB焊盘设计有直接的关系&#xff0c;焊盘的大小比例十分重要。如果PCB焊盘设计正确&#xff0c;贴装时少量的歪斜可以再次回流焊纠正(称为自定位或自校正效应)&#xff0c;相反&#xff0c;如果PCB焊盘设计不正确&#xff0c;即使贴装位置十分准确&#xff0c;…...

mysql锁分类大全

前言 为什么会出现锁 MySQL中的锁是为了保证并发操作的正确性和一致性而存在的。 当多个用户同时对同一份数据进行操作时&#xff0c;如果不加控制地进行读写操作&#xff0c;就可能导致数据不一致的问题。例如&#xff0c;当多个用户同时对同一行数据进行写操作时&#xff…...

推荐几款主流好用的远程终端连接管理软件

一、介绍 远程终端连接管理软件是管理服务器、虚拟机等远程计算机系统不可或缺的工具之一&#xff0c;它可以通过网络连接到另一台计算机&#xff0c;以执行命令、编辑文件或进行其他管理任务&#xff0c;下面我将为大家介绍几款主流好用的远程终端连接管理软件&#xff0c;并…...

描述性统计

参考文献 威廉 M 门登霍尔 《统计学》 文章目录定性数据的描述方法条形图饼图帕累托图定量数据点图茎叶图频数分布直方图MINITAB 工具在威廉《统计学》一书将统计学分为描述统计学和推断统计学&#xff0c;他们的定义分别如下&#xff1a;描述统计学&#xff1a;致力于数据集的…...

第十四届蓝桥杯三月真题刷题训练——第 7 天

目录 第 1 题&#xff1a;三角回文数 问题描述 答案提交 运行限制 代码&#xff1a; 第 2 题&#xff1a;数数 问题描述 答案提交 运行限制 代码&#xff1a; 第 3 题&#xff1a;倍数问题_同余定理_分情况讨论 题目描述 输入描述 输出描述 输入输出样例 运行限…...

剑指 Offer 57. 和为s的两个数字

一、题目 输入一个递增排序的数组和一个数字s&#xff0c;在数组中查找两个数&#xff0c;使得它们的和正好是s。如果有多对数字的和等于s&#xff0c;则输出任意一对即可。 示例 1&#xff1a; 输入&#xff1a;nums [2,7,11,15], target 9 输出&#xff1a;[2,7] 或者 [7…...

PDF转word在线转换方法!操作简单又高效

相信很多已经工作的人都知道&#xff0c;PDF文件格式的优点在于兼容性强、安全性高&#xff0c;而且查看和传输给他人都很方便。但是&#xff0c;这种格式的文件也有不太方便的地方&#xff0c;那就是不能对文件内容进行编辑和修改。对于许多人来说&#xff0c;如果想要编辑修改…...

Jquery项目中使用vue.js

大家在工作的情况中&#xff0c;可能会遇到之前的老项目采用jq书写&#xff0c;或者修改或者新增功能在jq中&#xff0c;原始jq的项目,代码可维护性很差,一个页面几千行jq,可维护性很差,工作量巨大&#xff0c;所以这个时候大家可以引入vue.js。 第一步&#xff1a;引入vue.js…...

蓝桥杯 删除字符

题目描述 给定一个单词&#xff0c;请问在单词中删除 t 个字母后&#xff0c;能得到的字典序最小的单词是什么&#xff1f; 输入描述 输入的第一行包含一个单词&#xff0c;由大写英文字母组成。 第二行包含一个正整数 t。 其中&#xff0c;单词长度不超过 100&#xff0c…...

析构函数 对象数组 对象指针

&#x1f436;博主主页&#xff1a;ᰔᩚ. 一怀明月ꦿ ❤️‍&#x1f525;专栏系列&#xff1a;线性代数&#xff0c;C初学者入门训练&#xff0c;题解C&#xff0c;C的使用文章 &#x1f525;座右铭&#xff1a;“不要等到什么都没有了&#xff0c;才下定决心去做” &#x1…...

Vue对Axios网络请求进行封装

一、为什么要对网络请求进行封装&#xff1f; 因为网络请求的使用率实在是太高了&#xff0c;我们有的时候为了程序的一个可维护性&#xff0c;会把同样的东西放在一起&#xff0c;后期找起来会很方便&#xff0c;这就是封装的主要意义。 二、如何进行封装&#xff1f; 1、将…...

Android framework HAL(HIDL)

简述 当你在Android系统中使用不同的硬件设备&#xff08;例如摄像头、传感器、音频设备等&#xff09;时&#xff0c;你需要与硬件抽象层&#xff08;HAL&#xff09;进行通信。 HAL是一个中间层&#xff0c;它充当了硬件和应用程序之间的桥梁。但是&#xff0c;由于硬件设备…...

QML 模型(ListModel)

LIstModel&#xff08;列表模型&#xff09; ListModel 是ListElement定义的简单容器&#xff0c;每个定义都包含数据角色。内容可以在 QML 中动态定义或显式定义。 属性&#xff1a; count模型中数据条目的数量dynamic动态角色&#xff0c;默认情况下&#xff0c;角色的类型…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...