一、前言
在标准库中map和set的底层结构是使用红黑树来实现的。但是，map是key，value类型的容器，set是key类型的容器，那我们是不是要分别写一个 kv类型的红黑树和key类型的红黑树去分别封装呢？还是说可以使用同一棵树去实现呢？
下面我们从标准库源码去看一看它是怎么封装的。
二、标准源码分析
我们直接上源码
从上面的源码中，我们看出：
1、set 和 map 的红黑树结构都有两个模板参数：key_type 和 value_type。
2、set 的红黑树结构的 key_type 和 value_type的本质都是key。
3、map 的红黑树结构的 key_type 和 value_type 分别是 key 和 pair。
* 而红黑树结点所存数据类型是由模板参数 value 来控制的。即通过vlaue 我们可以知道红黑树存储的是key类型的set，还是pair类型的map。
即一棵泛型结构的红黑树，通过不同实例化参数，实现出了map和set。
三、泛型红黑树
1、结点
为了实现结点的泛型，我们可以直接使用一个模板参数T，这样T既可以是key类型，也可以是pair<key, value>的类型。至于它存储的数据到底是哪种类型，我们可以在set和map的封装中通过去传参数来确定。
enum Colour { RED, BLACK }; template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; //pair<K, V> _kv; T _data; Colour _col; RBTreeNode(const T& data, Colour col = RED) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(col) {} };
2、红黑树框架
对于T模板参数可能是键值Key，也可能是由Key和Value共同构成的键值对。
template<class K, class T> struct RBTree { typedef RBTreeNode<T> Node; private: Node* _root = nullptr; }
3、set框架
如果是set容器，那么它传入底层红黑树的模板参数就是Key和Key。
template<class K> class set { private: RBTree<K,K> _t; };
4、map框架
如果是map容器，传入底层红黑树的模板参数就是Key和Key和value的键值对。
class map { private: RBTree<K, pair<K,V>> _t; };
四、仿函数
红黑树变成泛型后就出现了一个问题：插入的时候data的大小如何去进行比较呢？我们并不知道是什么类型，是key，还是pair的比较，而我们刚开始kv结构就直接用kv.first去比较了。但是现在我们并不能确定它到底是哪种类型。对于set是Key，可以比较，对于map是pair，那我们要取其中的first来比较。
那么这里，我们就需要一个仿函数来帮助我们解决这个问题了。所以正确的红黑树框架如下：
template<class K, class T, class KeyOfT> struct RBTree { typedef RBTreeNode<T> Node; private: Node* _root = nullptr; };
其中第三个模板参数就是我们要自己实现的一个仿函数。
template<class K> class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: private: RBTree<K, K, SetKeyOfT> _t; };
template<class K, class V> class map { struct MapKeyOfT { const K& operator()(const pair<K,V>& kv) { return kv.first; } }; public： private: RBTree<K, pair<K, V>, MapKeyOfT> _t; };
因此我们红黑树的插入的查找部分就可以使用仿函数来实现。
KeyOfT kot; Node* parent = nullptr; Node* cur = _root; 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 false; } } cur = new Node(data); Node* newnode = cur; if (kot(parent->_data) > kot(data)) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent;
五、迭代器
迭代器的定义：
template<class T, class Ref, class Ptr> struct __RBIterator { typedef RBTreeNode<T> Node; typedef __RBIterator<T, Ref, Ptr> RBIterator; Node* _node; __RBIterator(const Node*& node) :_node(node) {} }
解引用操作，返回对应结点数据的引用
Ref operator*() { return _node->_data; }
成员访问操作符，返回结点数据的引用
Ptr operator->() { return &_node->_data; }
等于和不等于
bool operator !=(const Self & s) const { return _node != s._node; } bool operator ==(const Self& s) const { return _node == s._node; }
++的重载
1、右子树不为空，++就是找右子树中序第一个（最左节点）
2、右子树为空，++找孩子是父亲左的那个祖先。
Self& operator++() { if (_node->_right) { Node* left = _node->_right; while (left->_left) { left = left->_left; } _node = left; } else { Node* parent = _node->_parent; Node* cur = _node; while (parent && cur == parent->_right) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; }
--的重载
对于–，如果是根，–就是左子树，找到左子树最大的那一个（最右节点）
1、如果节点的左子树不为空，--找左子树最右的节点。
2、如果节点的左子树为空，--找祖先（孩子是父亲的右的祖先）。
Self& operator--() { if (_node->_left) { Node* max = _node->_left; while (max->_right) { max = max->_right; } _node = max; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent&&cur==parent->_left) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; }
有了上面的迭代器模板，我们就可以实现红黑树的迭代器了
template<class K, class T,class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: typedef __RBTreeIterator<T> iterator; iterator begin() { Node* left = _root; while (left && left->_left) { left = left->_left; } return iterator(left); } iterator end() { return iterator(nullptr); } }；
六、红黑树代码
template<class K, class T, class KeyOfT> struct RBTree { typedef RBTreeNode<T> Node; public: typedef _RBIterator<T, T&, T*> iterator; typedef _RBIterator<T, const T&, const T*> const_iterator; iterator begin() { Node* left = _root; while (left && left->_left) { left = left->_left; } return iterator(left); } iterator end() { return iterator(nullptr); } pair<iterator, bool> insert(const T& data) { KeyOfT kot; if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true) } Node* parent = nullptr; Node* cur = _root; 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(parent->_data) > kot(data)) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; assert(grandfather); assert(grandfather->_col == BLACK); if (parent == grandfather->_left) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上处理 cur = grandfather; parent = cur->_parent; } // uncle 不存在 + 存在且为黑 else { 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; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上处理 cur = grandfather; parent = cur->_parent; } else { 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; return make_pair(iterator(newnode), true); } private: void RotateL(Node* parent) //左单旋 { Node* subR = parent->_right; Node* subRL = subR->_left; Node* pparent = parent->_parent; subR->_left = parent; parent->_parent = subR; parent->_right = subRL; if (subRL) subRL->_parent = parent; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subR; else pparent->_right = subR; subR->_parent = pparent; } } void RotateR(Node* parent) //右单旋 { Node* subL = parent->_left; Node* subLR = subL->_right; Node* pparent = parent->_parent; parent->_parent = subL; subL->_right = parent; parent->_left = subLR; if (subLR) subLR->_parent = parent; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subL; else pparent->_right = subL; subL->_parent = pparent; } } private: Node* _root = nullptr; };
七、set的封装
#pragma once #include"RBTree.h" namespace zdl { template<class K> class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: //typename:没有实例化的模板，区分不了是静态变量还是类型，typename告诉编译器是类型 typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; iterator begin() { _t.begin(); } iterator end() { _t.end(); } pair<iterator, bool> insert(const K& key) { return _t.insert(key); } private: RBTree<K, K, SetKeyOfT> _t; }; }
八、map的封装
#pragma once #include"RBTree.h" namespace zdl { 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<K, V>, MapKeyOfT>::iterator iterator; iterator begin() { _t.begin(); } iterator end() { _t.end(); } pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.insert(kv); } V& operator[](const K& key)const { pair<iterator, bool> ret = insert(make_pair(K, V())); return ret.first->second; } private: RBTree<K, pair<K, V>, MapKeyOfT> _t; }; }
