C++的STL库中，把红黑树封装为了两个容器map与set，本博客将基于红黑树，来实现map和set的封装。如果不了解红黑树，可见博客[数据结构/C++：红黑树]
将红黑树封装为泛型
我们现有如下结构的红黑树：
enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; pair<K, V> _kv; Colour _col; RBTreeNode(const pair<K, V>& kv) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _col(RED) {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: private: Node* _root = nullptr; };
基本结构：RBTreeNode是红黑树的节点，RBTree则是红黑树本体，RBTree内部的_root 是整颗红黑树的根。
这颗红黑树有一个问题，在于它的节点，存储的值是pair<K, V> _kv;，也就是键值对的形式来存储数据。但是在STL中，set是只存储key值的，只有map存储键值对。如果我们要使得红黑树可以同
时作为map和set的底层，那么我们就要想办法让这个红黑树的节点可以存储多种类型的数据。也就是让节点RBTreeNode内部存储泛型：
template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col; T _data; RBTreeNode(const T& data) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) {} };
我们把原先的模板template<class K, class V>换成了template<class T>，并把pair<K, V> _kv;改为了T _data;，此时我们存储的数据就不一定是键值对的格式了。
当我们需要存储键值对，那么T就是pair<K, V>
当我们只存储key值，那么T就是K
相应的，我们的RBTree主体也要修改一下：
template<class T> class RBTree { typedef RBTreeNode<T> Node; public: private: Node* _root = nullptr; };
现在我们先尝试对红黑树进行封装，写出一个map和set的基本框架：
mySet.h：
template<class K> class set { public: private: RBTree<K> _t; };
myMap.h：
template<class K, class V> class map { public: private: RBTree<pair<K, V>> _t; };
经过这一层封装，我们的map和set的基本框架就有了，但是有一个小问题：map和set中的key值是不可以修改的，所以我们要给K的类型加上const修饰。不过要注意map中的value是可以修改的，所以不是给pair加上const修饰，而是只修饰K。
mySet.h：
template<class K> class set { public: private: RBTree<const K> _t; };
myMap.h：
template<class K, class V> class map { public: private: RBTree<pair<const K, V>> _t; };
Find接口
到此为止，我们仅完成了基本框架的搭建，接下来我们看看红黑树的Find接口：
Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) cur = cur->_right; else if (cur->_kv.first > key) cur = cur->_left; else return cur; } return nullptr; }
以上Find接口，是在红黑树没有修改前的接口，我们看看它目前有什么问题：
- 我们已经把模板从
template<class K, class V>换成了template<class T>，此时已经没有K这个类型了，我们在给Find传参的时候，不可以直接传const K& key
但是我们既然要在红黑树中查找，一定是要查key的，也就是说，我们不可以遗漏K这个类型，因此我们的模板参数要再加一个K，变成：template<class K, class T>。前面的K用于传入key的类型，后面的T用于传入红黑树存储的数据类型。
template<class K, class T> class RBTree { typedef RBTreeNode<T> Node; public: private: Node* _root = nullptr; };
cur->_kv.first这个过程是有问题的，其意图通过找到key值，然后比较当前节点与查找节点的大小，来决定下一步去左子树还是右子树找节点。但是我们对RBTreeNode改造后，其内部存储的已经不是_kv了，而是_data，对于set而言，这个_data是没有first这个成员的，因此我们不能直接通过_kv.first这种方式来访问key。
这个问题的关键在于，我们想要拿到红黑树节点中的key值，但是对于map而言，这个key是_data中的成员变量first；而对于set而言，这个key就是_data。也就是map和set取用key值的方式不同，我们无法统一处理。
为了解决这个问题，我们就要想办法，用统一的方式从_data中获得map和set的key。此时可以在红黑树的外部写仿函数，然后在仿函数的内部返回key值。对于红黑树而言，不论是什么类型，只需要向仿函数传入_data，然后接受返回值就可以拿到key。
这里我们给红黑树传入第三个模板参数KeyOfT：
template<class K, class T, class keyOfT>//keyOfT仿函数，取出T对象中的key class RBTree { typedef RBTreeNode<T> Node; public: private: Node* _root = nullptr; };
接着就是set的仿函数：
struct SetKeyOfT { const K& operator()(const K& key) { return key; } };
对于set而言，T就是K，也就是_data的类型为K，要从_data中得到key，直接返回_data即可。
map的仿函数：
struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } };
对于map而言，T是pair<K, V>，也就是_data的类型为pair<K, V>，要从_data中得到key，需要返回_data的第一个成员first。
然后我们再对Find接口进行改造，把所有需要取用key的地方都改用仿函数：
bool Find(const K& key) { keyOfT 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 true; } return false; }
其中kot就是仿函数keyOfT 实例化出的对象。
当前框架如下：
RBTree：
template<class K, class T, class keyOfT>//keyOfT仿函数，取出T对象中的key class RBTree { typedef RBTreeNode<T> Node; public: private: Node* _root = nullptr; };
mySet.h：
template<class K> class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: iterator find(const K& key) { return _t.Find(key); } private: RBTree<K, const K, SetKeyOfT> _t; };
myMap.h：
template<class K, class V> class map { struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: bool find(const K& key) { return _t.Find(key); } private: RBTree<K, pair<const K, V>, MapKeyOfT> _t; };
迭代器
先搭建出一个迭代器iterator的基本框架：
template<class T, class Ptr, class Ref> struct RBTreeIterator { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, Ptr, Ref> Self; Node* _node; RBTreeIterator(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; } };
在此我不讲解这个框架是如何搭建的了，如果不明白，可见博客[C++：迭代器的封装思想]
现在的主要问题在于：迭代器应该如何行动，走到下一个节点？
通过迭代器遍历与直接中序遍历一颗红黑树不一样，中序遍历可以通过递归，自动按照左子树 - 根 - 右子树的顺序遍历。但是迭代器只知道当前节点，不知道前一步与后一步是谁。比如下图：
当前迭代器处于这个蓝色框中的节点，请问它下一步是往左子树走，右子树走，还是父节点走？
值得注意的是，当迭代器指向哪一个节点，说明当前就遍历到了哪一个节点，此时迭代器处于这个蓝色框中的节点，说明这个节点的左子树已经遍历完了，刚好遍历到这个蓝色框节点。因此下一步就是中序遍历右子树，即让迭代器走到当前节点的右子树位置，并且找到右子树的最左节点，该节点就是下一个节点。
但是如果右子树为空呢？
比如我们遍历到以下节点： 
此时说明以蓝色框为根的整颗子树都遍历完毕了，那么我们就要向上移动，走到当前节点的父节点处：
但是对于这个父节点而言，其左子树遍历完了，刚刚右子树遍历完毕后，走到了当前节点，说明当前节点也遍历完毕了（中序遍历，根节点一定在右子树前遍历完），此时还要向上移动，以此类推，直到走到第一个当前节点是父节点的左子树的情况。
至此，我们就大概清除迭代器移动的情况了：
如果迭代器当前节点的右子树不为空，遍历右子树（找到右子树的最左节点）
如果迭代器当前节点的右子树为空，向上找前一个节点是当前节点的左子树的节点
代码如下：
Self& operator++() { if (_node->_right)//右不为空，找右子树最左节点 { Node* subLeft = _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else//右为空 { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = parent; parent = cur->_parent; } _node = parent;//parent前一个节点cur是其左子树 } return *this; }
operator--同理，只是相反的：
如果迭代器当前节点的左子树不为空，遍历左子树（找到左子树的最右节点）
如果迭代器当前节点的左子树为空，向上找前一个节点是当前节点的右子树的节点
代码如下：
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 && cur == parent->_left) { cur = parent; parent = cur->_parent; } _node = parent;//第一个为cur右子树的祖先 } return *this; }
接下来我们要把迭代器的类封装进RBTree中，首先定义出iterator和const_iterator：
typedef RBTreeIterator<T, T*, T&> iterator; typedef RBTreeIterator<T, const T*, const T&> const_iterator;
接着写出begin，end的接口：
直接拿空指针构造end接口：
iterator end() { return iterator(nullptr); }
要注意的是，begin接口不是直接拿_root去构造iterator，中序遍历的第一个节点是整棵树的最左侧节点，所以要先找到最左侧节点，再构造：
iterator begin() { Node* subLeft = _root; while (subLeft && subLeft->_left) { subLeft = subLeft->_left; } return iterator(subLeft); }
const_iterator同理：
const_iterator begin() const { Node* subLeft = _root; while (subLeft && subLeft->_left) { subLeft = subLeft->_left; } return const_iterator(subLeft); } const_iterator end() const { return const_iterator(nullptr); }
接着我们再封装出map和set的迭代器，直接复用RBTree的迭代器接口即可：
mySet.h：
typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator; typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); }
myMap.h：
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator; typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); }
这里有一个注意点，在typedef的时候，由于我们的RBTree是一个模板，我们到模板的域中访问了变量。编译器无法区分模板中const_iterator的是变量还是类型，所以编译器会默认把它视为一个变量。如果它是一个类型，那么我们要明确告诉编译器，即通过typename 关键词。不然const_iterator会被识别为一个变量，而不是一个类型。
由于STL中，find接口返回的是迭代器，现在我们已经实现了迭代器，所以我们还要把find的返回值改为迭代器，而不是布尔值，这里不做展示了，可以到文章末尾的代码块中查看。
insert接口
在map和set中，insert的返回值比较特殊，其会返回pair<iterator, bool>
如果插入值data原先存在，此时iterator指向原先的data节点，bool值返回false表示插入失败
如果插入值
data原先不存在，此时iterator指向新插入的data节点，bool值返回true表示插入成功
因此我们还要改一下Insert接口：
如果插入成功：
return make_pair(iterator(newNode), true);
如果插入失败：
return make_pair(iterator(cur), false);
由于插入逻辑比较复杂，若需要看整段代码，可以在文章末尾查看。
map的operator[]接口
map还重载了[]，这个重载比较复杂，但是非常有用，我们先看到声明：
V& operator[] (const K& key);
其接收一个K类型的参数，也就是接受一个key，然后返回一个V&，也就是一个value的引用。其功能为：接受一个key值，然后返回这个key对应的value的引用。
其等效于下面的代码：
(*((this->insert(make_pair(k,V()))).first)).second
现在我们来解读以上代码，我们将其拆解为四个部分：make_pair(k, V( )) + this->insert( ) + ( ).first + (*( )).second，我们一层层解析。
第一层：
make_pair(k, V( ))
第二层：
this->insert( )
上一层我们构造了一个pair<key, value>，然后它被作为参数，传入到这个insert中，相当于把刚刚构造的节点插入进map中。map的插入后，不论成功与否，都会返回一个pair<iterator, bool>，iterator用于指向key的迭代器，bool用于标识插入是否成功。所以这一层最后得到了一个pair，分别存储了指向key的迭代器和bool。
第三层：
( ).first
上一层中我们得到了pair<iterator, bool>，这一层访问它的first，也就是访问了iterator，所以这一层得到了指向key值的迭代器。
第四层：
(*( )).second
我们上一层拿到了指向key的迭代器，这一层先对迭代器解引用*( )，此时就得到了一个map的节点。而map的节点是pair<key, value>，所以我们解引用得到了一个pair，随后通过( ).second访问pair<key, value>的second，也就是value。最后返回这个value的引用。
所以我们最后得到了key对应的value的引用。那么这有什么用呢？
假设我们有一个map<string, string>类型的字典dict，通过这个来展示operator[ ]的功能：
- 插入一个key值：
dict["left"];
以上语句在dict中插入了一个key = "left"但是没有value的节点
- 插入一对
key - value：dict["left"] = "左边";
由于operator[ ]返回的是对应的引用，因此我们可以直接给返回值赋值，此时我们就插入了一个节点key = "left" - value = "左边" - 修改
key对应的value：dict[“coffe”] = "咖啡";
如果我们的dict原先就存在key = "coffe"的节点，以上代码可以修改这个key的value值 - 得到
key对应的value：cout << dict["coffe"] << endl;
由于我们拿到的是value的引用，我们也可以把它作为一个值赋值给别人或者输出
可以看到，operator[]的功能非常丰富，整体来说还是一个很好用的重载。
operator[]实现：
由于我们先前已经用insert铺垫好了，我们直接调用insert，然后返回value的引用即可：
V& operator[](const K& key) { pair<K, V>& ret = insert(make_pair(key, V())); return ret.first->second; }
总代码展示
RBTree.h：
#pragma once #include <iostream> #include <assert.h> using namespace std; enum Colour { RED, BLACK }; template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col; T _data; RBTreeNode(const T& data) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) {} }; template<class T, class Ptr, class Ref> struct RBTreeIterator { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, Ptr, Ref> Self; Node* _node; RBTreeIterator(Node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self& operator++() { if (_node->_right)//右不为空 { Node* subLeft = _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else//右为空 { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = parent; parent = cur->_parent; } _node = parent;//第一个为cur左子树的祖先 } 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 && cur == parent->_left) { cur = parent; parent = cur->_parent; } _node = parent;//第一个为cur右子树的祖先 } return *this; } bool operator!=(const Self& s) { return _node != s._node; } bool operator==(const Self& s) { return _node == s._node; } }; template<class K, class T, class keyOfT>//keyOfT仿函数，取出T对象中的key class RBTree { typedef RBTreeNode<T> Node; public: typedef RBTreeIterator<T, T*, T&> iterator; typedef RBTreeIterator<T, const T*, const T&> const_iterator; iterator begin() { Node* subLeft = _root; while (subLeft && subLeft->_left) { subLeft = subLeft->_left; } return iterator(subLeft); } iterator end() { return iterator(nullptr); } const_iterator begin() const { Node* subLeft = _root; while (subLeft && subLeft->_left) { subLeft = subLeft->_left; } return const_iterator(subLeft); } const_iterator end() const { return const_iterator(nullptr); } 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; keyOfT 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); if (kot(parent->_data) > kot(data)) parent->_left = cur; else parent->_right = cur; cur->_parent = parent; Node* newNode = cur; while (parent && parent->_col == RED)//只有parent为红，才更新 (parent可能不存在) { Node* grandfather = parent->_parent; if (parent == grandfather->_left) { Node* uncle = grandfather->_right; //uncle存在且为红节点 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//uncle不存在或为黑节点 (旋转) { if (cur == parent->_left) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break;//旋转后一定平衡 } } else { Node* uncle = grandfather->_left; //uncle存在且为红节点 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//uncle不存在或为黑节点 (旋转) { if (cur == parent->_right) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break;//旋转后一定平衡 } } } _root->_col = BLACK;//在循环内部不判断root情况，统一处理 return make_pair(iterator(newNode), true); } //左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* ppNode = parent->_parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } 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; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* ppNode = parent->_parent; parent->_parent = subL; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } } size_t Size() { return _Size(_root); } size_t _Size(Node* root) { if (root == nullptr) return 0;; return _Size(root->_left) + _Size(root->_right) + 1; } iterator Find(const K& key) { keyOfT 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(); } //-------------------------------------------------------------------------------------------------------------- //中序 void InOrder() { _InOrder(_root); cout << "end" << endl; } private: //中序 void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " - "; _InOrder(root->_right); } Node* _root = nullptr; };
mySet.h：
#pragma once #include "RBTree.h" namespace mySet { 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>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } pair<iterator, bool> insert(const K& key) { return _t.Insert(key); } iterator find(const K& key) { return _t.Find(key); } private: RBTree<K, const K, SetKeyOfT> _t; }; }
myMap.h：
#pragma once #include "RBTree.h" namespace myMap { 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>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.Insert(kv); } V& operator[](const K& key) { pair<K, V>& ret = insert(make_pair(key, V())); return ret.first->second; } iterator find(const K& key) { return _t.Find(key); } private: RBTree<K, pair<const K, V>, MapKeyOfT> _t; }; }
