【C++】使用红黑树封装map与set

对于map与set，它们一个是KV模型，一个是K模型，那我们要写两个红黑树吗？
我们来看一下源码

1. 源码分析

我很疑惑为什么它们两个都传了两个参数给底层的红黑树，那再看一下红黑树的源码

我们可以发现，红黑树在底层不知道你传给它的是什么，为了兼容map与set它搞了两个参数。

但是搞了两个参数后，第一个模板参数Key是不是有点多余呢？

• 对于set而言，两个K确实是有点多余；对于map来说，pair里面也有K，好像也有点多余
• 如果只留第二个模板参数，_rb_tree_node< Value >，为set时 Value为K；为 map时 Value为pair<K,V>，好像也没问题。
• 对于插入操作，set是k，map是pair还挺好；但是对于查找操作时，set使用Value没问题；map查找时也要使用Value，但map的Value是一个pair(有K，V)，那我既然知道了K和V，我还查找什么呢？所以第一个模板参数不多于，反而是必须

但还有一个问题，在插入操作时，涉及数据比较大小。但是map的Value是一个pair，还得取里面的key；set的Value就是key，此时就比较麻烦。pair默认的比较规则是first比完second比，不符合我们的预期。因此我们还要给红黑树传递一个仿函数，以便获取key。

2. 调整红黑树的结构搭建map、set

那我们之前实现的红黑树的结构就得做一下调整了

除了上面呈现出来的模板参数以外，还可以传递自定义的比较规则模板Compare。

下面是map与set的基本框架

原来红黑树中涉及数据比较大小的地方，都得回调传递过来的KeyOfT获取Key后再比较

3. 红黑树的迭代器

3.1 普通迭代器

红黑树的迭代器无非也就是包含一个节点的指针，然后重载指针的各种操作即可。

一般迭代器的实现都是按照中序遍历，遍历完是有序的。所以红黑树迭代器的begin()，应该是树最左侧的节点；对于迭代器的end()，我们就按照NULL来处理。

那红黑树迭代器的++与- -操作是如何实现的呢？

对于++操作：

对于- -操作：为了方便_node == nullptr时找树最右侧的节点，我们再给迭代器加一个指针root记录树的根。

