前言
前面我们已经对红黑树做了介绍和实现，本期我们来对红黑树进一步改造，然后基于改造后的红黑树封装出map和set！
本期内容介绍
• 红黑树的改造
• 红黑树的迭代器实现
• map的封装
• set的封装
• 全部源码
● 红黑树的改造
我们目前的实现的红黑树，里面存的是一个pair<K,V>的键值对，但是我们知道set是只有key没有val的，map是<key,val>的！而他两都是基于红黑树实现的，难道是弄两棵红黑树分别封装？这是不是太cuo了呀！显然不是的，库里面他两底层用的是一颗红黑树：
这里人家是将底层存的数据没有写死，给了一个Value的类型！你上层如果封装成map就给pair<K,V>，如果是封装成set就给K即可！（后面的比较器和空间配置器暂时就不看了）
• 问题一：set使用时是一个key为什么底层也要传给红黑树两个key?
由于map和set的底层都用的是同一棵红黑树，而map存的是K,V类型的键值对，所以这里可以认为是set对map的迁就！所以set即使用的时候只是一个key，但底层还是给红黑树一样的V和K，目的是使得红黑树的模板参数的一致性！
• 问题二：红黑树的是在左插入等操作时，如何知道你是pair还是key呢？
的确红黑树那一层是不知道的，但是我们map和set层是知道的！如何让红黑树那一层知道呢？就是第三个参数，是一个获取存储值key的类；当map和set传过去之后，红黑树层可以创建对象获取！
OK，我们也改造一下自己的红黑树出来吧：（我们就把存储的数据类型改成T避免与V混淆）
节点类要就不在是K,V了，而是T了：
insert也是不再是插入（inert后面介绍到[]还会改造）
OK，我们先把红黑树的构造和拷贝构造以及赋值拷贝给整出来，在上层例如set进行赋值，拷贝等操作，就会到红黑树这一层，如果红黑树没有就成了浅拷贝了！
• 默认构造
这里本来可以不用写的，但是后面如果实现了赋值拷贝后就自动生不成了，所以得写！
RBTree():_root(nullptr)
{}还有一种就是即使有了拷贝构造可以强制让编译器生成：
RBTree() = default;//强制让编译器生成默认构造• 拷贝构造
这里采用二叉树的前序逐一拷贝即可：
RBTree(const RBTree<K, T, KofT>& t)
{_root = Copy(t._root);
}Node* Copy(Node* root)
{if (root == nullptr)return nullptr;//复制节点和颜色Node* newnode = new Node(root->_data);newnode->_col = root->_col;//复制左孩子newnode->_left = Copy(root->_left);if (newnode->_left)//连接newnode->_left->_parent = newnode;//复制右孩子newnode->_right = Copy(root->_right);if (newnode->_right)//连接newnode->_right->_parent = newnode;return newnode;
}• 赋值拷贝
直接采用以前的那种现在写法：将形参用值接受，然后与当前交换
RBTree<K, T, KofT>& operator=(RBTree<K, T, KofT> t)
{swap(_root, t._root);
}• 析构函数
采用二叉树的后序，先删除做孩子，再删除右孩子，最后删除根节点！
~RBTree()
{Destory(_root);_root = nullptr;
}void Destory(Node* root)
{if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;root = nullptr;
}● 红黑树的迭代器实现
红黑树的迭代器和链表的一样，空间不是连续的无法用原生指针来实现，得改一个类来达到“连续”的行为！我们使用的迭代器无非就begin、end、!=, *，->，++等但是begin和end只有红黑树知道，所以我们在迭代器里面只需要实现!=, *, ->,++等即可：
迭代器本质就是也即是一个节点的指针，所以这里的迭代器类和链表的一模一样：
template<class T, class Ref, class Ptr>
struct _RBTree_Iterator
{typedef RBTreeNode<T> Node;typedef _RBTree_Iterator<T, Ref, Ptr> Self;Node* _node;_RBTree_Iterator(Node* node):_node(node){}
}operator*
直接返回该节点的数据的引用即可！
Ref operator*()
{return _node->_data;
}
operator->
直接返回当前节点的数据的地址（指针）即可！
Ptr operator->()
{return &_node->_data;
}operator !=
直接比较两个节点的地址是否不相等即可！
bool operator!=(const Self& s)
{return _node != s._node;
}operator==
直接比较两个节点的地址是否相同即可！
bool operator==(const Self& s)
{return _node == s._node;
}operator++
实现思路：因为红黑树迭代器走的是中序，即 左->根->右！而*的时候已经访问了该节点的左和他本身++是去找当前节点的下一个节点！所以此时只需要考虑，当前节点的有节点是是否为空！
1、如果当前节点的右节点不为空，下一个要访问的节点就是，右子树的最左节点！
2、如果当前节点的右节点为空，说当树全部都访问完了，此时就得向上找当前节点是父节点的左的父节点！下一个访问的就是这个父节点！
Self& operator++()
{if (_node->_right){Node* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}operator++(int)
有了前置的++后置直接复用即可！后置++的特点是返回+1前的值，这里同理！我们先拷贝一份当前的迭代器，然后当前迭代器复用前置++到下一个要访问的节点，然后返回拷贝即可！
//后置++
Self operator++(int)
{Self tmp = *this;++(*this);return tmp;
}operator--
前置++的思路是更具中序的：左->根->右！这里的--就和前置++相反：右->根->左！
1、当前节点的左不为空，下一个访问的节点就是当前节点左子树的最右节点！
2、当前节点的左为空，找当前节点是父节点的有孩子的父节点，下一个访问的是该父节点
// 前置--
Self& operator--()
{if (_node->_left){Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}else{Node* cur = _node, * parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}operator--(int)
后置--同理直接先拷贝一份当前节点，然后调用前置--带下一个访问的节点，最后返回该拷贝即可！
//后置--
Self operator--(int)
{Self tmp = *this;--(*this);return tmp;
}begin
因为迭代器是按照中序走的，所以begin是整棵树的最左节点！
Iterator Begin()
{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);
}end
这里的end应该是最右节点的下一个节点，这里简单处理为nullptr；
Iterator End()
{return Iterator(nullptr);
}const_begin
ConstIterator Begin() const
{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return ConstIterator(leftMin);
}
const_end
ConstIterator End() const
{return ConstIterator(nullptr);
}● map的封装
OK，先搞一个框架出来：
#pragma oncenamespace cp
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const prai<K,V>& kv){return kv.first;}};public:private:RBTree<K, pair<const K, V>, MapKeyOfT> _m;//map的key不允许修改};
}
• 注意：map的key是不允许修改的所以用const修饰
OK，先来整迭代器出来，直接调用干红黑树的即可：
iterator
typedef typename RBTree<K, pair<const K,V>, MapKeyofT>::Iterator iterator;
typedef typename RBTree<K, pair<const K,V>, MapKeyofT>::ConstIterator const_iterator;iterator begin()
{return _m.Begin();
}iterator end()
{return _m.End();
}const_iterator begin() const
{return _m.Begin();
}const_iterator end() const
{return _m.End();
}注意：
typedef typename RBTree<K, const K, SetKofT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKofT>::ConstIterator const_iterator;这里的RBTree<K, const K, SetKofT>只是类型不是实体，所以编译器不认识，得加上typename告诉编译器这是类型；
find
iterator find(const K& key)
{return _m.Find(key);
}insert
这里的insert，当前的红黑树是不要满足的，因为我们以前介绍使用的时候介绍过它的返回值是一个pair<iterator, bool>，如果插入成功返回当前插入节点的迭代器，bool设置为true；如果插入的元素失败，返回当前存在元素的迭代器，bool是false;
所以，我么先得改造红黑树的insert:挂在燥起来也不难，就是将返回值换成pair<iterator, bool>即可，唯一注意的一个点就是最后返回的那个节点的迭代器；一定要在前面提前记录变色前的那个新节点的指针，方便后面构造迭代器；如果不记录后面直接返回cur这个cur就不一定是前面的cur了因为会旋转 + 变色改变！！！
pair<Iterator, bool> Insert(const T& data)
{//第一次插入if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//根节点是黑色return make_pair(Iterator(_root), true);}Node* cur = _root;//当前节点Node* parent = nullptr;//当前节点的父节点KofT kot;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(cur->_data) > kot(parent->_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){grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续更新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){grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续更新cur = grandfather;parent = cur->_parent;}else//叔叔不存在或为黑 --> 旋转+变色{if (cur == parent->_left){// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateL(grandfather);parent->_col = BLACK;//变色grandfather->_col = RED;}break;//旋转+变色完了就结束掉}}}_root->_col = BLACK;//保证根节点永远是黑色return make_pair(Iterator(newnode), true);
}
成功改造完红黑的的insert之后map和set的就直接可以调用了！
pair<iterator, bool> insert(const pair<K, V>& kv)
{return _m.Insert(kv);
}operator[]
[]是基于insert实现的，在介绍使用的时候介绍过，[]按照K值插入，不管插入成功与否，都返回V的引用~！
V& operator[](const K& key)
{pair<iterator, bool> ret = _m.Insert(make_pair(key, V()));return ret.first->second;
}OK，测试一下：
void Print_map(const cp::map<string, int> m)
{for (auto& e : m){cout << e.first << " : " << e.second << endl;}
}void TestMap()
{cp::map<int, int> m1;m1.insert({ 1,1 });m1.insert({ 2,2 });m1.insert({ 3,3 });m1.insert({ 4,4 });m1.insert({ 5,5 });cp::map<int, int>::iterator it = m1.begin();while (it != m1.end()){cout << it->first << ":" << it->second << endl;it++;}cout << "--------------------" << endl;cp::map<string, int> m2;string s[] = { "aaa", "bbb", "ccc", "bbb", "cpdd", "000", "苹果", "西瓜", "aaa" };for (auto& e : s)m2[e]++;Print_map(m2);
}
● set的封装
同理，我们可以搭建出一个set的基本框架出来：
#pragma oncenamespace cp
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:private:RBTree<K, K, SetKeyOfT> _s;};
}OK，先来整迭代器出来，直接调用干红黑树的即可：
inerator
typedef typename RBTree<K, const K, SetKofT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKofT>::ConstIterator const_iterator;iterator begin()
{return _s.Begin();
}iterator end()
{return _s.End();
}const_iterator begin() const
{return _s.Begin();
}const_iterator end() const
{return _s.End();
}find
iterator find(const K& key)
{return _s.Find(key);
}insert
pair<iterator, bool> insert(const K& key)
{return _s.Insert(key);
}OK，测试一下：
void Print_set(const cp::set<int>& s)
{for (auto& e : s){cout << e << endl;}
}void TestSet()
{vector<int> v = { 8, 3, 1, 10, 6, 4, 7, 14, 13, 8, 6 };cp::set<int> s;for (auto& e : v){s.insert(e);}Print_set(s);
}OK，到这里map和set的封装就已经实现完了！一些接口例如size、clear等前面实现过很多次这里就不在实现了！这里想说的是map和set就是套了一层红黑树的壳，真正的核心还是红黑！
● 全部源码
RBTree.h
#pragma once#pragma onceenum Col
{RED = 0,BLACK
};template <class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Col _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED)//默认新的节点是红色{}
};template<class T, class Ref, class Ptr>
struct _RBTree_Iterator
{typedef RBTreeNode<T> Node;typedef _RBTree_Iterator<T, Ref, Ptr> Self;Node* _node;_RBTree_Iterator(Node* node):_node(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* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}//后置++Self operator++(int){Self tmp = *this;++(*this);return tmp;}// 前置--Self& operator--(){if (_node->_left){Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}else{Node* cur = _node, * parent = cur->_parent;while (parent && parent->_right != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}//后置--Self operator--(int){Self tmp = *this;--(*this);return tmp;}
};template <class K, class T, class KofT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef _RBTree_Iterator<T, T&, T*> Iterator;typedef _RBTree_Iterator<T, const T&, const T*> ConstIterator;RBTree() = default;//强制让编译器生成默认构造//RBTree()// :_root(nullptr)//{}RBTree(const RBTree<K, T, KofT>& t){_root = Copy(t._root);}RBTree<K, T, KofT>& operator=(RBTree<K, T, KofT> t){swap(_root, t._root);}~RBTree(){Destory(_root);_root = nullptr;}Iterator Begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);}Iterator End(){return Iterator(nullptr);}ConstIterator Begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return ConstIterator(leftMin);}ConstIterator End() const{return ConstIterator(nullptr);}Iterator Find(const K& key){KofT 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);}Node* cur = _root;//当前节点Node* parent = nullptr;//当前节点的父节点KofT kot;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(cur->_data) > kot(parent->_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){grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续更新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){grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续更新cur = grandfather;parent = cur->_parent;}else//叔叔不存在或为黑 --> 旋转+变色{if (cur == parent->_left){// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateL(grandfather);parent->_col = BLACK;//变色grandfather->_col = RED;}break;//旋转+变色完了就结束掉}}}_root->_col = BLACK;//保证根节点永远是黑色return make_pair(Iterator(newnode), true);}void InOrder(){return _InOrder(_root);}bool IsBalance(){if (_root && _root->_col == RED)return false;//根节点不可能为红int black = 0;//根节点到任意一条从根节点到叶子节点的黑色节点的数目Node* cur = _root;while (cur){if (cur->_col == BLACK)black++;cur = cur->_left;}return Check(_root, black, 0);}private:Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newnode = new Node(root->_data);newnode->_col = root->_col;newnode->_left = Copy(root->_left);if (newnode->_left)newnode->_left->_parent = newnode;newnode->_right = Copy(root->_right);if (newnode->_right)newnode->_right->_parent = newnode;return newnode;}void Destory(Node* root){if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}bool Check(Node* root, const int black, int num){if (root == nullptr){if (num != black)return false;return true;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << "存在连续的红色节点：" << endl;return false;}if (root->_col == BLACK){++num;}return Check(root->_left, black, num) && Check(root->_right, black, num);}void RotateR(Node* parent){Node* subL = parent->_left;//父亲的左Node* subLR = subL->_right;//左子树的右Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接parent->_left = subLR;//将左子树的右给父亲的做if (subLR)subLR->_parent = parent;subL->_right = parent;//parent做左子树的右parent->_parent = subL;if (parent == _root)//parent是根{_root = subL;//此时的新根就是subL_root->_parent = ppNode;}else//parent不是根{//将新的根连接到ppNodeif (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void RotateL(Node* parent){Node* subR = parent->_right;//父亲的右Node* subRL = subR->_left;//右子树的左Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接parent->_right = subRL;//将右子树的左连接到parent的右if (subRL)subRL->_parent = parent;subR->_left = parent;//parent连接到subR的左parent->_parent = subR;if (parent == _root)//parent是根{_root = subR;//此时的新根就是subR_root->_parent = ppNode;}else//parent不是根{//将新的根连接到ppNodeif (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}private:Node* _root = nullptr;
};Mymap.h
#pragma oncenamespace cp
{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>::ConstIterator const_iterator;iterator begin(){return _m.Begin();}iterator end(){return _m.End();}const_iterator begin() const{return _m.Begin();}const_iterator end() const{return _m.End();}iterator find(const K& key){return _m.Find(key);}pair<iterator, bool> insert(const pair<K, V>& kv){return _m.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _m.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyofT> _m;};
}Myset.h
#pragma oncenamespace cp
{template<class K>class set{struct SetKofT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKofT>::Iterator iterator;typedef typename RBTree<K, const K, SetKofT>::ConstIterator const_iterator;iterator begin(){return _s.Begin();}iterator end(){return _s.End();}const_iterator begin() const{return _s.Begin();}const_iterator end() const{return _s.End();}iterator find(const K& key){return _s.Find(key);}pair<iterator, bool> insert(const K& key){return _s.Insert(key);}private:RBTree<K, const K, SetKofT> _s;};
}OK，本期分享就到这里，好兄弟我们下期再见~！
结束语：我们的目标是星辰大海！
