【STL】用一棵红黑树同时封装set和map
红黑树源代码
下面我们将对一颗kv模型的红黑树进行封装并且模拟实现出stl库当中的map和set
以下是需要使用到的红黑树源代码：
enum colour {RED, BLACK};
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _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:RBTree():_root(nullptr){}bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//两个情况//1.uncle存在且为红//2.uncle不存在/为黑//如果parent不为空，且为红，则需要进行调整，为黑直接插入即可while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//这里不知道parent在grandfather的左边还是右边，所以需要判断一下if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){grandfather->_left->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (uncle == nullptr || uncle->_col == BLACK){//右旋if (parent->_left == cur){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = cur->_col = RED;}//左右双旋else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = parent->_col = RED;}}}}else // parent == grandfather->right{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){grandfather->_right->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (uncle == nullptr || uncle->_col == BLACK){//左旋if (parent->_right == cur){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = cur->_col = RED;}//右左双旋else {RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = parent->_col = RED;}}}}}_root->_col = BLACK;return true;}//左旋转void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppNode = parent->_parent;parent->_parent = cur;if (ppNode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppNode->_left == parent){//parent->_right = cur;ppNode->_left = cur;}else{//parent->_right = cur;ppNode->_right = cur;}cur->_parent = ppNode;}}//右旋转void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppNode = parent->_parent;parent->_parent = cur;if (ppNode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppNode->_left == parent){//这里写的parent导致无限套娃//parent->_right = cur;ppNode->_left = cur;}else{//parent->_right = cur;ppNode->_right = cur;}cur->_parent = ppNode;}}private:Node* _root;
};
红黑树模板参数的控制
我们知道set是一个k模型的容器，而map是一个kv模型的容器，那么我们如何使用一颗kv模型的黑红树来同时封装它们两个呢？
我们需要控制我们传进红黑树中的模板参数，来进行对set和map的兼容
为了和原红黑树的模板参数进行区分，这里我们将红黑树的第二个模板参数修改为T
template<class K, class T>
class RBTreeT可以是键值Key，也可以是键值对Key和Value，如果是set容器那么它传入底层红黑树的就是Key和Key
template<class K>
class set
{
public://...private:RBTree<K, K> _t;
};若该容器是map，那么它传入底层红黑树的就是Key和Value组成的键值对
template<class K, class V>
class map
{
public://...private:RBTree<K, pair<K, V>> _t;
};对于set来说它只需要使用Key就足够了，因为set传进的两个参数是相同的，只是为了与map同一棵树进行封装，不得不传入两个Key，但是对于map来说Key和Value是不可或缺的，例如，在进行find，erase等一系列操作时都需要使用键值Key来进行搜索
在红黑树中，由于上层容器set和map传入参数的不同红黑树中的模板参数T也会有变化
set容器：T是键值Key
map容器：T是由键值Key和实值Value组成的键值对
更改后的结点代码：
template<class T>
struct RBTreeNode
{//三叉链RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;colour _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};这里我们将结点类的参数也改为T，当容器是set，传入参数为Key，是map时传入的参数为Key，Value键值对
这里有一个问题，结点模板参数现在为T，我们在后续在二叉树中寻找Key时，我们不知道这颗树上层容器使用的是set还是map，那么我们该如何比较呢？
为了解决上述问题我们需要分别在set和map中单独创建一个仿函数，在进行比较时仿函数会先获取set和map的键值，然后通过键值进行比较
仿函数
就是使用方法和函数相似，实际上就是operaotr()，从而达到效果和使用方法上和函数相类似，这就是仿函数
map
template<class K, class V>
class map
{//仿函数struct MapKeyofT{const K& operator()(const pair<K, V>& key){return key.first;}};public://...
private:RBTree<K, pair<K, V>， MapKeyofT> _t;
}set
template<class K, class V>
class set
{//仿函数struct SetKeyofT{const K& operator()(const K& key){return key;}};public://...
private:RBTree<K, pair<K, V>， SetKeyofT> _t;
}
注意：所以需要使用Key值进行比较的地方，全部都需要使用仿函数套一层进行比较
正向迭代器的实现
正向迭代器的实现就是对红黑树的结点进行封装，在正向迭代器中只有一个成员变量，那就是正向迭代器所封装的指针
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node; //结点的类型typedef __RBTreeIterator<T, Ref, Ptr> 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;
}在实现红黑树迭代器时，最关键的就是++和--运算符的重载，也是实现红黑树迭代器最难的地方
前置++运算符重载
我们想要实现迭代器的++，遍历的顺序：左子树->根->右子树
有二种情况我们需要注意：
以下情况图我就不画NIL结点了
情况1：所给的结点在8这个位置，右子树不为空的情况
当结点的右子树不为空时，我们只需要找到它右子树的最小结点（右子树的最左边的那个结点）
即：8->10
情况二：
->1.当所给结点在5这个位置，右子树为空的情况
那我们将需要找到孩子是父亲左的那个祖先结点，这个结点可能是父亲也可能是祖先
例：我们对5这个结点进行++，下一个结点就是6，是5的父亲
->2.当所给结点在7这个位置
7的结点为空，我们需要找到孩子是父亲左的那个祖先结点，这时我们所找到的就是8
总结：
1.右子树不为空，找它右子树的最左结点（右子树的最大值）
2.右子树为空，需要找到孩子是父亲左的祖先结点
我们以下图这个情况为例：
孩子是父亲左的祖先结点，如何理解这句话？
我们将以6为根的子树看作一个整体，则it在8左边，8就是7在其左子树上的一个孩子结点，即我们所需要找到的结点就是8
如何去寻找parent这个位置，我们通过向上遍历不断更新cur和paernt，直到parent->left == cur停止，这时parent就是我们需要找到的结点
代码实现：
self& operator++()
{//若右子树为空if (_node->_right != nullptr){Node* subleft = _node->_right;while (subleft && subleft->_left){subleft = subleft->_left;}_node = subleft;}//若右子树不为空的情况else{Node* cur = _node;Node* parent = cur->_parent;//注意判断以下parent是否为空，这棵树可能是空树while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;
}前置--运算符重载
具体图就不画了，和前置++类似
还是两种情况：
1.左子树不为空，就去找左子树中的最小结点（左子树的最右边）
2.左子树为空，需要去找孩子是父亲右的祖先结点
代码实现：
self& operator--()
{if (_node->_right != nullptr){Node* subleft = _node->_left;while (subleft && subleft->_right){subleft = subleft->_right;}_node = subleft;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;
}创建完红黑树的迭代器之后
我们需要在红黑树的实现当中进行迭代器类型的typedef，为了能在类外部使用迭代器，typdef的行为需要设置为public
begin函数返回这棵树最左边的结点的正向迭代器
end函数返回最后一个结点下一个位置的正向迭代器，即：空指针
template<class K, class T, class KeyOfValue>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;typedef __RBTreeIterator<T, const T&, const T*> const_iterator;RBTree():_root(nullptr){}iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* cur = _root;while (cur && cur->left){cur = cur->_left;}return iterator(cur);}const_iterator end() const{return iterator(nullptr);}
};下面我们来看看C++STL库中的红黑树是怎么样实现的，实现逻辑是怎么样的
C++STL库中实现红黑树时，在红黑树的根节点增加了一个头结点，头结点的左指针指向这颗红黑树的最左结点，右指针指向这棵树的最右结点，父亲结点指向根结点
在这个结构下begin()，end()迭代器都很容易就能实现，但同样的增加了一个头结点header，细节控制会更加复杂，类似我们增加一个_parent指针一样，用的时候很舒服，但是在实现左右旋转的时候，我们还需要考虑它，对代码的整体控制节奏要求很高。例：我们在5的左边或15的右边插入结点时需要更新头结点左右指针的指向
反向迭代器的实现
反向迭代器，我们可以通过封装正向迭代器来实现
//使用正向迭代器封装反向迭代器
//反向迭代器就是一个容器适配器
template<class iterator, class Ref, class Ptr>
struct Reserve_iterator
{ typedef Reserve_iterator<iterator, Ref, Ptr> self;iterator _it;Reserve_iterator(iterator it) //这里是浅拷贝，但是足够了:_it(it){}//复用正向迭代器的解引用Ref operator*(){iterator tmp = _it; return *tmp;}//复用正向迭代器的指向运算符Ptr operator->(){return &(opeartor*());}//复用正向迭代器的前置--self& operator++(){--_it;return *this;}//复用正向迭代器的前置++self& operator--(){ ++_it;return *this;}//复用正向迭代器的==bool operator==(const self& s){return _it == s;}//复用正向迭代器的!=bool operator!=(const self& s){return _it != s;}
};对部分代码解读：
//复用正向迭代器的前置--self& operator++(){--_it;return *this;}//复用正向迭代器的前置++self& operator--(){ ++_it;return *this;}
现在ret2是一个反向迭代器类型的，它的++就是正向迭代器的--，反之就是正向迭代器的++
以上步骤写完之后我们就可以来模拟实现map‘和set
set的模拟实现
#include "RBTree.h"namespace zyx1
{template<class K>class Set{struct SetKeyofvalue{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyofvalue>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyofvalue>::const_iterator const_iterator;typedef typename RBTree<K, K, SetKeyofvalue>::reverse_iterator reverse_iterator;typedef typename RBTree<K, K, SetKeyofvalue>::const_reverse_iterator const_reverse_iterator;//迭代器const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}reverse_iterator rbegin() {return _t.rbegin();}reverse_iterator rend(){return _t.rend();}//pair类模板中的iterator是const类型的，我们复用的红黑树中的insert接口，它返回的pair类模板中的iterator是不同迭代器//所以我们这里需要处理一下//insert的返回值使用pair<typename RBTree<K, T, KeyOfValue>::iterator, bool> ret接收，现在ret接就是普通迭代器//然后利用pair的构造函数将这个普通迭代器转换为const迭代器pair<iterator, bool> insert(const K& key){//_t.insert(key);pair<typename RBTree<K, K, SetKeyofvalue>::iterator, bool> ret = _t.insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetKeyofvalue> _t;};
}方法一：
pair类模板中的iterator是const类型的，我们复用的红黑树中的insert接口，它返回的pair类模板中的iterator是不同迭代器，所以我们这里需要处理一下，insert的返回值使用pair<typename RBTree<K, T, KeyOfValue>::iterator, bool> ret接收，现在ret接就是普通迭代器，然后利用pair的构造函数将这个普通迭代器转换为const迭代器
pair<iterator, bool> insert(const K& key){//_t.insert(key);pair<typename RBTree<K, K, SetKeyofvalue>::iterator, bool> ret = _t.insert(key);return pair<iterator, bool>(ret.first, ret.second);}
如果传入的是普通迭代器，这里就是一个拷贝构造函数，拷贝构造出一个const迭代器
如果传入的是const迭代器，这里就是一个构造函数，这里我没有写typedef的const_iterator，大家有兴趣可以试试
注意：这里我们使用的是struct默认public权限，如果我们使用的是class，_node成员变量权限需要设置为public，我们知道使用不同类型通过模板实例化出的类是不同的，所以terator和template<class T, class Ref, class Ptr>实例化的类型可能不一样，_node如果是私有类型，会导致报错
方法二：
通过以上分析，以下也是相同原理
pair<iterator, bool> insert(const K& key)
{return _t.insert(key);/*pair<typename RBTree<K, K, SetKeyofvalue>::iterator, bool> ret = _t.insert(key);return pair<iterator, bool>(ret.first, ret.second);*/
}map的模拟实现
namespace zyx2
{template <class K, class V>class Map{struct MapKeyofvalue{const K& operator()(const pair<K, V>& key){return key.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyofvalue>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyofvalue>::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();}V& operator[](const K& key){//return ((*((_t.insert(make_pair(key, V()))).first)).second);pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& key){return _t.insert(key);}void print(){_t.InOrder();}private:RBTree<K, pair<const K, V>, MapKeyofvalue> _t;};
反向迭代器
//使用正向迭代器封装反向迭代器
//反向迭代器就是一个容器适配器
template<class Iterator>
struct Reserve_iterator
{ typedef Reserve_iterator<Iterator> self;typedef typename Iterator::refrence Ref;typedef typename Iterator::pointer Ptr;Iterator _it;Reserve_iterator(Iterator it) //这里是浅拷贝，但是足够了:_it(it){}//复用正向迭代器的解引用Ref operator*(){//_it的本质是正向迭代器，然后调用正向迭代器里面--,如果让_it--,会破坏正向迭代器在外部的使用（调用反向迭代器，正向迭代器会减减）//所以需要一个中间变量Iterator tmp = _it; return *tmp;}//复用正向迭代器的指向运算符Ptr operator->(){return &(operator*());}//复用正向迭代器的前置--self& operator++(){--_it;return *this;}//复用正向迭代器的前置++self& operator--(){ ++_it;return *this;}//复用正向迭代器的==bool operator==(const self& s){return _it == s;}//复用正向迭代器的!=bool operator!=(const self& s){return _it != s;}
};RBTree
#include "Reverse_iterator.h"enum colour {RED, BLACK};
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;colour _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};//红黑树迭代器
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, T&, T*> iterator;typedef __RBTreeIterator<T, Ref, Ptr> self;typedef Ref refrence;typedef Ptr pointer;Node* _node;__RBTreeIterator(const iterator& it):_node(it._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 && subleft->_left){subleft = subleft->_left;}_node = subleft;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur != parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this; }self& operator--(){if (_node && _node->_right){Node* subleft = _node->_left;while (subleft && subleft->_right){subleft = subleft->_right;}_node = subleft;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur != parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}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 KeyOfValue>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;typedef __RBTreeIterator<T, const T&, const T*> const_iterator;typedef Reserve_iterator<iterator> reverse_iterator;typedef Reserve_iterator<const_iterator> const_reverse_iterator;RBTree():_root(nullptr){}//迭代器iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* cur = _root;while (cur && cur->left){cur = cur->_left;}return iterator(cur);}const_iterator end() const{return iterator(nullptr);}reverse_iterator rbegin() {Node* cur = _root;while (cur && cur->_right){cur = cur->_right;}return iterator(cur);//return end();}reverse_iterator rend(){return begin();}const_reverse_iterator rbegin() const{return end();}const_reverse_iterator rend() const{return begin();}//插入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;while (cur){if (kov(cur->_data) > kov(data)){parent = cur;cur = cur->_left;}else if (kov(cur->_data) < kov(data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);if (kov(parent->_data) > kov(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//两个情况//1.uncle存在且为红//2.uncle不存在/为黑//如果parent不为空，且为红，则需要进行调整，为黑直接插入即可Node* newnode = cur;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//这里不知道parent在grandfather的左边还是右边，所以需要判断一下if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){grandfather->_left->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (uncle == nullptr || uncle->_col == BLACK){//右旋if (parent->_left == cur){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = cur->_col = RED;}//左右双旋else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = parent->_col = RED;}}}}else // parent == grandfather->right{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){grandfather->_right->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (uncle == nullptr || uncle->_col == BLACK){//左旋if (parent->_right == cur){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = cur->_col = RED;}//右左双旋else {RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = parent->_col = RED;}}}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}//左旋转void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppNode = parent->_parent;parent->_parent = cur;if (ppNode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppNode->_left == parent){//parent->_right = cur;ppNode->_left = cur;}else{//parent->_right = cur;ppNode->_right = cur;}cur->_parent = ppNode;}}//右旋转void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppNode = parent->_parent;parent->_parent = cur;if (ppNode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppNode->_left == parent){//这里写的parent导致无限套娃//parent->_right = cur;ppNode->_left = cur;}else{//parent->_right = cur;ppNode->_right = cur;}cur->_parent = ppNode;}}private:KeyOfValue kov;Node* _root;
};