template<class Value>class RBTreeIterator{typedef TreeNode<Value> Node;typedef RBTreeIterator<Value> Self;private:Node* _node;Node* _root;public:RBTreeIterator(Node* data,Node* root):_node(data),_root(root){}Self& operator++(){//右树存在，找右树的最左侧节点if (_node->_right){Node* leftMost = _node->_right;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;//直接跳转至}else  //右树不存在，继续向上{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}//parent不存在或者该遍历根了_node = parent;}return *this;}Self& operator--(){//特殊处理end()，找整棵树的最右侧节点if (_node == nullptr){Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}//左子树存在，找左子树最右侧节点else if (_node->_left){Node* rightMost = _node->_left;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{//左子树不存在，当前树遍历完，继续向上Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}//parent不存在或者该遍历根了_node = parent;}return *this;}Value& operator*(){return _node->_data;}Value* operator->(){return &_node->_data;}bool operator==(const Self& it){return _node == it._node;}bool operator!=(const Self& it){return _node != it._node;}};

3.2 const迭代器

对于const迭代器而言，无非就是数据不能被修改，那也就是针对迭代器的operator* 与operator->了。

那就先改造底层的迭代器

然后map与set在上层封一下就行了

通过上面的我们可以看到，使用const迭代器以后确实都不能修改了；但是普通迭代器存在一个问题：

所以上层在传递给下层时，我们可以将k设置为const

到这里我们的迭代器就完美了。

3.3 map的operator[ ]

我们都知道map重载的[ ]既可以充当插入，也可以充当修改。那么在底层它用的就是insert。（点击可看map的使用）
那我们就需要改变一下insert的返回值了。

到这里我们map与set的封装就结束了。

4. 完整代码

4.1 RBTree

#pragma once
namespace my
{//颜色enum Color{RED = 0,BLACK};template<class Value>struct TreeNode{Value _data;TreeNode<Value>* _left;TreeNode<Value>* _right;TreeNode<Value>* _parent;//前驱节点Color _col;TreeNode(const Value& data): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)//默认新节点为红色的{}};template<class Value,class Ref,class Ptr>class RBTreeIterator{typedef TreeNode<Value> Node;typedef RBTreeIterator<Value,Ref,Ptr> Self;private:Node* _node;Node* _root;public:RBTreeIterator(Node* data,Node* root):_node(data),_root(root){}Self& operator++(){//右树存在，找右树的最左侧节点if (_node->_right){Node* leftMost = _node->_right;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;//直接跳转至}else  //右树不存在，继续向上{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}//parent不存在或者该遍历根了_node = parent;}return *this;}Self& operator--(){//特殊处理end()，找整棵树的最右侧节点if (_node == nullptr){Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}//左子树存在，找左子树最右侧节点else if (_node->_left){Node* rightMost = _node->_left;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{//左子树不存在，当前树遍历完，继续向上Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}//parent不存在或者该遍历根了_node = parent;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator==(const Self& it){return _node == it._node;}bool operator!=(const Self& it){return _node != it._node;}};template<class K,class Value,class KeyOfT>class RBTree{typedef TreeNode<Value> Node;public:typedef RBTreeIterator<Value,Value&,Value*> Iterator;typedef RBTreeIterator<Value,const Value&,const Value*> ConstIterator;Iterator Begin(){Node* leftMost = _root;//找最左侧的节点while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return Iterator(leftMost,_root);}Iterator End(){return Iterator(nullptr,_root);} ConstIterator Begin() const{Node* leftMost = _root;//找最左侧的节点while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return ConstIterator(leftMost,_root);}ConstIterator End() const{return ConstIterator(nullptr,_root);}RBTree() = default;RBTree(const RBTree<K, Value,KeyOfT>& tree){this->_root = Copy(tree._root);}//类里面直接写类名，无需传递模板参数也可。RBTree& operator=(RBTree tree){swap(this->_root, tree._root);//现代写法return *this;}~RBTree(){Destroy(_root);}pair<Iterator,bool> insert(const Value& data){if (_root == nullptr){_root = new Node(data);//如果插入的节点是头节点，需要遵守规则2（根是黑的）//需要默认的红色改为黑_root->_col = BLACK;return make_pair(Iterator(_root,_root),true);}KeyOfT kot;Node* cur = _root;Node* parent = cur->_parent;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;}elsereturn make_pair(Iterator(cur, _root), false);}//孩子连父亲cur = new Node(data);Node* newnode = cur;cur->_parent = parent;//父亲连孩子if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_left = cur;//检查是否违反红黑树的规则//如果父亲存在且为红，则违反规则while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){//根据爷爷节点找叔叔Node* uncle = grandfather->_right;//如果叔叔存在且为红,仅需要变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//然后继续向上调整cur = grandfather;parent = cur->_parent;}//如果叔叔不存在 或者存在且为黑，需要旋转+变色else{//判断单旋(直树)还是双旋(弯树)//单旋if (parent->_left == cur){	//       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;//旋转后已经符合规则，无需再调整了}}//grandfather->_right == parentelse{Node* uncle = grandfather->_left;//如果叔叔存在且为红,仅需要变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续调整cur = grandfather;parent = cur->_parent;}//如果叔叔不存在 或者存在且为黑，需要旋转+变色else{//    g// u     p//           cif (parent->_right == cur){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//      g//   u      p//	      celse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//父亲不存在，或者父亲为黑时，无需判断，直接将根变黑_root->_col = BLACK;return make_pair(Iterator(newnode, _root), true);}Iterator* find(const K& key){Node* cur = _root;KeyOfT kot;while (cur){if ( kot(cur->_data)< key)cur = cur->_right;else if (kot(cur->_data) > key)cur = cur->_left;elsereturn  Iterator(cur,_root);}return End();}void InOrder(){_InOrder(_root);cout << endl;}bool IsRBTree(){Node* root = _root;if (root == nullptr)//空树也是return true;if (root->_col == RED){cout << "根节点为红色，违反规则" << endl;return false;}//先统计最左侧路径上有多少黑节点作为标准Node* cur = root;int blackNum = 0;while (cur){if (cur->_col == BLACK)blackNum++;cur = cur->_left;}//k用来记录路径中黑节点的个数int k = 0;//在依据标准黑节点的个数，比较其它路径return _IsRBTree(root, blackNum, k);}int Size(){return _Size(_root);}int Height(){return _Height(_root);}private: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;}int _Size(Node* root){if (root == nullptr)return 0;return 1 + _Size(root->_left) + _Size(root->_right);}bool _IsRBTree(Node* root, int blackNum, int k){//一条路径走完，比较黑节点的个数if (root == nullptr){if (blackNum != k){cout << "路径黑节点个数不相等，违反规则" << endl;return false;}return true;}Node* parent = root->_parent;if (parent && root->_col == RED && parent->_col == RED){cout << "存在连续的红节点，违反规则" << endl;return false;}//统计黑节点if (root->_col == BLACK)k++;//统计完根，在依次统计左右子树return _IsRBTree(root->_left, blackNum, k)&& _IsRBTree(root->_right, blackNum, k);}void RotateR(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;//将连将SubL->_parent = parentParent;if (parentParent == nullptr){_root = SubL;}else{if (parentParent->_left == parent)parentParent->_left = SubL;elseparentParent->_right = SubL;}}void RotateL(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;//将连将SubR->_parent = parentParent;if (parentParent == nullptr)_root = SubR;else{if (parentParent->_left == parent)parentParent->_left = SubR;elseparentParent->_right = SubR;}}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;_root->_left = Copy(root->_left);_root->_right = Copy(root->_right);return _root;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}Node* _root;};
}

4.2 MyMap

#pragma once
#include"RBTree.h"namespace my
{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;const_iterator begin()const{return _t.Begin();}const_iterator end() const{return _t.End();}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}pair<iterator, bool> insert(const pair<K, V> kv){return _t.insert(kv);}bool find(const K& key){return _t.find(key);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key,V()));//如果key存在，则返回其对应的value//如果key不存在，则插入它，其value为类型的默认值return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};//void MapPrint(const map<string, string>& m)//{//	map<string, string>::const_iterator it = m.end();//	while (it != m.begin())//	{//		it->first += "x";//		it->second += "y";//		--it;//		cout << it->first << " " << it->second << endl;//	}//}void testmap(){map<string, string> m;m.insert({ "right","右"});m.insert({ "up","上"});m.insert({ "down","下"});m.insert({ "left","左"});m["left"] = "修改左";m["offer"] = "新增";//cout << m.find(3) << endl;//for (auto& e : m)//{//	cout << e.first << " " << e.second << endl;//}//MapPrint(m);map<string,string>::iterator it = m.end();while (it != m.begin()){//it->second += "y";//it->first += "x";--it;cout << it->first << " " << it->second << endl;}cout << endl;}
}

4.3 MySet

#pragma once
#include"RBTree.h"namespace my
{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>::ConstIterator const_iterator;const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}pair<iterator, bool> insert(const K& key){return _t.insert(key);}bool find(const K& key){return _t.find(key);}private:RBTree<K, const K, SetKeyOfT> _t;};//void SetPrint(const set<int>& s)//{//	set<int>::const_iterator it = s.end();//	while (it != s.begin())//	{//		//*it = 20;//		--it;//		cout << *it << " ";//	}//	cout << endl;//}void testset(){set<int> s;pair<set<int>::iterator,bool> ret = s.insert(5);cout << *(ret.first) << endl;//查看insert的返回值s.insert(2);s.insert(8);s.insert(15);s.insert(2);s.insert(9);set<int>::iterator it = s.end();while (it != s.begin()){//*it = 10;--it;cout << *it <<" ";}cout << endl;//SetPrint(s);}
}