STL之mapset续|红黑树篇

STL之map&set续|红黑树篇

  • 红黑树
    • 红黑树的规则
    • 红黑树的模拟实现
  • map&set的模拟实现
    • 封装map/set
    • 关于红黑树的复用
      • 红黑树模板参数
      • set的const迭代器问题

红黑树

红黑树也是一种搜索二叉树，它通过颜色和规则控制树上没有一条路径会比其他路径长两倍，实现接近平衡。它比AVL常用的一个原因就是它的控制条件不那么严苛，即不需要频繁旋转而效率较高。

红黑树的规则

规则：

  • 每个结点不是黑色就是红色
  • 根结点是黑色
  • 红结点的两个孩子结点都是黑的
  • 对于每个结点，从该结点到其后代所有结点的路径上，黑色结点数相同
  • 叶子结点是黑色的（指空结点）

可以看出，首先不存在连续的红结点。又因为每条路上黑结点数同，所以最短路径就是全黑，最长也是黑红相间，确实保证了树上没有一条路径会比其他路径长两倍。
再看看查找效率：假设黑结点N个，最长路径就是2log2N ，树的总结点数在N ~ 2N之间，这里按2N算，那么AVL树的最长路径是log2(2N+1)，约等于log2N。所以红黑树最坏查找时间约是AVL树的两倍。尽管如此，差别不大。

红黑树的模拟实现

先讨论一下红黑树的插入：
首先插入结点我们默认应该给红，因为如果给黑会影响黑结点数量，导致可能需要大范围调整才能让规则4满足。

  1. 假设插入位置的父亲是黑，那就正正好了，没违反任何规则，插入结束😜（这也是默认红色的好处）
  2. 如果插入位置的父亲是红，违反规则3，下面根据叔叔的情况分类讨论：
    • 情况一：叔叔（uncle）存在且为黑。这是最简单的情况。只需要父亲（parent）和叔叔变黑，祖父（grandparent）变红，这样祖父以下就没问题了，但因为祖父变色了，需要继续向上调整。
    • 情况二：uncle不存在。先左旋/左右双旋，再变色。注意，尽量保证顶部结点为黑，这样不会违反规则三，从而不再继续向上调整。
    • 情况三：uncle存在且为黑。先右旋/右左双旋，再变色。也注意一下顶部颜色。

注意下图中只是最简单的情况，比如一些父亲的右结点未画出，它们依然需要跟随旋转，只是不影响情况的分类判断，故未画出。
三种情况

细节都在代码里：

