C++学习之旅【封装红⿊树实现mymap和myset】
🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》《数据结构与算法》
✨逆境不吐心中苦,顺境不忘来时路!🎬 博主简介:
引言:前篇文章,小编已经介绍了关于C++伸展树介绍以及红黑树的实现!相信大家应该有所收获!接下来我将带领大家继续深入学习C++的相关内容!本篇文章着重介绍关于C++封装红⿊树实现mymap和myset!本文正是围绕"手动封装红黑树以实现mymap 和myset"展开:我们将先梳理红黑树的核心规则与基础操作(插入、删除、旋转),再基于红黑树的底层结构,分别设计mymap(适配键值对存储)和myset(适配单一键存储)的核心接口(如insert、erase、find、迭代器遍历等),最终实现与STL 容器核心行为对齐的自定义版本.通过这一过程.不仅能吃透红黑树的平衡机制,更能深刻理解关联式容器"有序、唯一"特性的底层实现逻辑,从"知其然"走向"知其所以然".那么这里面到底有哪些知识需要我们去学习的呢?废话不多说,带着这些疑问,下面跟着小编的节奏🎵一起去疯狂的学习吧！
目录
1.源码及框架分析
SGI-STL30版本源代码,map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等⼏个头⽂件中.map和set的实现结构框架核⼼部分截取出来如下:
// set#ifndef__SGI_STL_INTERNAL_TREE_H#include<stl_tree.h>#endif#include<stl_set.h>#include<stl_multiset.h>// map#ifndef__SGI_STL_INTERNAL_TREE_H#include<stl_tree.h>#endif#include<stl_map.h>#include<stl_multimap.h>// stl_set.htemplate<classKey,classCompare= less<Key>,classAlloc= alloc>classset{public:// typedefs:typedef Key key_type;typedef Key value_type;private:typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t;// red-black tree representing set};// stl_map.htemplate<classKey,classT,classCompare= less<Key>,classAlloc= alloc>classmap{public:// typedefs:typedef Key key_type;typedef T mapped_type;typedef pair<const Key, T> value_type;private:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t;// red-black tree representing map};// stl_tree.hstruct__rb_tree_node_base{typedef __rb_tree_color_type color_type;typedef __rb_tree_node_base* base_ptr; color_type color; base_ptr parent; base_ptr left; base_ptr right;};// stl_tree.htemplate<classKey,classValue,classKeyOfValue,classCompare,classAlloc=alloc>classrb_tree{protected:typedefvoid* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;typedef rb_tree_node* link_type;typedef Key key_type;typedef Value value_type;public:// insert⽤的是第⼆个模板参数左形参 pair<iterator,bool>insert_unique(const value_type& x);// erase和find⽤第⼀个模板参数做形参 size_type erase(const key_type& x); iterator find(const key_type& x);protected: size_type node_count;// keeps track of size of tree link_type header;};template<classValue>struct__rb_tree_node:public__rb_tree_node_base{typedef __rb_tree_node<Value>* link_type; Value value_field;};分模块详细解释1️⃣头文件包含与重复包含防护
①核心逻辑:先通过宏__SGI_STL_INTERNAL_TREE_H检查<stl_tree.h>是否已包含,未包含则引入这是C/C++ 中防止头文件重复包含的经典做法,避免重复定义编译错误.
②依赖关系:set/map的实现完全依赖红黑树,因此必须先引入红黑树的头文件,再引入set/map 自身的头文件.2️⃣set类的核心封装(底层是红黑树)
①模板参数
Key:set 存储的键类型(也是值类型);
Compare:键的比较规则(默认升序less<Key>);
Alloc:内存分配器(默认alloc,SGI STL 的默认分配器).
②类型别名:key_type和value_type都等于Key—因为set中键就是值,不允许重复元素.
③底层红黑树适配
rb_tree的第三个模板参数identity<value_type>:是一个函数对象,作用是"从value中提取key".因为set的value就是key,所以直接返回value本身即可.
成员变量t:红黑树实例,set的增删查改(如insert/erase/find)最终都调用t的对应接口.3️⃣map类的核心封装(底层也是红黑树)
①模板参数:比set 多了T(映射的值类型),其余和 set 一致.
②类型别名:
value_type = pair<const Key, T>:map存储的是"键值对",且键不可修改(所以Key加 const),这是map 的核心特性.
③底层红黑树适配:
rb_tree的第三个模板参数select1st<value_type>:函数对象,作用是"从键值对(pair)中提取第一个元素(Key)“—红黑树需要根据Key排序,因此必须能从存储的value中提取Key.4️⃣红黑树的核心结构与类
(1)红黑树节点基类(通用部分)
作用:封装所有红黑树节点的通用属性(颜色、父子指针),是节点的基类,实现代码复用.
(2)红黑树具体节点类(存储数据)
继承关系:继承__rb_tree_node_base,复用通用节点属性.
核心扩展:增加value_field成员,存储具体的业务数据(set/map的元素).
(3)红黑树核心类(rb_tree)
①模板参数核心意义
Key:红黑树排序的键类型;
Value:红黑树存储的实际值类型(set的Key/map的pair);
KeyOfValue:从Value中提取Key的函数对象(set用identity,map 用select1st);
Compare:Key的比较规则;
Alloc:内存分配器.
②核心接口设计
insert_unique:接收value_type(完整元素),返回"迭代器 + 是否插入成功”—对应set/map"不允许重复键"特性;
erase/find:接收key_type(仅键)—因为查找/删除只需要键,无需完整元素,更高效.
❶通过下图对框架的分析,我们可以看到源码中rb_tree⽤了⼀个巧妙的泛型思想实现,rb_tree是实现key的搜索场景,还是key/value的搜索场景不是直接写死的,⽽是由第⼆个模板参数Value决定_rb_tree_node中存储的数据类型.
❷set实例化rb_tree时第⼆个模板参数给的是key,map实例化rb_tree时第⼆个模板参数给的是pair<const key, T>,这样⼀颗红⿊树既可以实现key搜索场景的set,也可以实现key/value搜索场景的map.
❸要注意⼀下,源码⾥⾯模板参数是⽤T代表value,⽽内部写的value_type不是我们我们⽇常key/value场景中说的value,源码中的value_type反⽽是红⿊树结点中存储的真实的数据的类型.
❹rb_tree第⼆个模板参数Value已经控制了红⿊树结点中存储的数据类型,为什么还要传第⼀个模板参数Key呢?尤其是set,两个模板参数是⼀样的,这是很多人这时的⼀个疑问.要注意的是对于map和set,find/erase时的函数参数都是Key,所以第⼀个模板参数是传给find/erase等函数做形参的类型的.对于set⽽⾔两个参数是⼀样的,但是对于map⽽⾔就完全不⼀样了,map insert的是pair对象,但是find和ease的是Key对象.
❺这⾥源码命名⻛格⽐较乱,set模板参数⽤的Key命名,map⽤的是Key和T命名,⽽rb_tree⽤的⼜是Key和Value,可⻅⼤佬有时写代码也不规范.
2.模拟实现map和set
2.1实现出复⽤红⿊树的框架,并⽀持insert
①参考源码框架,map和set复⽤之前我们实现的红⿊树.
②我们这⾥相⽐源码调整⼀下,key参数就⽤K,value参数就⽤V,红⿊树中的数据类型,我们使⽤T.
③其次因为RBTree实现了泛型不知道T参数导致是K,还是pair<K,V>,那么insert内部进⾏插⼊逻辑⽐较时,就没办法进⾏⽐较,因为pair的默认⽀持的是key和value⼀起参与⽐较,我们需要时的任何时候只⽐较key,所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT,然后RBTree中通过KeyOfT仿函数取出T类型对象中的key,再进⾏⽐较,具体细节参考如下代码实现.
// 源码中pair⽀持的<重载实现template<classT1,classT2>booloperator<(const pair<T1,T2>& lhs,const pair<T1,T2>& rhs){return lhs.first<rhs.first ||(!(rhs.first<lhs.first)&& lhs.second<rhs.second);}// Mymap.hnamespace lcz {template<classK,classV>classmap{structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:boolinsert(const pair<K, V>& kv){return _t.Insert(kv);}private: RBTree<K, pair<K, V>, MapKeyOfT> _t;};}// Myset.hnamespace lcz {template<classK>classset{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:boolinsert(const K& key){return _t.Insert(key);}private: RBTree<K, K, SetKeyOfT> _t;};}// RBTree.henumColour{ RED, BLACK };template<classT>structRBTreeNode{ T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col;RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr){}};// 实现步骤：// 1、实现红⿊树// 2、封装map和set框架，解决KeyOfT// 3、iterator// 4、const_iterator// 5、key不⽀持修改的问题// 6、operator[]template<classK,classT,classKeyOfT>classRBTree{private:typedef RBTreeNode<T> Node; Node* _root =nullptr;public:boolInsert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returntrue;} KeyOfT kot; Node* parent =nullptr; Node* cur = _root;while(cur){if(kot(cur->_data)<kot(data)){ parent = cur; cur = cur->_right;}elseif(kot(cur->_data)>kot(data)){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(data); Node* newnode = cur;// 新增结点。颜⾊给红⾊ cur->_col = RED;if(kot(parent->_data)<kot(data)){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;//...returntrue;}}2.2⽀持iterator的实现
//iterator核⼼源代码struct__rb_tree_base_iterator{typedef __rb_tree_node_base::base_ptr base_ptr; base_ptr node;voidincrement(){if(node->right !=0){ node = node->right;while(node->left !=0) node = node->left;}else{ base_ptr y = node->parent;while(node == y->right){ node = y; y = y->parent;}if(node->right != y) node = y;}}voiddecrement(){if(node->color == __rb_tree_red && node->parent->parent == node) node = node->right;elseif(node->left !=0){ base_ptr y = node->left;while(y->right !=0) y = y->right; node = y;}else{ base_ptr y = node->parent;while(node == y->left){ node = y; y = y->parent;} node = y;}}};template<classValue,classRef,classPtr>struct__rb_tree_iterator:public__rb_tree_base_iterator{typedef Value value_type;typedef Ref reference;typedef Ptr pointer;typedef __rb_tree_iterator<Value, Value&, Value*> iterator;__rb_tree_iterator(){}__rb_tree_iterator(link_type x){ node = x;}__rb_tree_iterator(const iterator& it){ node = it.node;} reference operator*()const{returnlink_type(node)->value_field;}#ifndef__SGI_STL_NO_ARROW_OPERATOR pointer operator->()const{return&(operator*());}#endif/* __SGI_STL_NO_ARROW_OPERATOR */ self&operator++(){increment();return*this;} self&operator--(){decrement();return*this;}inlinebooloperator==(const __rb_tree_base_iterator& x,const __rb_tree_base_iterator& y){return x.node == y.node;}inlinebooloperator!=(const __rb_tree_base_iterator& x,const __rb_tree_base_iterator& y){return x.node != y.node;}iterator实现思路分析
①iterator实现的⼤框架跟list的iterator思路是⼀致的,⽤⼀个类型封装结点的指针,再通过重载运算符实现,迭代器像指针⼀样访问的⾏为.
②这⾥的难点是operator++和operator–的实现.之前使⽤部分,我们分析了,map和set的迭代器⾛的是中序遍历,左⼦树->根结点->右⼦树,那么begin()会返回中序第⼀个结点的iterator也就是10所在结点的迭代器.
③迭代器++的核⼼逻辑就是不看全局,只看局部,只考虑当前中序局部要访问的下⼀个结点.
④迭代器++时,如果it指向的结点的右⼦树不为空,代表当前结点已经访问完了,要访问下⼀个结点是右⼦树的中序第⼀个,⼀棵树中序第⼀个是最左结点,所以直接找右⼦树的最左结点即可.
⑤迭代器++时,如果it指向的结点的右⼦树空,代表当前结点已经访问完了且当前结点所在的⼦树也访问完了,要访问的下⼀个结点在当前结点的祖先⾥⾯,所以要沿着当前结点到根的祖先路径向上找.
⑥如果当前结点是⽗亲的左,根据中序左⼦树->根结点->右⼦树,那么下⼀个访问的结点就是当前结点的⽗亲;如下图:it指向25,25右为空,25是30的左,所以下⼀个访问的结点就是30.
⑦如果当前结点是⽗亲的右,根据中序左⼦树->根结点->右⼦树,当前当前结点所在的⼦树访问完了,当前结点所在⽗亲的⼦树也访问完了,那么下⼀个访问的需要继续往根的祖先中去找,直到找到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点.如下图:it指向15,15右为空,15是10的右,15所在⼦树话访问完了,10所在⼦树也访问完了,继续往上找,10是18的左,那么下⼀个访问的结点就是18.
⑧end()如何表示呢?如下图:当it指向50时,++it时,50是40的右,40是30的右,30是18的右,18到根没有⽗亲,没有找到孩⼦是⽗亲左的那个祖先,这是⽗亲为空了,那我们就把it中的结点指针置为nullptr,我们⽤nullptr去充当end.需要注意的是stl源码空,红⿊树增加了⼀个哨兵位头结点做为end(),这哨兵位头结点和根互为⽗亲,左指向最左结点,右指向最右结点.相⽐我们⽤nullptr作为end(),差别不⼤,它能实现的,我们也能实现.只是–end()判断到结点时空,特殊处理⼀下,让迭代器结点指向最右结点.具体参考迭代器–实现.
⑨迭代器–的实现跟++的思路完全类似,逻辑正好反过来即可,因为他访问顺序是右⼦树->根结点->
左⼦树,具体参考下⾯代码实现.
⑩set的iterator也不⽀持修改,我们把set的第⼆个模板参数改成const K即可,RBTree<K,const K,SetKeyOfT> _t;map的iterator不⽀持修改key但是可以修改value,我们把map的第⼆个模板参数pair的第⼀个参数改成const K即可,RBTree<K, pair<const K,V>,MapKeyOfT> _t;⽀持完整的迭代器还有很多细节需要修改,具体参考下⾯题的代码.
2.3map⽀持[]
map要⽀持[]主要需要修改insert返回值⽀持,修改RBtree中的insert返回值为:pair<Iterator, bool> Insert(const T& data)有了insert⽀持[]实现就很简单了,具体参考下⾯代码实现.
2.4map和set代码实现
// Myset.h#include"RBTree.h"namespace lcz {template<classK>classset{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:typedeftypenameRBTree<K,const K, SetKeyOfT>::Iterator iterator;typedeftypenameRBTree<K,const K, SetKeyOfT>::ConstIterator const_iterator; iterator begin(){return _t.Begin();} iterator end(){return _t.End();} const_iterator begin()const{return _t.Begin();} const_iterator end()const{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;};voidPrint(const set<int>& s){ set<int>::const_iterator it = s.end();while(it != s.begin()){--it;// 不⽀持修改//*it += 2; cout <<*it <<" ";} cout << endl;}voidtest_set(){ set<int> s;int a[]={4,2,6,1,3,5,15,7,16,14};for(auto e : a){ s.insert(e);}for(auto e : s){ cout << e <<" ";} cout << endl;Print(s);}}// Mymap.h#include"RBTree.h"namespace lcz {template<classK,classV>classmap{structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator; iterator begin(){return _t.Begin();} iterator end(){return _t.End();} const_iterator begin()const{return _t.Begin();} 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;};voidtest_map(){ map<string, string> dict; dict.insert({"sort","排序"}); dict.insert({"left","左边"}); dict.insert({"right","右边"}); dict["left"]="左边，剩余"; dict["insert"]="插⼊"; dict["string"]; map<string, string>::iterator it = dict.begin();while(it != dict.end()){// 不能修改first，可以修改second//it->first += 'x'; it->second +='x'; cout << it->first <<":"<< it->second << endl;++it;} cout << endl;}}// RBtree.henumColour{ RED, BLACK };template<classT>structRBTreeNode{ T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col;RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<classT,classRef,classPtr>structRBTreeIterator{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self; Node* _node; Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){} Self&operator++(){if(_node->_right){// 右不为空，右⼦树最左结点就是中序第⼀个 Node* leftMost = _node->_right;while(leftMost->_left){ leftMost = leftMost->_left;} _node = leftMost;}else{// 孩⼦是⽗亲左的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_right){ cur = parent; parent = cur->_parent;} _node = parent;}return*this;} Self&operator--(){if(_node ==nullptr)// end(){// --end()，特殊处理，⾛到中序最后⼀个结点，整棵树的最右结点 Node* rightMost = _root;while(rightMost && rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}elseif(_node->_left){// 左⼦树不为空，中序左⼦树最后⼀个 Node* rightMost = _node->_left;while(rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}else{// 孩⼦是⽗亲右的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_left){ cur = parent; parent = cur->_parent;} _node = parent;}return*this;} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};template<classK,classT,classKeyOfT>classRBTree{typedef RBTreeNode<T> Node;public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T,const T&,const T*> ConstIterator; Iterator Begin(){ Node* leftMost = _root;while(leftMost && leftMost->_left){ leftMost = leftMost->_left;}returnIterator(leftMost, _root);} Iterator End(){returnIterator(nullptr, _root);} ConstIterator Begin()const{ Node* leftMost = _root;while(leftMost && leftMost->_left){ leftMost = leftMost->_left;}returnConstIterator(leftMost, _root);} ConstIterator End()const{returnConstIterator(nullptr, _root);}RBTree()=default;~RBTree(){Destroy(_root); _root =nullptr;} pair<Iterator,bool>Insert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returnmake_pair(Iterator(_root, _root),true);} KeyOfT kot; Node* parent =nullptr; Node* cur = _root;while(cur){if(kot(cur->_data)<kot(data)){ parent = cur; cur = cur->_right;}elseif(kot(cur->_data)>kot(data)){ parent = cur; cur = cur->_left;}else{returnmake_pair(Iterator(cur, _root),false);}} cur =newNode(data); Node* newnode = cur;// 新增结点。颜⾊红⾊给红⾊ cur->_col = RED;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;// g// p uif(parent == grandfather->_left){ Node* uncle = grandfather->_right;if(uncle && uncle->_col == RED){// u存在且为红 -》变⾊再继续往上处理 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent;}else{// u存在且为⿊或不存在 -》旋转+变⾊if(cur == parent->_left){// g// p u//c//单旋RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// g// p u// c//双旋RotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else{// g// u p 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;returnmake_pair(Iterator(newnode, _root),true);} Iterator Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key){ cur = cur->_right;}elseif(cur->_kv.first > key){ cur = cur->_left;}else{returnIterator(cur, _root);}}returnEnd();}private:voidRotateL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;if(subRL) subRL->_parent = parent; Node* parentParent = parent->_parent; subR->_left = parent; parent->_parent = subR;if(parentParent ==nullptr){ _root = subR; subR->_parent =nullptr;}else{if(parent == parentParent->_left){ parentParent->_left = subR;}else{ parentParent->_right = subR;} subR->_parent = parentParent;}}voidRotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;if(subLR) subLR->_parent = parent; Node* parentParent = parent->_parent; subL->_right = parent; parent->_parent = subL;if(parentParent ==nullptr){ _root = subL; subL->_parent =nullptr;}else{if(parent == parentParent->_left){ parentParent->_left = subL;}else{ parentParent->_right = subL;} subL->_parent = parentParent;}}voidDestroy(Node* root){if(root ==nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}private: Node* _root =nullptr;};3.给红黑树增加迭代器,并对红黑树进行改造
#include<iostream>usingnamespace std;// 颜色枚举enumColor{ RED, BLACK };// 红黑树节点定义template<classT>structRBTreeNode{ T _data;// 节点存储的数据 Color _col;// 节点颜色 RBTreeNode* _left;// 左孩子 RBTreeNode* _right;// 右孩子 RBTreeNode* _parent;// 父节点// 节点构造函数RBTreeNode(const T& data):_data(data),_col(RED)// 默认红色,_left(nullptr),_right(nullptr),_parent(nullptr){}};// 迭代器实现（完善++/*/->/==/!=）template<classT>structRBTreeIterator{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T> Self; Node* _node;RBTreeIterator(Node* node):_node(node){}// 迭代器++操作（核心：中序遍历的下一个节点） Self&operator++(){// 情况1：当前节点有右孩子 → 下一个是右子树的最左节点if(_node->_right !=nullptr){ Node* cur = _node->_right;while(cur->_left !=nullptr){ cur = cur->_left;} _node = cur;}// 情况2：当前节点无右孩子 → 向上找第一个“当前节点是其父节点左孩子”的父节点else{ Node* cur = _node; Node* parent = cur->_parent;// 向上遍历，直到找到cur是parent的左孩子，或parent为空（遍历结束）while(parent !=nullptr&& cur == parent->_right){ cur = parent; parent = parent->_parent;} _node = parent;// 此时parent就是下一个节点（或nullptr，对应End()）}return*this;}// 重载*：返回节点数据的引用（像指针一样解引用） T&operator*(){return _node->_data;}// 重载->：返回节点数据的地址（支持迭代器->成员访问） T*operator->(){return&(_node->_data);}// 重载!=：比较迭代器指向的节点是否不同booloperator!=(const Self& s)const{return _node != s._node;}// 重载==：比较迭代器指向的节点是否相同booloperator==(const Self& s)const{return _node == s._node;}};// 红黑树类（完善迭代器别名+Begin()/End()）template<classK,classT,classKeyOfT>classRBTree{typedef RBTreeNode<T> Node;public:// 1. 给迭代器取别名（核心：关联RBTreeIterator）typedef RBTreeIterator<T> Iterator;// 2. Begin()：返回中序遍历第一个节点（整棵树的最左节点） Iterator Begin(){ Node* cur = _root;// 找最左节点（中序遍历起点）if(cur !=nullptr){while(cur->_left !=nullptr){ cur = cur->_left;}}returnIterator(cur);}// 3. End()：返回中序遍历的尾后迭代器（nullptr） Iterator End(){returnIterator(nullptr);}~RBTree(){Destroy(_root); _root =nullptr;}boolInsert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returntrue;} KeyOfT kot; Node* parent =nullptr; Node* cur = _root;while(cur){if(kot(cur->_data)<kot(data)){ parent = cur; cur = cur->_right;}elseif(kot(cur->_data)>kot(data)){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(data); cur->_col = RED;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){RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{RotateL(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{if(cur == parent->_right){RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}} _root->_col = BLACK;returntrue;}private:// 左旋voidRotateL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;if(subRL) subRL->_parent = parent; Node* parentParent = parent->_parent; subR->_left = parent; parent->_parent = subR;if(parentParent ==nullptr){ _root = subR; subR->_parent =nullptr;}else{if(parent == parentParent->_left){ parentParent->_left = subR;}else{ parentParent->_right = subR;} subR->_parent = parentParent;}}// 右旋voidRotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;if(subLR) subLR->_parent = parent; Node* parentParent = parent->_parent; subL->_right = parent; parent->_parent = subL;if(parentParent ==nullptr){ _root = subL; subL->_parent =nullptr;}else{if(parent == parentParent->_left){ parentParent->_left = subL;}else{ parentParent->_right = subL;} subL->_parent = parentParent;}}// 销毁树voidDestroy(Node* root){if(root ==nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}private: Node* _root =nullptr;};structTestData{int _key; string _value;TestData(int key,const string& value):_key(key),_value(value){}};// KeyOfT：从TestData中提取key的仿函数structKeyOfTestData{intoperator()(const TestData& data){return data._key;}};intmain(){// 1. 创建红黑树（Key=int, T=TestData, KeyOfT=KeyOfTestData） RBTree<int, TestData, KeyOfTestData> rbt;// 2. 插入测试数据 rbt.Insert(TestData(10,"A")); rbt.Insert(TestData(20,"B")); rbt.Insert(TestData(30,"C")); rbt.Insert(TestData(15,"D")); rbt.Insert(TestData(25,"E")); rbt.Insert(TestData(5,"F"));// 3. 用迭代器遍历红黑树（中序遍历，结果有序） cout <<"红黑树迭代器遍历（中序有序）："<< endl;for(auto it = rbt.Begin(); it != rbt.End();++it){ cout <<"key: "<< it->_key <<", value: "<< it->_value << endl;}return0;}敬请期待下一篇文章内容–>unordered_map和unordered_set的使⽤以及哈希表的实现!
每日心灵鸡汤:学会鼓励自己!
生活就是这样,有时候累到想逃,但无可退路.不管怎么样,一定要慢慢消化自己的情绪,放宽心,做好事,少抱怨,多努力.生活的道路或许崎岖,但每一步都有其意义.当我们放宽心,就会发现那些曾经困扰我们的难题,也不过是人生旅途中的小小插曲.努力的汗水会浇灌出成功的花朵,即使一时看不到成果,也在为未来的绽放积蓄力量.在这漫长的人生中,我们会遇到无数的挑战,但只要坚守内心的信念,以积极的态度去面对,就一定能在生活的磨砺中不断成长.少抱怨,多努力,用行动去改变现状,而不是在抱怨中虚度光阴!
