模拟实现map和set

• map和set是红黑树的两种不同封装形式，底层使用同一颗泛型结构的红黑树，只是存储类型不同。
• set是红黑树的K模型，存储key；map是红黑树的KV模型，存储pair<key,value>。

下面的代码和讲解着重体现红黑树的底层实现和map\set上层封装的衔接。红黑树的具体结构，基本操作，实现原理等内容请阅读下面几篇文章：

1. 【高阶数据结构】二叉搜索树 {概念；实现：核心结构，增删查，默认成员函数；应用：K模型和KV模型；性能分析；相关练习}
2. 【STL】map和set的介绍和使用 {关联式容器；键值对；map和set；multimap和multiset；OJ练习}
3. 【高阶数据结构】AVL树 {概念及实现；节点的定义；插入并调整平衡因子；旋转操作：左单旋，右单旋，左右双旋，右左双旋；AVL树的验证及性能分析}
4. 【高阶数据结构】红黑树 {概念及性质；红黑树节点的定义；红黑树插入操作详细解释；红黑树的验证}

---

一、核心结构

• 问题一：map和set底层使用同一颗泛型结构的红黑树，如何处理map(pair<key,value>)和set(key)存储值不同的问题？

  解决方案：泛型底层红黑树的存储类型，通过不同的实例化参数，实现出map和set。

• 问题二：在进行查找、插入、删除操作时，要对key值进行比较。在同一模版中，如何区别比较map和set中的key值？

  解决方案：通过传入仿函数KofT(KeyofTree)解决。如果是set，KofT对象返回data的值；如果是map，KofT对象返回data.first的值；

  注意：pair中重载了关系运算符，但first和second都参与运算，不符合要求。要求只比较pair.first (key)。

1.1 RBTreeNode && RBTree

// RBTree.hpp
enum Color{RED,BLACK
};template <class T>
struct RBTreeNode{RBTreeNode<T> *_left;RBTreeNode<T> *_right;RBTreeNode<T> *_parent;T _data; //泛型底层红黑树的存储类型，通过不同的实例化参数，实现出map和set。Color _color;RBTreeNode(const T &data = T(), Color color = RED):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_color(color){}
};//
// K: key的类型，
// T: 如果是map，则为pair<K, V>; 如果是set，则为K
// KofT: 通过T类型的data来获取key的一个仿函数类
template <class K, class T, class KofT>
class RBTree{typedef RBTreeNode<T> Node; //第二个模版参数T，决定红黑树的存储类型Node *_root = nullptr;//......
};

---

1.2 set & map封装

// Set.hpp
namespace zty{template <class K>class set{struct SetKofT{ //用于取出data中的keyconst K& operator()(const K &k){return k; } };typedef RBTree<K, K, SetKofT> RBT; //set是K模型的红黑树，只存储key值RBT _rbt;//......};
}//
// Map.hpp
namespace zty{template <class K, class V>class map{struct MapKofT{ //用于取出data中的keyconst K& operator()(const pair<K,V>& kv){return kv.first;}};typedef RBTree<K, pair<K,V>, MapKofT> RBT; //map是KV模型的红黑树，存储pair<K,V>键值对RBT _rbt;//......};
}

二、插入和查找

2.1 RBTree::insert

// RBTree.hpp
template <class K, class T, class KofT>
pair<typename RBTree<K,T,KofT>::iterator, bool> RBTree<K,T,KofT>::Insert(const T &data)
{KofT kot; //创建KofT对象，用于取出data中的keyif(_root == nullptr){_root = new Node(data, BLACK);return make_pair(iterator(_root), true); //返回pair<iterator, bool>，方便实现operator[]。}Node *cur = _root;Node *parent = nullptr;while(cur != nullptr){if(kot(data) > kot(cur->_data)) //不管是map还是set都能正确的取出key进行比较。{parent = cur;cur = cur->_right;}else if(kot(data) < kot(cur->_data)){parent  = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data,RED);Node *newnode = cur; //在调整红黑树的过程中cur的指向会改变，所以要提前记录新节点的指针。if(kot(data) > kot(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//上一次循环中grandparent 为根节点，此次循环parent == nullptrwhile(parent != nullptr && parent->_color == RED) {//......具体内容请参考红黑树章节内容} //end of whileif(cur == _root)cur->_color = BLACK;return make_pair(iterator(newnode), true); //返回pair<iterator, bool>，方便实现operator[]。
}

---

2.2 RBTree::find

//RBTree.hpp
template <class K, class T, class KofT>
typename RBTree<K,T,KofT>::iterator RBTree<K,T,KofT>::Find(const K &k){KofT kot;if(_root == nullptr){return end();}Node *cur = _root;  while(cur != nullptr){if(k > kot(cur->_data)){cur = cur->_right;}else if(k < kot(cur->_data)){cur = cur->_left;}else{return cur;}}return end();
}

2.3 set & map封装

//Set.hpp
namespace zty{template <class K>class set{//......bool Insert(const K& k){return _rbt.Insert(k).second;}iterator Find(const K& k){return _rbt.Find(k);}};
}//
// Map.hpp
namespace zty{template <class K, class V>class map{//......pair<iterator, bool> Insert(const pair<K,V>& kv){return _rbt.Insert(kv);}V& operator[](const K& k){ //Insert返回pair<iterator, bool>，方便实现operator[]。pair<iterator, bool> ret = Insert(make_pair(k, V()));return ret.first->second;}iterator Find(const K& k){return _rbt.Find(k);}};
}

---

三、迭代器

问题三：map和set（红黑树）的迭代器如何实现？

1. 红黑树的迭代器底层封装一个指向节点的指针，基本操作请参照list迭代器的实现。

2. 红黑树迭代器的实现难点在于++和–操作。

3. 通过二叉树的中序遍历规则得出：（中序：左子树，根，右子树）

