关于红黑树的模拟实现，大家不清楚的先去看看博主的博客再来看这篇文章，因为set和map的封装底层都是利用用的红黑树。所以这里不会过多介绍红黑树的相关内容，而更多的是去为了契合STL中的红黑树去进行改造，让封装的set和map能够去复用我们的这份代码
DS进阶：AVL树和红黑树-CSDN博客
在模拟实现之前，我们肯定要尝试去看看源码是如何实现的！我们会发现其实map和set的底层都是用的红黑树去封装的
但是你可能会有这样的疑惑，map是kv模型，set是k模型，那难道stl底层封装了两颗红黑树么？？其实并不是的，创建stl的大佬们为了增加代码的复用性，想方设法地想让map和set同时复用一颗红黑树。而解决方法就是通过控制模版参数来区分map和set。
既然底层是套的红黑树的壳子，我们就要来研究库里面的红黑树究竟通过了什么方法来让map和set都能够复用这份代码。
一、STL中的红黑树
1.1 利用模版参数控制和区分map和set
我们先来看看stl中的红黑树的模版参数，然后进行分析
接下来我们来看看第三个模版参数的作用究竟是什么
总结：
第1个模版参数是为了帮助我们拿到Key的类型，因为find、erase的接口都是Key类型比较方便
第2个模版参数决定了红黑树节点中存的是key还是pair，以此来区分map和set
第3个模版参数是通过仿函数决定了是拿什么去进行比较，对set来说就是拿key，对pair来说就是拿他的first。
第4个模版参数是具体的比较逻辑，比如说我们传的是指针，但是我们并不想通过指针比而是通过指针解引用的类型比，就可以通过传这个仿函数去控制其比较的行为。
第5个是stl实现的一个堆内存管理器，是为了提高从堆区申请内存的效率，基本上所有的stl容器都会涉及到这个，所以目前暂时不需要太在意！
1.2 stl中的红黑树结构
在该图中，设置了一个哨兵节点，哨兵节点的左指向最小节点5，最大节点的右指向哨兵节点header， 为什么要这样设计呢？？
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，
可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位
置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？
能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最
后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：
但是这样虽然方便我们找到第一个节点和最后一个节点，但是每一次都要最最左端和最右端的节点进行和头节点之间的联系，其实比较麻烦，所以下面我们直接改造成不带哨兵节点的红黑树。去模拟实现迭代器。
1.3 改造并模拟实现红黑树的迭代器
但是最最关键的逻辑就是，实现++和--这样迭代器才能跑的起来，下面我们来进行分析
迭代器的封装
template<class T,class Ref,class Ptr>struct _RBTreeIterator{typedef RBTreeNode<T> Node;typedef _RBTreeIterator<T, Ref, Ptr> Self; //返回一个自身的迭代器Node* _node;_RBTreeIterator(Node* node) //利用节点去构造迭代器:_node(node){}// 1、typedef __RBTreeIterator<T, T&, T*> itertaor; 拷贝构造// 2、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;// 支持普通迭代器构造const迭代器的构造函数_RBTreeIterator(const _RBTreeIterator<T, T&, T*>& it) //隐私类型转化:_node(it._node){}Ref operator*(){return _node->_data; //解引用拿到对应的东西 map拿到pair set拿到key}Ptr operator->() //返回对应的指针类型{return &operator*();}bool operator!=(const Self& s){return _node != s._node;//判断两个迭代器是否相同}bool operator==(const Self& s){return _node == s._node;//判断两个迭代器是否相同}Self& operator++() //实现迭代器的++{if (_node->_right){ //如有右不为空，那么就去找到 右子树的最左路节点Node* subright = _node->_right;while (subright->_left) subright = subright->_left; //找到最左路节点_node = subright;}else{ //右为空，沿着到根的路径，找孩子是父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--() //实现迭代器的-- 右 根 左{if (_node->_left){//如有左不为空，那么就去找到 左子树的最右路节点Node* subright = _node->_left;while (subright->_right) subright = subright->_right; //找到最左路节点_node = subright;}else{//左为空，沿着到根的路径，找孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}};1.4 红黑树实现的全部代码
enum Colour{RED,BLACK,};template<class T> //T表示传的是K还是pairstruct RBTreeNode{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}};template<class T,class Ref,class Ptr>struct _RBTreeIterator{typedef RBTreeNode<T> Node;typedef _RBTreeIterator<T, Ref, Ptr> Self; //返回一个自身的迭代器Node* _node;_RBTreeIterator(Node* node) //利用节点去构造迭代器:_node(node){}// 1、typedef __RBTreeIterator<T, T&, T*> itertaor; 拷贝构造// 2、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;// 支持普通迭代器构造const迭代器的构造函数_RBTreeIterator(const _RBTreeIterator<T, T&, T*>& it) //隐私类型转化:_node(it._node){}Ref operator*(){return _node->_data; //解引用拿到对应的东西 map拿到pair set拿到key}Ptr operator->() //返回对应的指针类型{return &operator*();}bool operator!=(const Self& s){return _node != s._node;//判断两个迭代器是否相同}bool operator==(const Self& s){return _node == s._node;//判断两个迭代器是否相同}Self& operator++() //实现迭代器的++{if (_node->_right){ //如有右不为空，那么就去找到 右子树的最左路节点Node* subright = _node->_right;while (subright->_left) subright = subright->_left; //找到最左路节点_node = subright;}else{ //右为空，沿着到根的路径，找孩子是父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--() //实现迭代器的-- 右 根 左{if (_node->_left){//如有左不为空，那么就去找到 左子树的最右路节点Node* subright = _node->_left;while (subright->_right) subright = subright->_right; //找到最左路节点_node = subright;}else{//左为空，沿着到根的路径，找孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}};//K是为了单独拿到key的类型 因为find erase 的接口都是key 而第二个模版参数T决定是这边传的是pair还是keytemplate<class K, class T,class KeyOfT> //KeyofT 取出来比较的是k 还是pair中的kclass RBTree{typedef RBTreeNode<T> Node;public:typedef _RBTreeIterator<T, T&, T*> iterator;typedef _RBTreeIterator<T, const T&, const T*> const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left) cur = cur->_left;//找到最左路的节点return iterator(cur);} iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* cur = _root;while (cur && cur->_left) cur = cur->_left;//找到最左路的节点return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);}~RBTree(){_Destroy(_root);_root = nullptr;}Node* Find(const K& key){Node* cur = _root;KeyOfT kot;//控制 是在pair中拿key还是直接拿keywhile (cur){if (kot(cur->_data) < key) cur = cur->_right; //我比你小，你往右找else if (kot(cur->_data) > key) cur = cur->_left; //我比你大，你往左找else return cur;}return nullptr;//说明找不到}//先用搜索树的逻辑插入节点，然后再去更新平衡因子。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;//控制 是在pair中拿key还是直接拿key//如果不为空树Node* parent = nullptr;Node* cur = _root;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);//相等 }//此时肯定是对应地接在parent的后面cur = new Node(data);Node* newnode = cur;//记住新加入的节点if (kot(parent->_data)> kot(data)) parent->_left = cur; //比父亲小连左边else parent->_right = cur; //比父亲大连右边//别忘了父亲指针cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//情况1，如果u为存在且为红if (grandfather->_left == parent)//如果p是g的左边，u就在右边{Node* uncle = grandfather->_right;//情况1，如果u为存在且为红 p u变黑，g变红 向上调整if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent;}else //情况2或者情况3， u为黑或者不存在 旋转+变色{if (cur == parent->_left) //情况2 右单旋+p变黑 g变红{// g// p u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //情况3 右左双旋 c变黑 g变红{// g// p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//情况2和情况3都要跳出循环}}else//if (grandfather->_right == parent)//如果p是g的右边，u就在左边 几乎一样，就是旋转的逻辑不同{Node* uncle = grandfather->_left;//情况1，如果u为存在且为红 p u变黑，g变红 向上调整if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent;}else//情况2或者情况3， u为黑或者不存在 旋转+变色{if (cur == parent->_right) //情况2 左单旋+p变黑 g变红{// g// p u// cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //情况3 左右双旋 c变黑 g变红{// g// p u// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//情况2和情况3都要跳出循环}}}_root->_col = BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑，总没错 return make_pair(iterator(newnode), true);}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root && _root->_col == RED){cout << "根节点颜色是红色" << endl;return false;}int benchmark = 0;//找到一条路径作为基准值 然后看看其他路径是否相等Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}// 连续红色节点return _Check(_root, 0, benchmark);}int Height(){return _Height(_root);}private:void _Destroy(Node* root){if (root == nullptr) return;//后序遍历销毁_Destroy(root->_left);_Destroy(root->_right);delete root;}int _Height(Node* root){if (root == nullptr)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}bool _Check(Node* root, int blackNum, int benchmark){if (root == nullptr){if (benchmark != blackNum){cout << "某条路径黑色节点的数量不相等" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED&& root->_parent&& root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return _Check(root->_left, blackNum, benchmark)&& _Check(root->_right, blackNum, benchmark);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}//旋转代码和AVL树是一样的，只不过不需要搞平衡因子void RotateL(Node* parent){//旋转前，先记录对应的节点Node* subR = parent->_right;Node* subRL = subR->_left;Node* ppnode = parent->_parent;//子树的前驱节点//先让b变成30的边parent->_right = subRL;if (subRL) subRL->_parent = parent;//让30变成60的左边subR->_left = parent;parent->_parent = subR;//此时与前驱节点连接起来 如果前驱节点为空，直接改变根if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边else{if (ppnode->_left == parent) ppnode->_left = subR;else ppnode->_right = subR;//向上连接subR->_parent = ppnode;}}void RotateR(Node* parent){//旋转前，先记录对应的节点Node* subL = parent->_left;Node* subLR = subL->_right;Node* ppnode = parent->_parent;//子树的前驱节点//先让b变成60的左边parent->_left = subLR;if (subLR) subLR->_parent = parent;//让60变成30的右边subL->_right = parent;parent->_parent = subL;//此时与前驱节点连接起来 如果前驱节点为空，直接改变根if (ppnode == nullptr){_root = subL;_root->_parent = nullptr;}//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边else{if (ppnode->_left == parent) ppnode->_left = subL;else ppnode->_right = subL;//向上连接subL->_parent = ppnode;}}Node* _root = nullptr;};二、set的模拟实现
前面我们已经将架子搭好了，这个时候就可以直接开始用了！！
namespace cyx{template<class K>class set{struct SetKeyofT{ const K& operator()(const K& key) //为了跟map保持一致{return key;}};public:typedef typename RBTree< K,K,SetKeyofT>::iterator iterator;//在没有实例化的时候 编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const K&key){return _t.Insert(key);}private:RBTree<K, K, SetKeyofT> _t;};注意：
1、在没有实例化的时候 ，编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题
2、对于insert返回值的改造，本质上是为了map去服务的，set只是配合而已。
三、map的模拟实现
3.1 insert的改装
在stl中 insert的返回值是pair<iterator,bool> 一开始我不太能理解为什么要这么设计。后来我明白了其实本质上为了后面重载[ ]的实现做铺垫。我们可以通过返回值去拿到iterator，并对对应节点的value进行直接修改！！
//先用搜索树的逻辑插入节点，然后再去更新平衡因子。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;//控制 是在pair中拿key还是直接拿key//如果不为空树Node* parent = nullptr;Node* cur = _root;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);//相等 }//此时肯定是对应地接在parent的后面cur = new Node(data);Node* newnode = cur;//记住新加入的节点if (kot(parent->_data)> kot(data)) parent->_left = cur; //比父亲小连左边else parent->_right = cur; //比父亲大连右边//别忘了父亲指针cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//情况1，如果u为存在且为红if (grandfather->_left == parent)//如果p是g的左边，u就在右边{Node* uncle = grandfather->_right;//情况1，如果u为存在且为红 p u变黑，g变红 向上调整if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent;}else //情况2或者情况3， u为黑或者不存在 旋转+变色{if (cur == parent->_left) //情况2 右单旋+p变黑 g变红{// g// p u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //情况3 右左双旋 c变黑 g变红{// g// p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//情况2和情况3都要跳出循环}}else//if (grandfather->_right == parent)//如果p是g的右边，u就在左边 几乎一样，就是旋转的逻辑不同{Node* uncle = grandfather->_left;//情况1，如果u为存在且为红 p u变黑，g变红 向上调整if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent;}else//情况2或者情况3， u为黑或者不存在 旋转+变色{if (cur == parent->_right) //情况2 左单旋+p变黑 g变红{// g// p u// cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //情况3 左右双旋 c变黑 g变红{// g// p u// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//情况2和情况3都要跳出循环}}}_root->_col = BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑，总没错 return make_pair(iterator(newnode), true);}3.2 重载[ ]的实现
V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V())); //默认构造return ret.first->second;}通过insert拿到对应位置的迭代器，然后指向其second 这样就可以直接进行修改了。
3.3 模拟实现的代码
namespace cyx{template<class K, class V>class map{struct MapKeyofT{const K& operator()(const pair<const K, V>& kv) //为了跟map保持一致{return kv.first;}};public://模版类型的内嵌类型 加typenametypedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;//在没有实例化的时候 编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题iterator begin(){return _t.begin();}iterator end(){return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V())); //默认构造return ret.first->second;}pair<iterator, bool> insert(const pair<const K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K,V>, MapKeyofT> _t;};
