C++番外篇——红黑树模拟实现set与map

embedded/2025/3/1 14:24:47/

问题探究

我们知道：set是K模型，Key=Value，所以如果用红黑树实现set，那么红黑树的每个节点直接存储一个值即可：

struct RBTreeNode_set
{RBTreeNode_set* _left;//节点的左孩子RBTreeNode_set* _right;//节点的右孩子RBTreeNode_set* _parent;//节点的父亲Key Value;//节点的值域Colour _col;//节点的颜色
};

map是KV模型，要通过Key找Value，所以如果用红黑树实现map，那么红黑树的每个节点要存储一个键值对pair<const K,V>：

struct RBTreeNode_map
{RBTreeNode_map<K, V>* _left;//节点的左孩子RBTreeNode_map<K, V>* _right;//节点的右孩子RBTreeNode_map<K, V>* _parent;//节点的父亲pair<const K, V> _kv;//节点的值域Colour _col;//节点的颜色
};

先来看看C++标准库中是如何封装set与map的：

 可见set与map共用一套模板来实现各自功能时都传递了两个参数，即：

set的参数为< Key , Value >；

map的参数为< Key , pair < const Key , Value > >;

C++底层居然这样实现，我们不禁发问：

set的Key与Value相同，map的Key与pair中的Key相同，那么传参数的时候就直接传递一个参数，即：set<Value>；map<pair<const Key,Value>>，这样不是更简单明了吗？

这是因为：

一方面，在C++标准库中，set、map、multiset、multimap等容器都是依靠红黑树来实现的，也就是说，红黑树需要为以上所有容器提供统一的模板接口，如果红黑树模板只接受一个参数，则无法通用处理不同容器的需求；

另一方面，如果省略第一个参数K，红黑树需要明确键类型来实现比较逻辑。set的键和值类型相同，所以省略掉第一个参数也无所谓；这种设计主要是为了兼顾map，对于map，如果只传递pair<const K,V>，红黑树无法知道用pair::first作为键，还是需要用其他方式提取键。

简单来说就是：第一个K是告诉红黑树键的类型，告知红黑树要以此类型来明确排序依据，如果参数是<K,K>红黑树就知道这是set类型的数据，需要以K作为排序依据；如果参数是<K,pair<const K,V>>红黑树就知道这是map类型的数据，需要拿出pair中的K即pair::first作为排序依据。

因此，如果需要用C++入门16——红黑树中的红黑树来实现set和map，我们就需要在已有基础上修改红黑树模板，为这些容器提供统一接口。

具体实现：

RBTRee.h

