⭐博客主页：️CS semi主页 ⭐欢迎关注：点赞收藏+留言 ⭐系列专栏：C++进阶 ⭐代码仓库：C++进阶 家人们更新不易，你们的点赞和关注对我而言十分重要，友友们麻烦多多点赞＋关注，你们的支持是我创作最大的动力，欢迎友友们私信提问，家人们不要忘记点赞收藏＋关注哦！！！
用一棵红黑树封装map和set 一、红黑树原码二、红黑树模板参数控制三、红黑树结点当中存储的数据四、红黑树结点中仿函数五、正向迭代器1、框架+构造函数2、Ref3、Ptr4、重载operator==和operator!=5、operator++ 【重点讲解】（1）情况1：当前结点的右子树有结点（2）情况2：当前结点的右子树为空（3）代码 6、operator--（1）情况1：当前节点的左子树有节点（2）情况2：当前结点的左子树没结点（3）代码 7、正向迭代器在RBTree中的实现（1）begin()（2）end()（3）代码 8、缺陷和改进 六、反向迭代器1、反向迭代器的实现2、RBTree中使用反向迭代器 七、代码汇总一、红黑树原码
传送
二、红黑树模板参数控制set是Key模型的容器，map是key-value模型的容器，而我们是需要用一种模板来进行实现set和map，所以，我们使用了key-value模型来进行模拟实现set和map，我们将第二个模版参数改成class T，这样能够以示区分原来的红黑树的模版。
这个T既可能是K值，也可能是key与value共同构成的键值对，我们看一下set容器的实现形式：
我们再来写一下map的实现形式：
三、红黑树结点当中存储的数据那我们红黑树中的结点也是需要进行一下更改的，我们看下图，MySet中第二个模板参数传到RBTree中是传的是Key，而MyMap中第二个模板参数传到RBTree中的是pair<K, V>，这是kv的键值对，而RBTreeNode中接收的是第二个模板参数，我们以下列一下K和T不同的模板形式：
set：K和T都代表着Key。 map：K代表键值Key，T代表键值对pair<K, V>。
所以我们只需要使用第二个模板参数T就可以实现红黑树结点根据不同的容器进行模板实例化，但有同学要问了，为什么我们不能直接在set和map中只使用一个模版参数T呢？而偏偏要使用两个模板参数K和T？ 似乎是没什么问题的，对set来讲有没有这个第一个参数K都不影响的，而对于大部分的map情况中也是没有什么影响的，而具有最重大影响的是map的find和erase这两个接口函数，这两个接口函数是需要用到第一个参数K的，所以为了保持所有的接口都能用，只能委屈一下set，让set多一个模板参数K。
//红黑树结点的定义template<class T>struct RBTreeNode{//构造函数RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}//三叉链RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;//存储的数据T _data;//结点的颜色int _col; //红/黑}; 四、红黑树结点中仿函数一个很简单的现象，参数T：set的上层是K，直接能进行比较，而map上层是pair<K, V>，而我们进行比较map的时候是很难进行pair比较的，因为比较不了，所以我们需要将pair中的K特地摘出来进行比较，那么这个比较就需要通过一个仿函数进行摘出来K进行比较键值对。
仿函数：我们之前写过这种类似的仿函数模型，其实就是要实现一个operator()的功能，这个类就有了类似函数的行为，就是一个仿函数类了。
Map：
我们Map写了以后，我们思考一下Set写不写？ 看似似乎并不用写这个Set，因为我们的Key能直接拿到，但是这只是我们人的视角下是肯定可以的，但是编译器能那么聪明吗？我们了解到，编译器是没有办法进行判断我们传过来的是Map还是Set，所以我们需要委屈一下Set，把Set的仿函数也书写一下： 小故事：今天女朋友说要去逛街买包，你敢不去吗？也就是Set是一个陪逛街的身份，但它必须陪着Map逛街。
这样我们根据上面的逻辑图看实例化，是在RBTree中加入一个仿函数，将Set和Map的仿函数比较过程进行传参并实例化，那我们下面用一个Find子函数进行解析一下：
// 红黑树的查找Node* Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){// 当前结点的值大于寻找的结点的值if (key < kot(cur->_data)){cur = cur->_left;}else if (key > kot(cur->_data)){cur = cur->_right;}else{// 找到了return cur;}}return nullptr;} 五、正向迭代器红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是正向迭代器所封装结点的指针。
// 正向迭代器template<class T, class Ref, class Ptr>struct __TreeIterator{typedef RBTreeNode<T> Node; //结点类型typedef __TreeIterator<T, Ref, Ptr> Self; //正向迭代器类型Node* _node;};我们在之前写过有关T，Ref和Ptr，所以我们先介绍一下，T就是我们的模版参数，Ref是解引用操作，Ptr是指针操作。
1、框架+构造函数 // 正向迭代器template<class T, class Ref, class Ptr>struct __TreeIterator{typedef RBTreeNode<T> Node; //结点类型typedef __TreeIterator<T, Ref, Ptr> Self; //正向迭代器类型// 构造函数__TreeIterator(Node* node):_node(node){}Node* _node;}解释一下：T是第一个模版参数，定义类型的，Ref是解引用操作的模版参数，Ptr是指针指向的模版参数。
2、Ref要对于一个结点解引用的操作，我们直接返回这个结点的值即可。
// 正向迭代器解引用操作Ref operator*(){return _node->_data;} 3、Ptr要对于一个结点进行->的操作的时候，我们直接返回这个结点数据的指针即可。
// 正向迭代器指向操作Ptr operator->(){return &_node->_data;} 4、重载operator==和operator!=直接使用Self类型进行判断这两个迭代器是否相同。
// 判断两个正向迭代器是否不同bool operator!=(const Self& s) const{return _node != s._node;}// 判断两个正向迭代器是否相同bool operator==(const Self& s) const{return _node == s._node;} 5、operator++ 【重点讲解】我们要实现这个operator++，我们首先需要了解这个红黑树的遍历打印是中序遍历打印，也就是先左子树，再根，再右子树，所以我们如下两种情况：
（1）情况1：当前结点的右子树有结点找该节点的右子树的最左节点。
（2）情况2：当前结点的右子树为空++操作后在该结点的祖先结点中，找到孩子不在父亲右的祖先。
（3）代码 // 正向迭代器++操作Self operator++(){// 结点的右子树不为空，找右子树的最左结点if (_node->_right != nullptr){Node* R_left = _node->_right;while (R_left->_left != nullptr){R_left = R_left->_left;}_node = R_left;}// 结点的右子树为空，找祖先结点不为右的结点else{Node* cur = _node;Node* parent = cur->_parent;while (parent&& cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;} 6、operator–即遍历当前结点的前一个结点，与++正好相反。
1、如果当前结点的左子树不为空，则–操作后应该找到其左子树当中的最右结点。 2、如果当前结点的左子树为空，则–操作后应该在该结点的祖先结点中，找到孩子不在父亲左的祖先。
（1）情况1：当前节点的左子树有节点–是找左子树的最右结点。
（2）情况2：当前结点的左子树没结点 （3）代码 // 正向迭代器--操作Self operator--(){// 结点的左子树不为空，找左子树中的最右节点if (_node->_left != nullptr){Node* L_right = _node->_left;while (L_right->_right != nullptr){L_right = L_right->_right;}_node = L_right;}// 节点的左子树为空，找祖先结点中，找到孩子不在父亲左的祖先else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;} 7、正向迭代器在RBTree中的实现正向迭代器分为begin()和end()，所以我们分析一下begin()和end()：
我们要将iterator放到public当中，让外部可以拿到。
（1）begin()begin()就是我们前面所提的红黑树的第一个位置，而第一个位置则是整颗红黑树，begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点。
typedef __TreeIterator<T, T&, T*> iterator;// 最左节点iterator begin(){Node* left = _root;while (left && left->_left != nullptr){left = left->_left;}// 返回最左结点的迭代器return iterator(left);} （2）end()end()就是我们前面所提到的红黑树的最末尾的位置的下一个位置，那么就是nullptr！
typedef __TreeIterator<T, T*, T&> iterator;// end()是整个树的最末尾结点的后一个位置iterator end(){return iterator(nullptr);} （3）代码 template<class K, class T, class KeyOfT>class RBTree{typedef RBTreeNode<T> Node;public:typedef __TreeIterator<T, T*, T&> iterator;// 最左节点iterator begin(){Node* left = _root;while (left && left->_left != nullptr){left = left->_left;}// 返回最左结点的迭代器return iterator(left);}// end()是整个树的最末尾结点的后一个位置iterator end(){return iterator(nullptr);}private:Node* _root;}; 8、缺陷和改进我们大家不知道发现了没有，上述所写的end()是指向的最后一个结点的下一个位置，即nullptr，但我们的C++SGI版本中不是这样写的，其end()是指向最后一个元素的，所以我们来看一下SGI版本下的end()封装是怎么封装的：
我们看，在这个版本中，多了个header结点刚刚好是13根节点的父节点，这个header结点的左边指向这棵红黑树的最左节点象征着begin()，这个header结点的右边指向这棵红黑树的最右结点象征着rbegin()。实现end()和rend()时，直接用头结点构造出正向和反向迭代器即可。此后，通过对逻辑的控制，就可以实现end()进行–操作后得到最后一个结点的正向迭代器。
六、反向迭代器 1、反向迭代器的实现反向迭代器我们根本都不需要一步一步写下来了，我们只需要用正向迭代器进行封装反向迭代器即可，如下代码：
//反向迭代器 -- 根据正向迭代器封装template<class Iterator>struct ReverseIterator{typedef ReverseIterator<Iterator> Self; //反向迭代器的类型// 这里为了能够让反向迭代器能够拿到正向迭代器的解引用和指针typedef typename Iterator::reference Ref; //结点指针的解引用*typedef typename Iterator::pointer Ptr; //结点指针->//构造函数ReverseIterator(Iterator rit):_rit(rit){}// 和正向迭代器一样Ref operator*(){return *_rit;}// 和正向迭代器一样Ptr operator->(){return _rit.operator->(); }// ++操作就是正向迭代器的--操作Self& operator++(){--_rit;return *this;}// --操作就是正向迭代器的++操作Self& operator--(){++_rit;return *this;}// 不等号一样bool operator!=(const Self& s) const{return _rit != s._rit;}// 等号也一样bool operator==(const Self& s) const{return _rit == s._rit;}Iterator _rit;}; 2、RBTree中使用反向迭代器 template<class K, class T, class KeyOfT>class RBTree{typedef RBTreeNode<T> Node;public:typedef __TreeIterator<T, T*, T&> iterator;typedef ReverseIterator<iterator> reverse_iterator;// 最左节点iterator begin(){Node* left = _root;while (left && left->_left != nullptr){left = left->_left;}// 返回最左结点的迭代器return iterator(left);}// end()是整个树的最末尾结点的后一个位置iterator end(){return iterator(nullptr);}// 最右结点reverse_iterator rbegin(){Node* right = _root;while (right && right->_left != nullptr){right = right->_right;}// 返回最右结点的迭代器return reverse_iterator(iterator(right));}// end()是整个树的最末尾结点的后一个位置reverse_iterator rend(){return reverse_iterator(iterator(nullptr));}private:Node* _root;}; 七、代码汇总Set.h:
#include"MyRBTree.h"namespace JRH{template<class K, class T>class MySet{// 仿函数struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; //正向迭代器typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器// begin()iterator begin(){return _t.begin();}// end()iterator end(){return _t.end();}// rbegin()reverse_iterator rbegin(){return _t.rbegin();}// rend()reverse_iterator rend(){return _t.rend();}// 插入pair<iterator, bool> insert(const K& key){return _t.Insert(key);}// 删除void erase(const K& key){return _t.Erase(key);}// 查找iterator find(const K& key){return _t.Find(key);}private:RBTree<K, K, SetKeyOfT> _t;};}map.h
#include"MyRBTree.h"namespace JRH{template<class K, class V>class MyMap{//仿函数struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv) //返回键值对当中的键值Key{return kv.first;}};public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; //正向迭代器typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器// begin()iterator begin(){return _t.begin();}// end()iterator end(){return _t.end();}// rbegin()reverse_iterator rbegin(){return _t.rbegin();}// rend()reverse_iterator rend(){return _t.rend();}// 插入pair<iterator, bool> insert(const pair<const K, V>& kv){return _t.Insert(kv);}// 删除void erase(const K& key){return _t.Erase(key);}// 查找iterator find(const K& key){return _t.Find(key);}//[]运算符重载函数V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));iterator it = ret.first;return it->second;}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};}正向和反向迭代器：
// 正向迭代器template<class T, class Ref, class Ptr>struct __TreeIterator{typedef RBTreeNode<T> Node; //结点类型typedef __TreeIterator<T, Ref, Ptr> Self; //正向迭代器类型// 为了让下面反向迭代器拿到typedef typename Ref reference;typedef typename Ptr pointer;// 构造函数__TreeIterator(Node* node):_node(node){}// 正向迭代器解引用操作Ref operator*(){return _node->_data;}// 正向迭代器指向操作Ptr operator->(){return &_node->_data;}// 判断两个正向迭代器是否不同bool operator!=(const Self& s) const{return _node != s._node;}// 判断两个正向迭代器是否相同bool operator==(const Self& s) const{return _node == s._node;}// 正向迭代器++操作Self operator++(){// 结点的右子树不为空，找右子树的最左结点if (_node->_right != nullptr){Node* R_left = _node->_right;while (R_left->_left != nullptr){R_left = R_left->_left;}_node = R_left;}// 结点的右子树为空，找祖先结点不为右的结点else{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 != nullptr){Node* L_right = _node->_left;while (L_right->_right != nullptr){L_right = L_right->_right;}_node = L_right;}// 节点的左子树为空，找祖先结点中，找到孩子不在父亲左的祖先else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Node* _node;};//反向迭代器 -- 根据正向迭代器封装template<class Iterator>struct ReverseIterator{typedef ReverseIterator<Iterator> Self; //反向迭代器的类型// 这里为了能够让反向迭代器能够拿到正向迭代器的解引用和指针typedef typename Iterator::reference Ref; //结点指针的解引用*typedef typename Iterator::pointer Ptr; //结点指针->//构造函数ReverseIterator(Iterator rit):_rit(rit){}// 和正向迭代器一样Ref operator*(){return *_rit;}// 和正向迭代器一样Ptr operator->(){return _rit.operator->(); }// ++操作就是正向迭代器的--操作Self& operator++(){--_rit;return *this;}// --操作就是正向迭代器的++操作Self& operator--(){++_rit;return *this;}// 不等号一样bool operator!=(const Self& s) const{return _rit != s._rit;}// 等号也一样bool operator==(const Self& s) const{return _rit == s._rit;}Iterator _rit;};RBtree改装：
#include<algorithm>#include<iostream>using namespace std;enum Col{BLACK,RED};//红黑树结点的定义template<class T>struct RBTreeNode{//构造函数RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}//三叉链RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;//存储的数据T _data;//结点的颜色int _col; //红/黑};template<class K, class T, class KeyOfT>class RBTree{typedef RBTreeNode<T> Node;public:typedef __TreeIterator<T, T&,T*> iterator;typedef ReverseIterator<iterator> reverse_iterator;// 构造函数RBTree():_root(nullptr){}//赋值运算符重载RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t){swap(_root, t._root);return *this;}//析构函数~RBTree(){_Destroy(_root);_root = nullptr;}// 最左节点iterator begin(){Node* left = _root;while (left && left->_left != nullptr){left = left->_left;}// 返回最左结点的迭代器return iterator(left);}// end()是整个树的最末尾结点的后一个位置iterator end(){return iterator(nullptr);}// 最右结点reverse_iterator rbegin(){Node* right = _root;while (right && right->_left != nullptr){right = right->_right;}// 返回最右结点的迭代器return reverse_iterator(iterator(right));}// end()是整个树的最末尾结点的后一个位置reverse_iterator rend(){return reverse_iterator(iterator(nullptr));}// 红黑树的查找Node* Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){// 当前结点的值大于寻找的结点的值if (key < kot(cur->_data)){cur = cur->_left;}else if (key > kot(cur->_data)){cur = cur->_right;}else{// 找到了return cur;}}return nullptr;}// 插入pair<iterator, bool> Insert(const T& data){KeyOfT kot;// 一棵空树if (_root == nullptr){// 创建新结点 + 颜色初始化为黑色_root = new Node(data);_root->_col = BLACK; // 根节点得是黑的return make_pair(iterator(_root), true);}// 先找到 -- 利用二叉搜索树的方法进行查找Node* cur = _root;Node* parent = nullptr;// 左小右大while (cur){// 当前结点值大于待插入结点值，往左子树走if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}// 当前结点值小于待插入结点值，往右子树走else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}// 待插入结点的值和当前结点的值相等，插入失败else{return make_pair(iterator(cur), false);}}// 将当前结点的值插入进去cur = new Node(data); // new一个新的结点cur->_col = RED;Node* newnode = cur; // 记录新插入的结点// 新插入的节点值小于父节点的节点值，插入到parent的左边if (kot(data) < kot(parent->_data)){parent->_left = cur;cur->_parent = parent;}// 新插入的节点值小于父节点的节点值，插入到parent的左边else{parent->_right = cur;cur->_parent = parent;}// 新插入结点的父节点是红色的，需要做出调整while (parent && parent->_col == RED){Node* grandfather = parent->_parent; // parent是红色，则其父结点一定存在// 以grandparent左右孩子为分界线，分成if和elseif (parent == grandfather->_left) // 左孩子{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)// 情况一：uncle存在且为红色{// 颜色调整grandfather->_col = RED;uncle->_col = parent->_col = BLACK;// 继续往上处理cur = grandfather;parent = cur->_parent;}else// 情况二：uncle存在且为黑色 / 情况三：uncle不存在{// 用左右孩子分为两半，一半是if用来表示在左孩子，一半是else用来表示在右孩子if (cur == parent->_left){// g// p// c// 右单旋RoateR(grandfather);// 颜色调整parent->_col = BLACK;grandfather->_col = RED;}else{// g// p// c// 左右双旋RoateLR(grandfather);// 颜色调整cur->_col = BLACK;grandfather->_col = RED;}break;}}else // 右孩子{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)// 情况一：uncle存在且为红色{// 颜色调整grandfather->_col = RED;uncle->_col = parent->_col = BLACK;// 继续往上处理cur = grandfather;parent = cur->_parent;}else// 情况二：uncle存在且为黑色 / 情况三：uncle不存在{// 用左右孩子分为两半，一半是if用来表示在左孩子，一半是else用来表示在右孩子if (cur == parent->_right){// g// p// c// 左单旋RoateL(grandfather);// 颜色调整parent->_col = BLACK;grandfather->_col = RED;}else{// g// p// c// 右左双旋RoateRL(grandfather);// 颜色调整cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}// 左单旋void RoateL(Node* parent){// 三叉链Node* subr = parent->_right;Node* subrl = subr->_left;Node* ppnode = parent->_parent;// subrl与parent的关系parent->_right = subrl;if (subrl)subrl->_parent = parent;// subl和parent的关系subr->_left = parent;parent->_parent = subr;// ppnode和subr的关系if (ppnode == nullptr){_root = subr;subr->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subr;}else{ppnode->_right = subr;}subr->_parent = ppnode;}}// 右单旋void RoateR(Node* parent){// 三叉链Node* subl = parent->_left;Node* sublr = subl->_right;Node* ppnode = parent->_parent;//sublr和parent之间的关系parent->_left = sublr;if (sublr)sublr->_parent = parent;//subl和parent的关系subl->_right = parent;parent->_parent = subl;//ppnode 和 subl的关系if (ppnode == nullptr){_root = subl;subl->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subl;}else{ppnode->_right = subl;}subl->_parent = ppnode;}}// 左右双旋void RoateLR(Node* parent){RoateL(parent->_left);RoateR(parent);}// 右左双旋void RoateRL(Node* parent){RoateR(parent->_right);RoateL(parent);}private://析构函数子函数void _Destroy(Node* root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}Node* _root;};
