手撕红黑树（map和set底层结构）（2）

@[TOC]红黑树

一 红黑树概念

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

简单来说红黑树通过了对颜色的控制进而对树的长度做出了限制，不再需要平衡因子。
红黑树性质

  1. 每个节点不是红色就是黑色
  2. 根节点为黑色
  3. 如果一个节点是红色，那么他的孩子节点就是黑色。没有连续的红色节点
  4. 对于每个节点，他的所以路径上的黑色节点的数量是相同的。
  5. 每个叶子节点都是黑色的（注意：这里的叶子节点指的是空节点）

红黑树通过这些性质保证了他的高度是合法的。
在这里插入图片描述
红黑树保证的是：最长路径不超过最短路径的两倍

二 红黑树的实现

2.1 红黑树的结构

enum Color
{Red,Black,
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _color;pair<K, V> _kv;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _color(Red), _kv(kv){}
};
template<class K,class V>
class RBtree
{typedef RBTreeNode<K, V> Node;private:Node* _node=nullptr;
}

2.2 红黑树的插入

在这里插入图片描述
我们要注意：我们在插入新节点的时候，默认插入元素的颜色为红色，（黑色节点不好控制，因为要保证全部的路径的黑色节点数量是相同的，插入了一个黑色节点，就不能保证这一原则了）
然后插入元素对整棵树的影响我们就要从局部开始看，

  1. 如果插入元素的父亲为黑色那就不用在变化了；
  2. 插入元素的父亲为红色，此时就出翔了连续的红色节点，我们就要对这颗树进行处理；

我们对第二种情况分类讨论（用上述的图片为例）

第一种：cur为红，p为红，g为黑，u存在且为红

把p和u变为黑色，再把g变成红色；
到这里就要继续分类讨论：

  1. g为根节点，那就把g再变成黑色。
  2. 如果不是根节点，就把g=c，向上继续处理
    注意（p/u是g的左还是右都不影响，同样cur是p的左还是右也不影响）

第二种: cur为红，p为红，g为黑，u不存在/u存在且为黑
（i）u不存在在这里插入图片描述
这里cur一定是新插入的节点，如果cur不是新插入的节点，cur和p一定有一个是黑色的。
（ii）u存在且为黑色在这里插入图片描述
这里的cur就不是新插入的节点，u是黑色那么，每个路径下黑色节点数量一定相同，所以cur原本一定是黑色的，是因为新插入的原因被变成了红色。
以上这两个情况本质上是一种。
这里就要用到旋转，旋转和前面AVL树的旋转一模一样

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
旋转完：p、g变色–p变黑，g变红。

参考下面的图，进一步理解
在这里插入图片描述
在这里插入图片描述
第三种 cur为红，p为红，g为黑，u不存在/u存在且为黑，但这里的左右位置不同

(i) p为g的左，cur为p的右
在这里插入图片描述
在这里插入图片描述
可以看到这里就变回了情况二，根据上面的我们再进行右单旋即可。
在这里插入图片描述
(i) p为g的右，cur为p的左

这个就是先右旋+左旋即可。这个图留个大家去完成。

2.3代码

bool Insert(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->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);//红色if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_color == Red){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//情况一：存在且为红if (uncle && uncle->_color == Red){//变色parent->_color = Black;uncle->_color = Black;grandfather->_color = Red;//向上处理cur = grandfather;parent = cur->_parent;}//情况二：不存在or存在且为黑else{//旋转+变色//    g//  p    u//cif (cur == parent->_left){RotateR(grandfather);parent->_color = Black;grandfather->_color = Red;}else{//情况三//    g//  p    u//     c  RotateL(parent);RotateR(grandfather);cur->_color = Black;grandfather->_color = Red;}break;}}else//p是g的右孩子{Node* uncle = grandfather->_left;//情况一：存在且为红if (uncle && uncle->_color == Red){//变色parent->_color = Black;uncle->_color = Black;grandfather->_color = Red;//向上处理cur = grandfather;parent = cur->_parent;}//情况二：不存在or存在且为黑else{//旋转+变色//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);parent->_color = Black;grandfather->_color = Red;}else{//情况三//    g//  u   p//     cRotateR(parent);RotateL(grandfather);cur->_color = Black;grandfather->_color = Red;}break;}}}_root->_color = Black;return true;}