#include <iostream>
using namespace std;//节点的颜色
enum Colour
{red,black
};
//节点
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;//节点的左孩子RBTreeNode<T>* _right;//节点的右孩子RBTreeNode<T>* _parent;//节点的父亲Colour _col;//节点的颜色T _data;RBTreeNode(const T& data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(red)//红色节点{}
};template<class T, class Ptr, class Ref>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ptr, Ref> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_right){//右子树的中序第一个节点（最左节点）Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left; }_node = subLeft;}else{//祖先里面孩子是父亲最左孩子的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};// set->RBTree<K, K, SetKeyOfT>
// map->RBTree<K, pair<K, V>, MapKeyOfT>// 因为set是K模型，map是KV模型
// 用红黑树为模板实现二者，
// KeyOfT仿函数，兼顾map，方便取出T对象中的Key	 
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T*, T&> iterator;typedef RBTreeIterator<T, const T*, const T&> const_iterator;iterator begin(){Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);}const_iterator begin() const{Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return const_iterator(subLeft);}iterator end(){return iterator(nullptr);}const_iterator end() const {return const_iterator(nullptr);}iterator Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return iterator(cur);}}return end();}pair<iterator,bool> Insert(const T& data){if (_root == nullptr)//树本来就是空树，直接新增节点{_root = new Node(data);_root->_col = black;//头节点是黑色return make_pair(iterator(_root), true);}KeyOfT kot;//先按二叉搜索树的规则先找到要插入的位置Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) < kot(data))//大于，往右插入{parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data))//小于，往左插入{parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);//等于，无法插入}}//此时新节点要插入的位置已找到//接着开始将节点插入到该位置cur = new Node(data); // 红色的  前面已经说过，新插入节点需是红色Node* newnode = cur;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//为满足红黑树“黑色节点个数相同”while (parent && parent->_col == red)//当头节点存在或头节点变黑时，结束循环{Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况一：叔叔存在且为红if (uncle && uncle->_col == red){// 变色parent->_col = uncle->_col = black;grandfather->_col = red;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色if (cur == parent->_left){//       g//    p    u// cRotateR(grandfather);parent->_col = black;grandfather->_col = red;}else{//       g//    p     u//      cRotateL(parent);RotateR(grandfather);cur->_col = black;grandfather->_col = red;}break;}}else{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == red){// 变色parent->_col = uncle->_col = black;grandfather->_col = red;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = black;grandfather->_col = red;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = black;grandfather->_col = red;}break;}}}//存在头节点为红色的情况_root->_col = black;return make_pair(iterator(newnode), true);}//①右单旋void RotateR(Node* parent){Node* subL = parent->_left;// subL: parent的左孩子Node* subLR = subL->_right;// subLR: parent的左孩子的右孩子（可能为空）//①subLR变为parent的左孩子parent->_left = subLR;//②subLR可能不存在，如果存在，则更新subLR的父亲：subLR的父亲从subL变为parentif (subLR){subLR->_parent = parent;}//③parent从subL的父亲变为subL的右孩子subL->_right = parent;//④由于parent可能是棵子树，因此在更新父亲之前必须先保存parent的父亲Node* pparent = parent->_parent;//⑤更新parent的父亲：subL从parent儿子的身份变为parent的父亲parent->_parent = subL;//⑥如果parent是根节点，更新指向根节点的指针if (parent == _root){_root = subL;subL->_parent = nullptr;}else{//如果parent是子树，其可能是父亲的左子树，也可能是右子树if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}//⑦更新subL的父亲：subL的父亲从parent变为pparentsubL->_parent = pparent;}}//②左单旋void RotateL(Node* parent){Node* subR = parent->_right;// subR: parent的右孩子Node* subRL = subR->_left;// subRL: parent的右孩子的左孩子（可能为空）//①subRL变为parent的右孩子parent->_right = subRL;//②subRL可能不存在，如果存在，则更新subRL的父亲：subRL的父亲从subR变为parentif (subRL){subRL->_parent = parent;}//③parent从subR的父亲变为subR的左孩子subR->_left = parent;//④由于parent可能是棵子树，因此在更新父亲之前必须先保存parent的父亲Node* pparent = parent->_parent;//⑤更新parent的父亲：subR从parent儿子的身份变为parent的父亲parent->_parent = subR;//⑥如果parent是根节点，更新指向根节点的指针if (parent == _root){_root = subR;subR->_parent = nullptr;}else{//如果parent是子树，其可能是父亲的左子树，也可能是右子树if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}//⑦更新subR的父亲：subR的父亲从parent变为pparentsubR->_parent = pparent;}}private:Node* _root = nullptr;
};

MySet.h

#include "RBTree.h"namespace MySet
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator,bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t;};void test_set(){set<int> s;int a[] = { 4,2,6,1,3,5,15,7,16,14 };for (auto e : a){s.insert(e);}set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}
}

MyMap.h

#include "RBTree.h"namespace MyMap
{template<class K,class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}const_iterator begin() const{return _t.begin();}iterator end(){return _t.end();}const_iterator end() const{return _t.end();}pair<iterator,bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}iterator find(const K& key){return _t.Find(key);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t; };void test_map(){map<int, int> m;int a[] = { 4,2,6,1,3,5,15,7,16,14 };for (auto e : a){m.insert(make_pair(e, e));}map<int,int>::iterator it = m.begin();while (it != m.end()){cout << "(" << it->first << "," << it->second << ")" << " ";++it;}cout << endl;}
}

测试

