【C++ / STL】封装红黑树实现map和set

一. 源码及框架分析

1.决定搜索类型的传参

1.这是rb_tree主要成员变量，可以看出，rb_tree是实现单个Key还是pair型，节点的类型并不是写死的，而是由第二个参数Value决定，这样即可以实现Key搜索场景的set，又可以实现Key/Value场景的map

2. 这是map的主要成员变量，从这里可以看出map在复用rb_tree时，第二个参数传的是pair型

3. 这是set的主要成员变量，从这里可以看出set在复用rb_tree时，第一个和第二个参数传的是Key型

思考：为什么要传第一个参数

思考：既然第二个参数决定节点的存储类型，为什么还要再传第一个参数Key呢？
第一个参数Key是给find/erase等函数做形参类型的，对于set，两个参数一样，但对于map，insert的是pair型，find/erase的是Key型。

2.KeyOfValue的作用

在rb_tree内，并不知道Value是一个Key值还是pair,在进行插入比较时，需要比较的是Key，而KeyOfValue可以提取出来相比较的两个数据的Key值，可以在map和set调用rb_tree时传入KeyOfValue的方法
源码是通过std::select1st和std:: identity来实现的，这里我改成了在map和set层实现KOV_M和KOV_S的仿函数传给rb_tree,同样也能实现提取Key的效果，具体看下面的代码实现

二. 模拟实现map和set

1. 实现出复用红黑树框架,并支持insert

参照源码，红黑树的第二个参数决定存储的数据类型，这里就需要对原来实现的红黑树做一下调整
【1】在实现insert时，对比节点大小要用map和set层提供的KeyOfValue来提取出要比较的值
【2】为了支持map的实现，返回值改为pair型，pair的一个参数为插入节点的迭代器，第二个节点为是否成功插入

rb_tree基本结构

//rb_tree
template <class K, class V,class KeyOfValue,class Compare=std::less<K>>
class RBTree
{
public:typedef RBTreeNode<V> Node;typedef RBTreeIterator<V, V&, V*> Iterator;typedef RBTreeIterator<V, const V&, const  V*> ConstIterator;std::pair<Iterator,bool> Insert(const V& value);Node*  _root=nullptr;Iterator Find(K& key);
private:Node*  _root=nullptr;void  RorateRL(Node* root)；void  RorateLR(Node* root)；void RorateR(Node* root)；void RorateL(Node* root)；};

insert实现

template <class K, class V, class KeyOfValue, class Compare>
std::pair<RBTreeIterator<V, V&, V*>, bool> RBTree < K,V, KeyOfValue,Compare>::Insert(const V& value)
{if (_root == nullptr){_root = new Node(value);_root->_color = RBTreeBlack;return { {_root,_root},true };}Node* parent = nullptr; Node* cur = _root;//二叉树规则插入KeyOfValue kov;Compare com;while (cur){ //	if (cur->_kv.first < kv.first) if(kov(value)==kov(cur->_value))return { {cur,_root},true };if( com( kov(cur->_value),kov(value) )  ){parent = cur;   cur = cur->_right; } //else if (cur->_kv.first > kv.first) else if ( com( kov(value), kov(cur->_value) ) ){parent = cur;    cur = cur->_left;}}cur = new Node(value);//判断新增节点使父节点左还是右//if (parent->_value.first < value.first)if(com(kov(parent->_value),kov(value)))parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent && parent->_color == RBTreeRed){Node* grandfather = parent->_parent;//  g//p   u//p为g的左代码实现if (parent == grandfather->_left){Node* uncle = grandfather->_right;//  u存在且为红,p和u变黑，g变红，改变cur和p的指向，继续向上变；if (uncle && uncle->_color == RBTreeRed){parent->_color = uncle->_color = RBTreeBlack;grandfather->_color = RBTreeRed;cur = grandfather;parent = grandfather->_parent;}// u不存在或存在且为黑else{//      g//    p    u//  c//单旋加变色，c为p的左,   p变成新的根，p变黑，g变红if (cur == parent->_left){RorateR(grandfather);parent->_color = RBTreeBlack;grandfather->_color = RBTreeRed;}//        g//    p         u//       c//双旋加变色，c为p的右，else{RorateLR(grandfather);cur->_color = RBTreeBlack;grandfather->_color = RBTreeRed;}}return { {cur,_root},true };}else{ //这里是p为g的情}return { {cur,_root},true };}return { {cur,_root},true };
}}

封装map

my_map
template<class K, class V>
class KOV_M
{
public:K operator()(const std::pair<K, V> data){return data.first;}
};template<class K, class V, class Compare = std::less<K>>
class map
{
public:typedef typename RBTree<K, std::pair<K, V>, KOV_M<K, V>>::Iterator iterator;typedef typename RBTree< K, std::pair<K, V>, KOV_M<K, V>>::ConstIterator   const_iterator;std::pair<iterator, bool> insert(const std::pair<K, V>& p)
{return _tree.Insert(p);
}
private:RBTree<K, std::pair<K, V>, KOV_M<K,V>> _tree;
};

封装set

template<class V>
class KOV_S
{
public:V  operator()(const V& data){return data;}
};
template< class V, class Compare =std:: less<V>>
class set
{
public:std::pair<iterator, bool>  insert(int value){return _tree.Insert(value);}
private:RBTree<V,V, KOV_S<V>> _tree;
};

2. 支持iterator的实现

参照源码，需要实现iterator的++和–等操作，

iterator实现思路分析