三 检查函数

	bool Check(Node* cur, int BlackNum, int refBlackNum){if (cur == nullptr){if (BlackNum != refBlackNum){cout << "黑色节点的数量不匹配" << endl;return false;}elsereturn true;}if (cur->_color == Red && cur->_parent->_color == Red){cout << "出现了连续的红色节点" << endl;return false;}if (cur->_color == Black)++BlackNum;return Check(cur->_left, BlackNum, refBlackNum) &&Check(cur->_right, BlackNum, refBlackNum);}bool IsBalance(){if (_root == nullptr || _root->_color == Red)return false;//给一个基准值，和其他的黑色节点去比较int refBlackNum = 0;Node* cur = _root;while (cur){if (cur->_color == Black)++refBlackNum;cur = cur->_left;}return Check(_root, 0, refBlackNum);}

四 总结

总的来说红黑树的实现和AVL树非常像，他们就是兄弟，红黑树就是把考虑的因素从平衡因子转变成了颜色。

五 完整代码

#pragma once
#include<assert.h>
#include<vector>
enum Color
{Red,Black,
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _color;pair<K, V> _kv;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _color(Red), _kv(kv){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(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->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);//红色if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_color == Red){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//情况一：存在且为红if (uncle && uncle->_color == Red){//变色parent->_color = Black;uncle->_color = Black;grandfather->_color = Red;//向上处理cur = grandfather;parent = cur->_parent;}//情况二：不存在or存在且为黑else{//旋转+变色//    g//  p    u//cif (cur == parent->_left){RotateR(grandfather);parent->_color = Black;grandfather->_color = Red;}else{//情况三//    g//  p    u//     c  RotateL(parent);RotateR(grandfather);cur->_color = Black;grandfather->_color = Red;}break;}}else//p是g的右孩子{Node* uncle = grandfather->_left;//情况一：存在且为红if (uncle && uncle->_color == Red){//变色parent->_color = Black;uncle->_color = Black;grandfather->_color = Red;//向上处理cur = grandfather;parent = cur->_parent;}//情况二：不存在or存在且为黑else{//旋转+变色//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);parent->_color = Black;grandfather->_color = Red;}else{//情况三//    g//  u   p//     cRotateR(parent);RotateL(grandfather);cur->_color = Black;grandfather->_color = Red;}break;}}}_root->_color = Black;return true;}void RotateL(Node* parent){//++rotateSize;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}void RotateR(Node* parent){//++rotateSize;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);}/////检查函数bool Check(Node* cur, int BlackNum, int refBlackNum){if (cur == nullptr){if (BlackNum != refBlackNum){cout << "黑色节点的数量不匹配" << endl;return false;}elsereturn true;}if (cur->_color == Red && cur->_parent->_color == Red){cout << "出现了连续的红色节点" << endl;return false;}if (cur->_color == Black)++BlackNum;return Check(cur->_left, BlackNum, refBlackNum) &&Check(cur->_right, BlackNum, refBlackNum);}bool IsBalance(){if (_root == nullptr || _root->_color == Red)return false;//给一个基准值，和其他的黑色节点去比较int refBlackNum = 0;Node* cur = _root;while (cur){if (cur->_color == Black)++refBlackNum;cur = cur->_left;}return Check(_root, 0, refBlackNum);}
private:Node* _root = nullptr;
};void TestRBTree1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 14,16};RBTree<int, int> t;for (auto e : a){if (e == 16){int x = 0;}t.Insert(make_pair(e, e));// 1、先看是插入谁导致出现的问题// 2、打条件断点，画出插入前的树// 3、单步跟踪，对比图一一分析细节原因cout << e << "->" << t.IsBalance() << endl;}t.InOrder();cout << t.IsBalance() << endl;
}

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

选择ERP系统需要考虑哪些因素 企业ERP系统选型指南

选择ERP系统需要考虑哪些因素 企业ERP系统选型指南

ERP系统是一个复杂的软件系统&#xff0c;中小企业要建成ERP系统首先是要选择一个适合自己的ERP软件。目前市场上的ERP软件品种繁多&#xff0c;功能各异&#xff0c;那么中小企业应如何结合自己的实际情况“量体裁衣”找到最适合自己的ERP软件呢?这是目前中小企业进行ERP选型…
阅读更多...
介绍-响应式编程-001

介绍-响应式编程-001

&#x1f917; ApiHug {Postman|Swagger|Api...} 快↑ 准√ 省↓ GitHub - apihug/apihug.com: All abou the Apihug apihug.com: 有爱&#xff0c;有温度&#xff0c;有质量&#xff0c;有信任ApiHug - API design Copilot - IntelliJ IDEs Plugin | Marketplace 开篇&am…
阅读更多...
Ultralytics YOLOv8 英伟达™ Jetson®处理器部署

Ultralytics YOLOv8 英伟达™ Jetson®处理器部署

系列文章目录 前言 本综合指南提供了在英伟达 Jetson设备上部署Ultralytics YOLOv8 的详细攻略。此外&#xff0c;它还展示了性能基准&#xff0c;以证明YOLOv8 在这些小巧而功能强大的设备上的性能。 备注 本指南使用Seeed Studio reComputer J4012进行测试&#xff0c;它基于…
阅读更多...
2024年三支一扶报名照上传要求很严格

2024年三支一扶报名照上传要求很严格

2024年三支一扶报名照上传要求很严格
阅读更多...
Unity 使用GPU计算物体距离

Unity 使用GPU计算物体距离

在游戏开发中&#xff0c;计算物体之间的距离是一个常见的需求&#xff0c;例如用于碰撞检测、视觉效果等。传统的计算方法可能会在大量物体时带来性能问题&#xff0c;而在 Unity 中&#xff0c;借助 GPU 进行计算可以有效提高性能。本文将介绍一种使用 Compute Shader 在 Uni…
阅读更多...
windows安装nc命令的解决方案

windows安装nc命令的解决方案

大家好，我是爱编程的喵喵。双985硕士毕业，现担任全栈工程师一职，热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…
阅读更多...
C++ | Leetcode C++题解之第40题组合总和II

C++ | Leetcode C++题解之第40题组合总和II

题目&#xff1a; 题解&#xff1a; class Solution { private:vector<pair<int, int>> freq;vector<vector<int>> ans;vector<int> sequence;public:void dfs(int pos, int rest) {if (rest 0) {ans.push_back(sequence);return;}if (pos fr…
阅读更多...
找回删除的视频，3个神奇小妙招！

找回删除的视频，3个神奇小妙招！

“作为一名业余摄影师&#xff0c;我保存了很多重要的视频文件在电脑上&#xff0c;但刚刚电脑突然没电关机&#xff0c;开机后我发现很多视频莫名消失了。有什么方法可以找回这些丢失的视频吗&#xff1f;” 在数字化时代&#xff0c;视频文件往往承载着我们生活中的重要回忆。…
阅读更多...
Windows 安全中心：页面不可用 你的 IT 管理员已限制对此应用的某些区域的访问，并且你尝试访问的项目不可用。有关详细信息，请与 IT 支持人员联系。

Windows 安全中心：页面不可用 你的 IT 管理员已限制对此应用的某些区域的访问，并且你尝试访问的项目不可用。有关详细信息，请与 IT 支持人员联系。

问题 1&#xff1a;Windows 安全中心提示&#xff1a;【页面不可用 你的 IT 管理员已限制对此应用的某些区域的访问&#xff0c;并且你尝试访问的项目不可用。有关详细信息&#xff0c;请与 IT 支持人员联系。】 修复 Microsoft.SecHealthUI 方法 1&#xff1a;命令自动重装安…
阅读更多...
【C语言】数据的存储_数据类型：浮点型存储

【C语言】数据的存储_数据类型：浮点型存储

常见的浮点数&#xff1a; 3.1415926 1E10 浮点型包括&#xff1a;float、double、long double类型 浮点数表示的范围&#xff1a;float.h中定义 浮点数存储规则&#xff1a; 第二个n和*pFloat在内存中明明是同一个数&#xff0c;但浮点数和整数解读结果差别很大。 要理解这…
阅读更多...
Web入门-Tomcat

Web入门-Tomcat

黑马程序员JavaWeb开发教程 文章目录 一、简介1、Web服务器2、Tomcat 二、基本使用三、入门程序解析 一、简介 1、Web服务器 对HTTP协议操作进行封装&#xff0c;简化web程序开发部署Web项目&#xff0c;对外提供网上信息浏览服务 2、Tomcat 概念&#xff1a;Tomcat是Apach…
阅读更多...
Gitea 简单介绍、用法以及使用注意事项！

Gitea 简单介绍、用法以及使用注意事项！

Gitea 是一个轻量级的代码托管解决方案&#xff0c;它提供了一个简单而强大的平台&#xff0c;用于托管和协作开发项目。基于 Go 语言编写&#xff0c;与 GitLab 和 GitHub Enterprise 类似&#xff0c;但专为自托管而设计。以下是对 Gitea 的详细介绍&#xff0c;包括常用命令…
阅读更多...
TI API ，详情见ti.com

TI API ，详情见ti.com

TI API &#xff0c;详情见ti.com TI API 接口开发&#xff0c;实现货品查询、查询订单、自动下单、抢购等功能。
阅读更多...
掌握C++17的“武器“：Boost库带来的新特性

掌握C++17的“武器“：Boost库带来的新特性

C 17如何受益于Boost库 一、简介二、搜索算法三、文件系统库&#xff1a;filesystem四、特殊数学函数&#xff1a;clamp、gcd等五、模板增强&#xff1a;and、or、not六、C 20概览七、总结 一、简介 在上一篇文章中关于介绍了几个特性&#xff1a;std::optional、std::variant…
阅读更多...
Unity3d的海盗王地图

Unity3d的海盗王地图

一直以来&#xff0c;都想将海盗王的地图搬到手游unity3d上面。 经过漫长时间的研究&#xff0c;终于实现了当初的想法。
阅读更多...
STM32 软件I2C方式读取MT6701磁编码器获取角度例程

STM32 软件I2C方式读取MT6701磁编码器获取角度例程

STM32 软件I2C方式读取MT6701磁编码器获取角度例程 &#x1f4cd;相关篇《STM32 软件I2C方式读取AS5600磁编码器获取角度例程》&#x1f33f;《Arduino通过I2C驱动MT6701磁编码器并读取角度数据》&#x1f530;MT6701芯片和AS5600从软件读取对比&#xff0c;只是读取的寄存器和…
阅读更多...
AJAX——Promise-链式调用

AJAX——Promise-链式调用

1.Promise链式调用 概念&#xff1a;依靠then()方法会返回一个新生成的Promise对象特性&#xff0c;继续串联下一环任务&#xff0c;知道结束 细节&#xff1a;then()回调函数中的返回值&#xff0c;会影响新生成的Promise对象最终状态和结果 好处&#xff1a;通过链式调用&…
阅读更多...
恒峰智慧科技—森林消防泵：既可灭除火灾，又可清理水患

恒峰智慧科技—森林消防泵：既可灭除火灾，又可清理水患

在广袤的森林中&#xff0c;火灾与水患如同潜伏的猛兽&#xff0c;时刻威胁着生态的安全。然而&#xff0c;随着科技的进步&#xff0c;我们有了更强大的武器来对抗这些威胁——森林消防泵。这款神奇的设备不仅能迅速扑灭火灾&#xff0c;还能在雨季到来时清理水患&#xff0c;…
阅读更多...
ragflow 大模型RAG知识库使用案例

ragflow 大模型RAG知识库使用案例

参考： https://github.com/infiniflow/ragflow/blob/main/README_zh.md 支持丰富的文件类型，包括 Word 文档、PPT、excel 表格、txt 文件、图片、PDF、影印件、复印件、结构化数据, 网页等。 运行步骤： 1、确保 vm.max_map_count 不小于 262144 【更多】： 如需确认 vm.…
阅读更多...
磐石云外呼系统使用注意事项

磐石云外呼系统使用注意事项

磐石云外呼系统是一种基于云计算技术的电话外呼服务&#xff0c;旨在帮助企业提高外呼效率&#xff0c;增强客户沟通和服务能力。在使用过程中&#xff0c;企业需要注意系统的选择、安装、配置、使用方法以及数据安全和合规性等方面的问题。 使用前的准备 在使用磐石云外呼系统…
阅读更多...
最新文章

Copyright @ 2022~2023