#include "MyMap.h"
#include "MySet.h"int main()
{MySet::test_set();MyMap::test_map(); return 0;
}

http://www.ppmy.cn/embedded/169075.html

相关文章

Java中使用FFmpeg拉取RTSP流

Java中使用FFmpeg拉取RTSP流

在Java中使用FFmpeg拉取RTSP流并推送到另一个目标地址是一个相对复杂的任务&#xff0c;因为Java本身并没有直接处理视频流的功能。但是&#xff0c;我们可以借助FFmpeg命令行工具来实现这个功能。FFmpeg是一个非常强大的多媒体处理工具&#xff0c;能够处理音频、视频以及其他…
阅读更多...
AI关于SHAP分析与列线图（算法）解释线性模型矛盾之处的解释

AI关于SHAP分析与列线图（算法）解释线性模型矛盾之处的解释

AI关于SHAP分析与列线图&#xff08;算法&#xff09;解释线性模型矛盾之处的解释 两种解释方法在个案的局部解释方面&#xff0c;有矛盾之处&#xff0c;其背后的原理已经超出了我的知识范畴&#xff0c;以下是询问AI的几个问题&#xff0c;希望能从中梳理出一个合理的解释。…
阅读更多...
广州4399游戏25届春招游戏策划管培生内推

广州4399游戏25届春招游戏策划管培生内推

【热招岗位】 游戏策划管培生、产品培训生、游戏文案策划、游戏数值策划、游戏系统策划、游戏产品运营、游戏战斗策划、游戏关卡策划 【其他岗位】产品类&#xff08;产品培训生、产品运营等&#xff09;、技术类&#xff08;开发、测试、算法、运维等&#xff09;、运营市场类…
阅读更多...
图书数据采集：使用Python爬虫获取书籍详细信息

图书数据采集：使用Python爬虫获取书籍详细信息

文章目录 一、准备工作1.1 环境搭建1.2 确定目标网站1.3 分析目标网站二、采集豆瓣读书网站三、处理动态加载的内容四、批量抓取多本书籍信息五、反爬虫策略与应对方法六、数据存储与管理七、总结在数字化时代，图书信息的管理和获取变得尤为重要。通过编写Python爬虫，可以从各…
阅读更多...
《AI强化学习：元应用中用户行为引导的智能引擎》

《AI强化学习：元应用中用户行为引导的智能引擎》

在科技飞速发展的当下&#xff0c;元应用正以前所未有的速度融入我们的生活&#xff0c;从沉浸式的虚拟社交到高度仿真的工作模拟&#xff0c;元应用构建出一个个丰富多彩的虚拟世界。而在这背后&#xff0c;人工智能的强化学习技术宛如一位无形却强大的幕后推手&#xff0c;深…
阅读更多...
迁移过程中，hive元数据字段校对

迁移过程中，hive元数据字段校对

有时候在迁移过程中&#xff0c;源端字段可能被修改了&#xff0c;这些都存储在元数据库里&#xff0c;通常我们一般配置的hive元数据库都是mysql。所以我们最快的速度查出结果&#xff0c;就是在mysql里查。 然后对比2端表的md5就可以找到哪个表有问题了&#xff0c;再针对这…
阅读更多...
我的世界1.20.1forge模组开发进阶物品（7）——具有动画、3D立体效果的物品

我的世界1.20.1forge模组开发进阶物品（7）——具有动画、3D立体效果的物品

基础的物品大家都会做了对吧？包括武器的释放技能，这次来点难度，让物品的贴图呈现动画效果和扔出后显示3D立体效果，这个3D立体效果需要先学习blockbench，学习如何制作贴图。 Blockbench Blockbench是一个用于创建和编辑三维模型的免费软件，特别适用于Minecraft模型的设计…
阅读更多...
DeepSeek 助力 Vue 开发：打造丝滑的表单验证（Form Validation）

DeepSeek 助力 Vue 开发：打造丝滑的表单验证（Form Validation）

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 Deep…
阅读更多...
最新文章

Copyright @ 2022~2023