【数据结构】红黑树(RBTree)

news/2024/4/24 18:24:36/文章来源:https://blog.csdn.net/m0_73865858/article/details/136352322

介绍

概念

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

性质

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

红黑树的插入调整

因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论

情况一: cur为红,p为红,g为黑,u存在且为红

在这里插入图片描述
u存在且为红,p,u变黑,g变红。
如果gg为黑,则不用处理了,gg为红,令g为cur,继续向上处理

情况二:cur为红,p为红,g为黑,u不存在/u存在且为黑(一定由情况一变化调整而来)

在这里插入图片描述
在这里插入图片描述
p为g的左孩子,cur为p的左孩子,则进行右单旋
p为g的右孩子,cur为p的右孩子,则进行左单旋

情况三:比情况二多了次旋转而已

在这里插入图片描述
代码:

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 (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//u存在且为红,变色处理,并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BlACK;uncle->_col = BlACK;grandfather->_col = RED;//continue to modifycur = grandfather;parent = cur->_parent;}//u不存在或u存在且为黑,旋转+变色else{//   g//  p  u//cif (cur == parent->_left){RotateR(grandfather);parent->_col = BlACK;grandfather->_col = RED;}else{//	  g//  p   u//    cRotateL(parent);RotateR(grandfather);parent->_col = RED;grandfather->_col = RED;cur->_col = BlACK;}break;}}else{Node* uncle = grandfather->_left;//u存在且为红,变色处理,并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BlACK;uncle->_col = BlACK;grandfather->_col = RED;//continue to modifycur = grandfather;parent = cur->_parent;}//u不存在或u存在且为黑,旋转+变色else{//   g//  u  p//       cif (cur == parent->_right){RotateL(grandfather);parent->_col = BlACK;grandfather->_col = RED;}else{//	  g//  u   p//    cRotateR(parent);RotateL(grandfather);parent->_col = RED;grandfather->_col = RED;cur->_col = BlACK;}break;}}_root->_col = BlACK;}return true;}

红黑树的拷贝构造

RBTree(const RBTree& rb){_root = CopyTree(rb._root, nullptr);}Node*  CopyTree(Node* rbroot,Node* parent){if (rbroot == nullptr)return nullptr;Node* newroot = new Node(rbroot->_kv);newroot->_col = rbroot->_col;newroot->_parent = parent;newroot->_left = CopyTree(rbroot->_left, newroot);newroot->_right = CopyTree(rbroot->_right, newroot);return newroot;}

set和map

RBTree的Iterator

template<class T,class Ref,class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator != (const Self & s){return _node != s._node;}Self& operator++(){if (_node->_right){//1.右不为空,找右子树的最左节点Node* subleft = _node->_right;while (subleft->_left){subleft = subleft->_left;}_node = subleft;}else{//2.右为空,沿着到根的路径,找孩子是父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){//左不为空,找左子树的最右节点Node* subright = _node->_left;while (subright->_right){subright = subright->_right;}_node = subright;}else{//左为空,找孩子是父亲的右的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};
template<class K,class T,class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;typedef __RBTreeIterator<const T, const T&, const T*> const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}

set/map和unordered_set/unordered_map区别

前者是底层是红黑树,双向迭代器,迭代器遍历是有序的;后者底层是哈希表,单向迭代器,迭代器遍历是无序的。

const迭代器和 const_iterator区别

博客园详见

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

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

相关文章

专家解读:2024年十大项目管理工具综合排名与评价

2024年涌现出一批新的项目管理工具&#xff0c;各具特色的功能和设计为企业解决了诸多的管理难题。今天我们就来盘点2024年的十款项目管理工具Zoho Projects、AgileMaster、PlanItAll、CommuniQ、WorkFlowRanger、GanttGenius、RiskAssessor、TeamHarmony、BudgetBoss、CloudCo…

智能控制:物联网智能插座对接文档

介绍 一开始买的某米的插座&#xff0c;但是好像接口不开放&#xff0c;所以找到了这个插座&#xff0c;然后自己开发了下&#xff0c;用接口控制插座开关。wifi的连接方式&#xff0c;通电后一般几秒后就会连接上wifi&#xff0c;这个时候通过接口发送命令给他。 产品图片 通…

#QT(DEMO)

1.IDE&#xff1a;QTCreator 2.实验&#xff1a;打印"hello wolrd" 3.记录 &#xff08;1&#xff09;创建一个新工程&#xff1a; 新建好一个工程存放文件夹&#xff08;路径不能有中文&#xff09;,然后按下图配置 &#xff08;2&#xff09;点击widgets.ui拖入以…

聚焦两会 | 从2024年政府工作报告看网络安全新机

在今年的《政府工作报告》&#xff08;下面简称“报告”&#xff09;中&#xff0c;除了对2023年里我国所取得的重大成就作了全面总结外&#xff0c;针对2024年全年经济社会发展作出的部署安排引起全国人民的关注。报告中与网络安全相关的内容也引起网络安全行业相关从事人员的…

如何查看前端的vue项目是vue2还是vue3项目

1. 检查package.json文件 在项目的根目录下&#xff0c;打开package.json文件&#xff0c;查找dependencies或devDependencies部分中的vue条目。版本号将告诉你是Vue 2还是Vue 3。例如&#xff1a; Vue 2.x: "vue": "^2.x.x"Vue 3.x: "vue": &…

vue svelte solid 虚拟滚动性能对比

前言 由于svelte solid 两大无虚拟DOM框架&#xff0c;由于其性能好&#xff0c;在前端越来越有影响力。 因此本次想要验证&#xff0c;这三个框架关于实现表格虚拟滚动的性能。 比较版本 vue3.4.21svelte4.2.12solid-js1.8.15 比较代码 这里使用了我的 stk-table-vue(np…

微信小程序用户登陆和获取用户信息功能实现

官方文档&#xff1a; https://developers.weixin.qq.com/miniprogram/dev/framework/open-ability/login.html 接口说明&#xff1a; https://developers.weixin.qq.com/miniprogram/dev/OpenApiDoc/user-login/code2Session.html 我们看官方这个图&#xff0c;梳理一下用户…

IEEE754标准的c语言阐述,以及几个浮点数常量

很多年前&#xff0c;调研过浮点数与整数之间的双射问题&#xff1a; win7 intel x64 cpu vs2013 c语言浮点数精度失真问题 最近重新学习了一下IEEE754标准&#xff0c;也许实际还有很多深刻问题没有被揭示。 计算机程序设计艺术&#xff0c;据说这本书中也有讨论。 参考&…

校招中的“熟悉linux操作系统”一般是指达到什么程度?

校招中的“熟悉linux操作系统”一般是指达到什么程度&#xff1f; 在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「Linux的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&am…

官网:随便搞个?那不如不搞,搞不好就给公司减分了。

官网建设确实需要认真对待&#xff0c;不能随便搞。一个粗制滥造的官网可能会给公司带来负面影响&#xff0c;降低品牌形象和用户体验。以下是一些官网建设的重要原则&#xff1a; 专业性&#xff1a;官网应该展示公司的专业性和专业知识。它应该以专业的设计、内容和功能来展示…

uipath调用js代码

1&#xff0c;调用js代码&#xff0c;不带参数&#xff0c;没有返回值 为了去掉按钮的disabled属性 function(){ document.getElementsByClassName(submitBtn)[0].removeAttribute(disabled); } 2&#xff0c;调用js代码&#xff0c;带参数&#xff0c;没有返回值 输入参数&a…

Day 6.有名信号量(信号灯)、网络的相关概念和发端

有名信号量 1.创建&#xff1a; semget int semget(key_t key, int nsems, int semflg); 功能&#xff1a;创建一组信号量 参数&#xff1a;key&#xff1a;IPC对像的名字 nsems&#xff1a;信号量的数量 semflg&#xff1a;IPC_CREAT 返回值&#xff1a;成功返回信号量ID…

Hololens 2应用开发系列(2)——MRTK基础知识及配置文件配置(上)

Hololens 2应用开发系列&#xff08;2&#xff09;——MRTK基础知识及配置文件配置 一、前言二、MRTK基础知识2.1 MRTK概述2.2 MRTK运行逻辑2.3 MRTK配置文件介绍2.4 MRTK服务 三、配置文件使用3.1 总配置文件3.2 相机配置3.3 其他配置 参考文献 一、前言 在前面的文章中&…

有一点好看的wordpress外贸独立站模板

手机配件wordpress外贸网站模板 充电器、移动电源、手机膜、手机电池、手机壳、手机转接头等手机配件wordpress外贸网站模板。 https://www.jianzhanpress.com/?p3809 车载电器wordpress外贸网站模板 车载吸尘器、空气净化器、行车记录仪、车载充电器、车载影音导航等车载电…

两数之和(c++ 、c)

给定一个整数数组nums和一个整数目标值target&#xff0c;请你再该数组中找出和为目标值target的那两个数&#xff0c;并返回它们的数组下标 题目介绍方法一思路及算法复杂度分析 方法二&#xff1a;哈希表什么是哈希表思路及算法C中unordered_map用法复杂度分析 方法三&#x…

C++ STL自定义排序

更具体的看【速记】C STL自定义排序 - 知乎 (zhihu.com) sort sort第三个位置放的greater<int>和less<int>萌新可能会弄错&#xff0c;这两个单词不是更大和更小的意思&#xff0c;而是大于和小于&#xff0c;并且比较就是自定义排序中的前者和后者。 如果是less…

【CSP试题回顾】201503-3-节日

CSP-201503-3-节日 关键点&#xff1a;格式化输出 在C中&#xff0c;格式化输出通常利用iostream库中的功能&#xff0c;特别是iomanip头文件提供的一系列操作符。这些操作符用于控制输出格式&#xff0c;如宽度、填充、对齐方式等。在你提供的代码中&#xff0c;用于格式化输…

电脑要用多少V的电源?电脑电源输入电压是市电

台式电源的输出电压是多少&#xff1f; 电脑电源输出一般有三种不同的电压&#xff0c;分别是&#xff1a; 12V、5V、3.3V。 电脑电源负责给电脑配件供电&#xff0c;如CPU、主板、内存条、硬盘、显卡等&#xff0c;是电脑的重要组成部分。 工作电流根据不同的硬件及其使用状…

Linux 开发工具 yum、git、gdb

目录 一、yum 1、软件包 2、rzsz 3、注意事项 4、查看软件包 5、安装软件 6、卸载软件 二、git操作 1、克隆三板斧 2、第一次使用会出现以下情况&#xff1a; 未配置用户名和邮箱&#xff1a; push后弹出提示 三、gdb使用 1、背景 2、使用方法 例一&#xff1a…

根据标准化开发流程---解析LIN总线脉冲唤醒的测试方法和用例设计思路

前言&#xff1a;本文从标准化开发流程的角度&#xff0c;以LIN总线脉冲唤醒为切入点。从测试工程师的角度来讲测试工作应当如何展开&#xff08;结合我干测试总结出来的测试经验&#xff09;。希望大家都能从中有收获&#xff01;&#xff01;谢谢&#xff01;&#xff01; 1…