1. 整体思路和list的iterator类似，用类封装节点的指针，然后通过重载运算符，使迭代器实现像指针一样的行为
2. map和set的迭代器走的是中序遍历，这样才能有序，所以在++和–操作时就要遵循中序遍历的规则
3. 支持->等运算符是为了封装map时支持 [ ] 操作

【iterator++操作实现详解】

1. 如果cur的右子树不为空，根据二叉树的规则，它的右子树的最左节点就是他的下一个节点，

2. 如果cur的右子树为空，就代表以cur为根的树已经走完了，接下来就要分成两种情况来讨论
【1】cur为父节点的左节点，++操作就是走到cur的父节点

【2】cur为父节点的右节点，这种情况就是以cur的父节点为根的树走完了，需要一直向上更新，直到遇到一个节点是父节点左节点或者走到终点

这里关于end()的实现，源码中是设置了一个哨兵位头节点，它和根互为父节点，左指向最左，右指向最右，这里我用空节点实现的end(),可以实现和源码同样的功能，但在–end()时需要特殊处理一下，让迭代器指向最右节点,具体看–的代码实现

template<class V, class Ref, class Ptr>
class RBTreeIterator
{
public:typedef RBTreeNode<V> Node;//typedef RBTreeIterator<V, V&, V*> Iterator;//typedef RBTreeIterator<V, const V&, const  V*> ConstIterator;typedef RBTreeIterator<V, Ref, Ptr> Self;RBTreeIterator(){}RBTreeIterator(Node* node,Node* root) :_node(node), _root(root){}void increment(){if (_node->_right != nullptr){_node = _node->_right;while (_node->_left != nullptr)_node = _node->_left;}else{Node* p = _node->_parent;if (_node == p->_left)_node = p;else{while (p != nullptr && _node == p->_right){_node = p;p = p->_parent;}if (p == nullptr)_node = nullptr;}}}void decrement(){if (_node->_left != nullptr){_node = _node->_left;while (_node->_right != nullptr)_node = _node->_right;}else{Node* p = _node->_parent;while (p != nullptr && _node == p->_left){_node = p;p = p->_parent;}_node = p;}}Node* rightMost(){Node* RightMost = _root;while (RightMost != nullptr && RightMost->_right != nullptr)RightMost = RightMost->_right;return RightMost;}Self& operator++(){increment();return *this;}Self operator++(int){Self tmp = *this;increment();return tmp;}Self& operator--(){if (_node == nullptr)_node = rightMost();elsedecrement();return *this;}Self operator--(int){Self tmp = *this;if (_node == nullptr)_node = rightMost();elsedecrement();return tmp;}bool operator==(Self& y){return  _node == y._node;}bool operator!=(Self& y){return  _node != y._node;}Ref operator*(){return _node->_value;}Ptr operator->(){return &_node->_value;}
public:Node* _node;Node* _root;
};

3.支持map的[ ]操作

有了insert的实现，实现[]就很简单了，可以复用insert代码，而在这里先前iterator支持的->操作也派上用场了，用来返回pair的第二个参数，具体看代码

4.map和set代码实现

//map

namespace kzz
{template<class K, class V>class KOV_M{public:K operator()(const std::pair<K, V> data){return data.first;}};template<class K, class V, class Compare = std::less<K>>class map{public:typedef typename RBTree<K, std::pair<K, V>, KOV_M<K, V>>::Iterator iterator;typedef typename RBTree< K, std::pair<K, V>, KOV_M<K, V>>::ConstIterator   const_iterator;std::pair<iterator, bool> insert(const std::pair<K, V>& p){return _tree.Insert(p);}iterator begin(){return _tree.Begin();}iterator end(){return _tree.End();}const_iterator begin()const{return _tree.Begin();}const_iterator end()const{return _tree.End();}iterator find(K& key){_tree.Find(key);}V& operator[](const K& key){std::pair<iterator,bool> ret= _tree.Insert(   std::pair<K,V>(key,V())   );return ret.first->second;}private:RBTree<K, std::pair< K, V>, KOV_M<K,V>> _tree;};
}

//set

namespace kzz
{template<class V>class KOV_S{public:V  operator()(const V& data){return data;}};template< class V, class Compare =std:: less<V>>class set{public:typedef typename RBTree<V, const V, KOV_S<V>>::Iterator iterator;typedef typename RBTree<V, const V, KOV_S<V>>::ConstIterator   const_iterator;std::pair<iterator, bool>  insert(int value){return _tree.Insert(value);}iterator begin(){return _tree.Begin();}iterator end(){return _tree.End();}const_iterator begin()const{return _tree.Begin();}const_iterator end()const{return _tree.End();}iterator find(K& key){_tree.Find(key);}private:RBTree<V,const V, KOV_S<V>> _tree;};
}

//rb_tree

template <class K, class V,class KeyOfValue,class Compare=std::less<K>>
class RBTree
{
public:typedef RBTreeNode<V> Node;typedef RBTreeIterator<V, V&, V*> Iterator;typedef RBTreeIterator<V, const V&, const  V*> ConstIterator;std::pair<Iterator,bool> Insert(const V& value);Iterator End(){return Iterator(nullptr, _root);}Iterator Begin(){Node* leftMost = _root; while (leftMost && leftMost->_left) {leftMost = leftMost->_left; }return Iterator(leftMost, _root);}ConstIterator End()const{return ConstIterator(nullptr, _root);}ConstIterator Begin()const{Node* leftMost = _root;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return ConstIterator(leftMost, _root);}public:Iterator Find(K& key);Node*  _root=nullptr;void  RorateRL(Node* root);void  RorateLR(Node* root);void RorateR(Node* root);void RorateL(Node* root);bool IsBanlance(Node* root);bool check(Node* root,int count,const int blackNum);
};