enum COLOR {RED,BLACK
};
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left = nullptr;RBTreeNode<T>* _right = nullptr;RBTreeNode<T>* _parent = nullptr;//方便起见，采取三叉链T _data;COLOR _col = RED;//优先给红RBTreeNode(const T& data) :_data(data) {}
};
template<class T, class Ref, class Ptr>
class __RBTreeIterator
{
public:typedef RBTreeNode<T> node;typedef __RBTreeIterator<T, Ref, Ptr> Self;typedef __RBTreeIterator<T, T&, T*>normal_iterator;__RBTreeIterator(node* node) :_node(node) {}//下面是高手操作，const迭代器实例化类模板时，这里是在用普通迭代器来构造const迭代器，太妙了//而如果是普通迭代器实例化类模板时，这就是普通迭代器的正常拷贝构造__RBTreeIterator(const normal_iterator& it) :_node(it._node) {}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}Self& operator++(){if (_node->_right)//右不为空，则右的最左节点{_node = _node->_right;while (_node->_left)_node = _node->_left;}else//右为空，沿着到根的路径，找孩子是父亲的左的那个节点{while (_node->_parent && _node != _node->_parent->_left){_node = _node->_parent;}if (!_node->_parent)_node = nullptr;else _node = _node->_parent;}return *this;}Self& operator--()//与++逻辑相反{if (_node->_left){_node = _node->_left;}else{while (_node->_parent && _node != _node->_parent->_right)_node = _node->_parent;if (!_node->_parent)_node = nullptr;else _node = _node->_parent;}}node* _node;};
template<class K, class T, class KeyOfT>
class RBTree
{
public:typedef RBTreeNode<T> node;//红黑树传的第二个参数就是节点里存的数据typedef __RBTreeIterator<T, T&, T*>iterator;typedef __RBTreeIterator<T, const T&, const T*>const_iterator;
public:iterator begin()const{node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end()const{return iterator(nullptr);}pair<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}node* parent = nullptr;node* cur = _root;KeyOfT kot;while (cur){//这里是不知道data里面的key在哪的，可能data就是K，也可能K是data的first，但是上层的map和set知道，所以需要传一个keyoftif (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else return make_pair(iterator(cur), false);}cur = new node(data);node* res = cur;cur->_parent = parent;if (kot(parent->_data) > kot(data))parent->_left = cur;elseparent->_right = cur;while (parent && parent->_col == RED){node* grandparent = parent->_parent;if (parent == grandparent->_left){node* uncle = grandparent->_right;if (uncle && uncle->_col == RED)//情况1{parent->_col = BLACK;grandparent->_col = RED;uncle->_col = BLACK;cur = grandparent;parent = cur->_parent;}else//情况2+3，uncle的颜色不变 if (uncle == nullptr|| uncle->_col == BLACK){if (cur == parent->_left){RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{RotateL(parent);RotateR(grandparent);grandparent->_col = RED;//parent->_col =还是红cur->_col = BLACK;}break;}}else{node* uncle = grandparent->_left;if (uncle && uncle->_col == RED)//与上一致{parent->_col = BLACK;grandparent->_col = RED;uncle->_col = BLACK;cur = grandparent;parent = cur->_parent;}else//情况2+3，uncle的颜色不变 if (uncle == nullptr|| uncle->_col == BLACK){if (cur == parent->_right){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{RotateR(parent);RotateL(grandparent);grandparent->_col = RED;//parent->_col =还是红cur->_col = BLACK;}break;}}}_root->_col = BLACK;return make_pair(iterator(res), true);}iterator Find(const K& key){node* cur = _root;while (cur){if (key > KeyOfT()(cur->_data))cur = cur->_right;else if (key < KeyOfT()(cur->_data))cur = cur->_left;else return iterator(cur);}return end();}~RBTree(){Destroy(_root);_root = nullptr;}
private:void Destroy(node* root){if (!root)return;Destroy(root->_left);Destroy(root->_right);delete root;}void RotateL(node* parent){node* subR = parent->_right;node* subRL = subR->_left;node* pparent = parent->_parent;parent->_right = subRL;subR->_left = parent;subR->_parent = pparent;if (subRL)subRL->_parent = parent;parent->_parent = subR;if (pparent){if (pparent->_left == parent)pparent->_left = subR;else pparent->_right = subR;}else _root = subR;}void RotateR(node* parent){node* subL = parent->_left;node* subLR = subL->_right;node* pparent = parent->_parent;parent->_left = subLR;subL->_right = parent;subL->_parent = pparent;if (subLR)subLR->_parent = parent;parent->_parent = subL;if (pparent){if (parent == pparent->_left)pparent->_left = subL;else pparent->_right = subL;}else _root = subL;}
private:node* _root = nullptr;
};

红黑树这里和AVL树的模拟实现一样都不实现erase，较为复杂，而我的目的也不是造轮子。
下面提供一些测试代码：

bool isRBTree()
{if (_root && _root->_col == RED){cout << "root is red" << endl;return false;}int benchMark = -1;return _isRBTree(_root, 1, benchMark);
}
void Inorder()
{_Inorder(_root);
}
int Height()
{return _Height(_root);
}
int _Height(node* root)
{if (!root)return 0;int LeftH = _Height(root->_left) + 1;int RightH = _Height(root->_right) + 1;return LeftH > RightH ? LeftH : RightH;
}
bool _isRBTree(node* root, int blackNum, int& benchMark)
{if (root == nullptr){if (benchMark == -1){benchMark = blackNum;}if (benchMark != blackNum){cout << "黑色节点数量不等" << endl;return false;}return true;}if (root->_col == BLACK)blackNum++;if (root->_col == RED && root->_parent->_col == RED){cout << root << ":parent is red" << endl;return false;}return _isRBTree(root->_left, blackNum, benchMark)&& _isRBTree(root->_right, blackNum, benchMark);
}
void _Inorder(node* root)
{if (!root)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);
}int main()
{//RBTree<int, int>t;int arr[] = { 16,3,7,11,9,26,18,14,15 };//int arr[] = { 4,2,6,1,3,5,15,7,16,14 };//for (int i = 0; i < 9; i++)//{//	t.Insert(make_pair(arr[i], i));//	//cout << "第" << i << ":";//调试//	//cout << t.isRBTree() << endl;//	//cout << endl;//}//t.Inorder();/*srand(time(0));const size_t N = 10000000;AVLTree<int, int>t;RBTree<int, int>rbt;for (size_t i = 0; i < N; i++){size_t x = rand() + i;t.Insert(make_pair(x, x));rbt.Insert(make_pair(x, x));}cout << t.isAVLTree() << endl;cout << rbt.isRBTree() << endl;cout << t.Height() << endl;cout << rbt.Height() << endl;for (size_t i = 0; i < N; i++){size_t x = rand();}*/
}

map&set的模拟实现

封装map/set

接下来封装红黑树来实现map/set

namespace lky
{template<class K>class set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;//typename告诉编译器是类型名，而非类内静态成员typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;//typename告诉编译器是类型名，而非类内静态成员pair<iterator, bool> insert(const K& key){return _t.Insert(key);//这里iterator转为const版发生了特殊拷贝构造，见上文高手操作}iterator begin(){return _t.begin();}iterator end(){return _t.end();}private:RBTree<K, K, SetKeyOfT>_t;//第二个参数传K，红黑树节点里存的就是key了};template<class K, class V>class map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){return _t.Insert(make_pair(key, V())).first->second;}iterator find(const K& key){return _t.Find(key);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}private:RBTree<K, pair<const K, V>, MapKeyOfT>_t;//防修改pair里的k};
}

关于红黑树的复用

写stl库的大佬很喜欢用模板参数来实现复用，比如list那块的const迭代器和超级无敌万能反向迭代器。还有下面map和set去复用rbtree。

红黑树模板参数