   1. begin是中序遍历的第一个节点，即二叉树的最左（最小）节点。

   2. end是中序遍历最后一个节点的下一个位置（左闭右开），这里我们设为nullptr。

   3. ++操作：（中序：左子树，根，右子树）

      1. 如果当前节点的右子树不为空，++就是找右子树中序的第一个节点（最左节点）。

      2. 如果当前节点的右子树为空，++就是找孩子不是右节点的那个祖先。

         提示：右子树为空或孩子是右节点，说明这棵子树已经遍历访问完了。

   4. –操作：和++相反（右子树，根，左子树）

      1. 如果当前节点的左子树不为空，–就是找左子树的最右节点。

      2. 如果当前节点的左子树为空，–就是找孩子不是左节点的那个祖先。

         提示：左子树为空或孩子是左节点，说明这棵子树已经遍历访问完了。

3.1 RBT_iterator

// RBTree.hpp
template<class T, class Ref, class Ptr>
class RBT_iterator{typedef RBT_iterator<T, Ref, Ptr> iterator;typedef RBTreeNode<T> Node;Node *_pnode; //红黑树的迭代器底层封装一个指向节点的指针
public://基本操作请参照list迭代器的实现，不做过多解释RBT_iterator(Node *pnode = nullptr):_pnode(pnode){}Ref operator*() const{ return _pnode->_data;}Ptr operator->() const{return &_pnode->_data;}bool operator==(const iterator &it) const{return _pnode == it._pnode;}bool operator!=(const iterator &it) const{return _pnode != it._pnode;}//红黑树的迭代器的实现难点在于++和--操作iterator& operator++(){if(_pnode->_right != nullptr) //如果当前节点的右子树不为空，++就是找右子树中序的第一个节点（最左节点）。{Node *left = _pnode->_right;while(left->_left != nullptr){left= left->_left;}_pnode = left;}else{ //如果当前节点的右子树为空，++就是找孩子不是右节点的那个祖先。Node *parent = _pnode->_parent;Node *cur = _pnode;while(parent != nullptr && cur == parent->_right) //parent == nullptr表示遍历到尾{parent = parent->_parent;cur = cur->_parent;}_pnode = parent;}return *this;}iterator& operator--(){if(_pnode->_left != nullptr) //如果当前节点的左子树不为空，--就是找左子树的最右节点。{Node *right = _pnode->_left;while(right->_right != nullptr){right = right->_right;}_pnode = right;}else{ //如果当前节点的左子树为空，--就是找孩子不是左节点的那个祖先。Node *parent = _pnode->_parent;Node *cur = _pnode;while(parent != nullptr && cur == parent->_left) //parent == nullptr表示遍历到头{parent = parent->_parent;cur = cur->_parent;}_pnode = parent;}return *this;}
};//template <class K, class T, class KofT>
class RBTree{
//......
public:typedef RBT_iterator<T, T&, T*> iterator; //普通迭代器typedef RBT_iterator<T, const T&, const T*> const_iterator; //const迭代器iterator begin(){ //begin是中序遍历的第一个节点，即二叉树的最左（最小）节点。Node *left = _root;while(left != nullptr && left->_left != nullptr){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr); //end是中序遍历最后一个节点的下一个位置（左闭右开），这里我们设为nullptr。}
};

---

3.2 set & map封装

// Set.hpp
namespace zty{template <class K>class set{//......typedef RBTree<K, K, SetKofT> RBT;   public:typedef typename RBT::iterator iterator; //set的迭代器类型typedef typename RBT::const_iterator const_iterator; //const迭代器iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}};
}//
// Map.hpp
namespace zty{template <class K, class V>//......typedef RBTree<K, pair<K,V>, MapKofT> RBT;public:typedef typename RBT::iterator iterator; //map的迭代器类型typedef typename RBT::const_iterator const_iterator; //const迭代器iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}};
}

---

四、STL中的红黑树结构

• 为了后续实现关联式容器简单，STL红黑树的实现中增加一个头结点，因为根节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的_parent域指向红黑树的根节点，_left域指向红黑树中最小的节点，_right域指向红黑树中最大的节点。

• STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：