  1. 库中为了复用红黑树，map和set传给RBTree的第二个参数才是结点中实际存的数据类型，set通过K和T都传K类型实现复用，而map则传pair。注意，map传的pair里面可是const K哦，防止通过迭代器等等来修改pair里的key。
  2. 而第一个参数是单独的K类型，因为红黑树的一些接口如find/erase需要知道K类型。
  3. 模板里的KeyOfT是用来取出pair里的key，因为insert里虽然你知道map里pair的第一个参数是key，结构体取成员还不简单，但是set可是直接传的key啊，所以需要一个仿函数保证insert能取得key。
  4. alloc开内存池不再多言。
  5. 还有一个compare是为了支持比较key的大小，万一你插了一个自定义类型，对吧。

set的const迭代器问题

库里面set的普通迭代器和const迭代器都是红黑树的const迭代器。在没写迭代器里的拷贝构造之前，set里的insert是编不过的，因为红黑树的insert返回的是普通迭代器，而没有类型转换的话，set里面的insert返回的pair里的迭代器可是const迭代器哦，所以会报错无法从普通迭代器转化成const迭代器。库里是怎么解决的呢？
没错，它写了迭代器的拷贝构造，而且巧妙利用了模板
rbtree迭代器的拷贝构造
解析一下，这里的iterator就是永远的普通迭代器，因为他写死了（因为这里Value无论哪种迭代器都传的是T，而非const T，所以typedef的模板里面三个参数固定是T，T&，T*），所以当你传T时，这是个正常的拷贝构造；当你传const T时，这就是个从普通迭代器到const迭代器的特殊拷贝构造，支持了从普通到const的类型转换。
很妙吧，高手啊
本篇博客也就到此为止了，map/set完结撒花。但是来不及悼念了，接下来登场的是哈希大哥。C++的学业快望到头了😘😜

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

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

相关文章

三、计算机视觉_03LeNet5及手势识别案例

三、计算机视觉_03LeNet5及手势识别案例

1 LeNet-5基本介绍 LeNet-5是一种经典的卷积神经网络&#xff08;CNN&#xff09;架构&#xff0c;由Yann LeCun在1998年提出&#xff0c;用于手写数字识别&#xff0c;LeNet-5是卷积神经网络的开创性工作之一&#xff0c;它引入了卷积层、池化层和全连接层的组合&#xff0c;为…
阅读更多...
【论文模型复现】深度学习、地质流体识别、交叉学科融合？什么情况，让我们来看看

【论文模型复现】深度学习、地质流体识别、交叉学科融合？什么情况，让我们来看看

文献&#xff1a;蓝茜茜,张逸伦,康志宏.基于深度学习的复杂储层流体性质测井识别——以车排子油田某井区为例[J].科学技术与工程,2020,20(29):11923-11930. 本文目录 一、前言二、文献阅读-基于深度学习的复杂储层流体性质测井识别2.1 摘要2.2 当前研究不足2.3 本文创新2.4 论文…
阅读更多...
Uni-APP+Vue3+鸿蒙 开发菜鸟流程

Uni-APP+Vue3+鸿蒙 开发菜鸟流程

参考文档 文档中心 运行和发行 | uni-app官网 AppGallery Connect DCloud开发者中心 环境要求 Vue3jdk 17 Java Downloads | Oracle 中国 【鸿蒙开发工具内置jdk17&#xff0c;本地不使用17会报jdk版本不一致问题】 开发工具 HBuilderDevEco Studio【目前只下载这一个就…
阅读更多...
Unity-Editor扩展Odin + 自定义EditorWindow记录

Unity-Editor扩展Odin + 自定义EditorWindow记录

没有上下文&#xff0c;可能你不知道这是什么&#xff08;关于Odin Inspector) 在写一个 Odin 插件的完整文章&#xff0c;卡了三天&#xff0c;之后会放出 使用Unity的人之中 1/10 可能会使用Editor扩展&#xff0c;而这之中的又1/10的 人可能会用Odin这个Editor的附加扩展 -…
阅读更多...
FIFO系列 - FIFO使用中需要注意的若干问题

FIFO系列 - FIFO使用中需要注意的若干问题

FIFO使用中需要注意的若干问题 文章目录 FIFO使用中需要注意的若干问题前言场景1：包数据FIFO设计之冗余法场景2、FIFO数据传输之流控总结前言 场景1：包数据FIFO设计之冗余法 场景：类似图像、文字等码流数据是不需要重复被访问的，因此使用FIFO进行缓存（如果需要被存储，一…
阅读更多...
计算机毕业设计 | springboot+vue大学城水电管理系统 校园学校物业水电管理(附源码+文档)

计算机毕业设计 | springboot+vue大学城水电管理系统 校园学校物业水电管理(附源码+文档)

1&#xff0c;绪论 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理大学城水电管理系统的相关信息成…
阅读更多...
5-对象的访问权限

5-对象的访问权限

对象的访问权限知识点 对象的分类 在数据库中&#xff0c;数据库的表、索引、视图、缺省值、规则、触发器等等、都可以被称为数据库对象&#xff0c;其中对象主要分为两类 1、模式(schema)对象&#xff1a;模式对象可以理解为一个存储目录、包含视图、索引、数据类型、函数和…
阅读更多...
药方新解：Spring Boot中药实验管理系统设计

药方新解：Spring Boot中药实验管理系统设计

3系统分析 3.1可行性分析 通过对本中药实验管理系统实行的目的初步调查和分析&#xff0c;提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本中药实验管理系统采用SSM框架&#xff0c;JAVA作为开发语…
阅读更多...
动态规划-完全背包问题——279.完全平方数

动态规划-完全背包问题——279.完全平方数

1.题目解析 题目来源 279.完全平方数——力扣 测试用例 2.算法原理 1.状态表示 完全背包问题通常都是使用一个二维数组来表示其状态&#xff0c;这里是 dp[i][j]&#xff1a;在[1,i]区间选择平方数&#xff0c;当此时已选择平方数的总和完全等于j时所选择的最小平方数个数 …
阅读更多...
二叉树的层序遍历

二叉树的层序遍历

一、题目 给定一个二叉树&#xff0c;返回该二叉树层序遍历的结果&#xff0c;&#xff08;从左到右&#xff0c;一层一层地遍历&#xff09; 例如&#xff1a; 给定的二叉树是{3,9,20,null,null,15,7}, 该二叉树层序遍历的结果是 [[3],[9,20],[15,7]] 二、解决方案 2.0 树…
阅读更多...
模型训练过程的显存占用实测

模型训练过程的显存占用实测

依赖项说明 pip install nvitop pip install timm pip install peft后续的显存占用数据截图&#xff0c;均基于nvitop命令实现 1、模型显存占用说明 1.1 理论占用值 在 一文讲明白大模型显存占用&#xff08;只考虑单卡&#xff09;与大模型显存占用分析都对模型训练过程中…
阅读更多...
后端分层解耦

后端分层解耦

引入 在上篇所举的例子中&#xff0c;我们将所有的代码均放在HelloControl方法之中&#xff0c;这样会导致代码的复用性、可读性较差&#xff0c;难以维护。因此我们需 三层架构 在之前的代码中&#xff0c;代码大体可以分为三部分&#xff1a;数据访问、数据逻辑处理、响应数…
阅读更多...
AIGC 入门全攻略：开启智能创作新时代

AIGC 入门全攻略：开启智能创作新时代

一、AIGC 初印象 AIGC&#xff0c;即人工智能生成内容&#xff0c;是继专业生产内容&#xff08;PGC&#xff09;、用户生产内容&#xff08;UGC&#xff09;之后的新型内容创作方式。它涵盖了文本生成、图像与视频创作、音频生成等多个领域&#xff0c;正在以惊人的速度改变着…
阅读更多...
约克VRF地暖中央空调，让你舒适过冬

约克VRF地暖中央空调，让你舒适过冬

想要冬季过得舒服&#xff0c;采暖必须要到位&#xff01;对于没有集中供暖的南方地区来说&#xff0c;冬季室内阴冷刺骨。 选购地暖中央空调时&#xff0c;强效制热的能力必不可少&#xff0c;让我们可以享受温暖的室内温度&#xff0c;有效减少室内忽冷忽热的温度变化。 约克…
阅读更多...
基于Java Springboot宠物领养救助平台

基于Java Springboot宠物领养救助平台

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据…
阅读更多...
使用原生 OpenTelemetry 解锁各种可能性：优先考虑可靠性，而不是专有限制

使用原生 OpenTelemetry 解锁各种可能性：优先考虑可靠性，而不是专有限制

作者&#xff1a;来自 Elastic Bahubali Shetti•Miguel Luna Elastic 现在支持使用 OTel Operator 在 Kubernetes 上部署和管理 Elastic Distributions of OpenTelemetry (EDOT)。SRE 现在可以访问开箱即用的配置和仪表板&#xff0c;这些配置和仪表板旨在通过 Elastic Observ…
阅读更多...
基于python Django的boss直聘数据采集与分析预测系统，爬虫可以在线采集，实时动态显示爬取数据，预测基于技能匹配的预测模型

基于python Django的boss直聘数据采集与分析预测系统，爬虫可以在线采集，实时动态显示爬取数据，预测基于技能匹配的预测模型

本系统是基于Python Django框架构建的“Boss直聘”数据采集与分析预测系统&#xff0c;旨在通过技能匹配的方式对招聘信息进行分析与预测&#xff0c;帮助求职者根据自身技能找到最合适的职位&#xff0c;同时为招聘方提供更精准的候选人推荐。系统的核心预测模型基于职位需求技…
阅读更多...
安装 python-pcl 遇到的问题

安装 python-pcl 遇到的问题

安装python-pcl 成功安装错误尝试尝试一尝试二尝试三 本人环境 Ubuntu 22.04.4LTS ros2-humble cpython 3.0.11 python 3.10.12 libpcl-dev 1.12.1dfsg-3build1 pcl-tools 1.12.1dfsg-3build1 代码摘抄来源&#xff1a;Breadcrumbsouster-ros-extras/scripts/ros2_pcl_filters.…
阅读更多...
【C++进阶篇】——string类的使用

【C++进阶篇】——string类的使用

文章目录 前言&#xff1a;1. string的介绍2. string类对象的常见构造3. string类对象的容量操作4. string类对象的访问5. 迭代器6. string类对象的修改操作7. string类对象的字符串运算8.string类成员函数9.string类非成员函数10.string类常量成员 前言&#xff1a; std::str…
阅读更多...
vmware虚拟机给创建的centos扩展磁盘步骤

vmware虚拟机给创建的centos扩展磁盘步骤

1.先看看原来的磁盘信息&#xff0c;目前磁盘是20g的&#xff0c;重点关注红色箭头指向的地方&#xff0c;一个17g 可用11g&#xff0c;接下来要对其进行扩展 df -h2.关闭当前虚拟机&#xff0c;先进行磁盘扩展&#xff0c;目前我扩展到了50g。 3.重新开启虚拟机&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023