控制底层红黑树模板参数

如果我们用一棵KV模型的红黑树同时实现map和set,我们就需要控制map和set中的所传入红黑树中的模板参数,其中,封装过程中,为了与红黑树的模板参数区分,我们将红黑树中模板参数由V改成T.

template <class K, class T>
struct RBTree
{// 
};

对于T来说,如果是set容器,那么T实例化出来的便是Key

namespace mySet
{template<class K>class set{public://private:RBTree<K, K>> _t;};}

如果是map容器,那么T实例化出来的便是pair<K,V>键值对.

namespace myMap
{template<class K,class V>class map{public://private:RBTree<K, pair<K, V>> _t;};
}

T实例化例图如下:

那么,在红黑树中我们可不可以只保留一个模板参数T,根据实参类型转换为所需要的存储类型呢?

不可以,之所以还需要第一个模板参数K,就是因为STL中map所提供的find和erase接口需要key来指定删除或者查找的结点.

模板参数中的仿函数

在插入中,结点中存储的类型T可能为Set容器中的key,也有可能是Map中的pair<K,V>键值对,底层红黑树如何针对不同类型的容器进行比较呢?

我们所需要的是:
如果是set容器,那么T就是类型key,我们需要取数据类型为T的data就行.

如果是map容器,那么T就为键值对pair<K,V>,我们需要取键值对pair中的first与所给值key比较.

所以,综合以上情况,我们需要在上层set,map中添加一个仿函数,根据实参所传的不同类型进而获取不同数据类型来比较两个结点.

例如:
以下为set,map容器分别传入一个仿函数,在比较时会更具容器类型不同进而调用所需要的仿函数.
set仿函数:

namespace mySet
{template<class K>class set{public:struct SetKeyOfT{const K& operator()(const K& key ){return key;}};private:RBTree<K, K, SetKeyOfT> _t;};}

map仿函数:

namespace myMap
{template<class K,class V>class map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};private:RBTree<K, pair<K, V>,MapKeyOfT> _t;};}

所以,当容器为set时,红黑树中的仿函数就实例化为set容器中的仿函数,当容器为map时,红黑树中的仿函数就实例化为map中的仿函数.

进而,当我们通过上层容器中的Insert函数调用底层红黑树中的Insert函数时,在比较时就会根据存储类型T,分别调用所需要的仿函数进行结点的比较.
例如:
以下是底层红黑树Insert函数仿函数调用插入新结点部分代码:

bool Insert(const T& data )            //插入函数{KeyOfT kot;if (_root == nullptr) //如果为空树,直接插入结点就可以了.{_root = new Node(data);cout << kot(_root->_data);return true;}Node* parent = nullptr;Node* cur = _root;while (cur)                          //寻找插入位置{if (kot(data) <  kot(cur->_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);               //找到插入位置并插入.//......}

map,set中的正向迭代器

map和set中的迭代器实际上就是对指向结点的指针进行封装,正向迭代器中一个内置成员.

其中Ref,Ptr分别代表目标数据类型的引用,指针类型.

template <class T,class Ref,class Ptr>
struct _RBTreeIterator
{typedef RBTreeNode<T> Node;       //重新定义红黑树结点类型为Nodetypedef _RBTreeIterator<T, Ref, Ptr> Self; //重新定义迭代器类型为SelfNode* _node;
}

正向迭代器的构造:

_RBTreeIterator(Node* node = nullptr):_node(node){}

正向迭代器的解引用运算符重载:
当我们使用正向迭代器的解引用运算符重载时,直接返回目标数据的引用.

    Ref operator*(){return _node->_data;}

正向迭代器的->运算符重载
当我们使用正向迭代器的->运算符重载,直接返回目标数据的地址.

Ptr operator->(){return &_node->_data;}

正向迭代器还包括了==,!=运算符重载,我们直接判断两个迭代器中的结点指针是否相同即可.

bool operator!=(const Self& s) const //普通对象和const对象都可以进行调用.{return _node != s._node;}bool operator==(const Self& s) const {return _node == s._node;}

前置++运算符重载:
前置++运算重载是按照中序遍历进行访问的,主要有两个步骤
1: 如果it所指的结点中右子树存在,则访问右子树的最左结点.

2: 如果it所指的结点中右子树不存在,则寻找孩子不是父亲右的那个祖先,并对其进行访问.

代码如下:

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: 如果it所指的结点中左子树存在,则访问左子树的最右结点.

2: 如果it所指的结点中左子树不存在,则寻找孩子不是父亲左的那个祖先,并对其进行访问.

当正向迭代器实现后,我们可以在上层对该迭代器进一步封装.可以在底层红黑树的public区域中重新定义迭代器的类型为iterator,并且封装两个函数:
1: begin函数中迭代器指向底层红黑树的最左结点.

2: end函数中原本返回的是最后一个数据的下一个地址,如果有哨兵位则返回哨兵位,为了方便,我们采用的是返回nullptr构造的迭代器.(但是这样在it从end–遍历时会访问空指针造成程序崩溃Bug)

begin函数和end函数代码如下:

	iterator begin()          //指向的是底层红黑树的最左结点.{Node* left = _root;while ( left && left->_left ) //不能是的空树.{left = left->_left;}return iterator(left);      //构造一个迭代器返回.}iterator end()            //返回的是最后一个数据的下一个地址,如果有//哨兵位就返回哨兵位,如果没有哨兵位就返回空的迭代器.{return iterator(nullptr);}

map,set中的反向迭代器

map,set中的反向迭代器底层就是对正向迭代器的封装,反向迭代器实际上是一个迭代器适配器

template<class Iterator,class Ref,class Ptr>
struct ReverseIterator                  //反向迭代器
{typedef ReverseIterator<Iterator,Ref,Ptr> Self; //重新定义反向迭代器的类型Iterator _it;                     //反向迭代器的内置成员就是正向迭代器ReverseIterator(Iterator it)       //初始化列表:_it(it)                     //正向迭代器构造一个反向迭代器{}Ref operator*(){return *_it; //调用正向迭代器的operator*返回结点数据的引用}Ptr operator->(){return _it.operator->(); //调用正向迭代器的operator->返回结点数据的指针}Self& operator++()	          //前置++{--_it; //调用正向迭代器的前置--return *this;}//前置--Self& operator--(){++_it; //调用正向迭代器的前置++return *this;}bool operator!=(const Self& s) const{return _it != s._it; //调用正向迭代器的operator!=}bool operator==(const Self& s) const{return _it == s._it; //调用正向迭代器的operator==}
};

当反向迭代器实现后,我们可以在底层红黑树中的public区域重新定义一个反向迭代器的类型Riterator并且封装两个函数:
1: rbegin函数返回底层红黑树的最右结点.

2: rend函数中如果有哨兵位则返回哨兵位,为了方便,我们采用的是返回nullptr构造的迭代器.(但是这样在it从rend++遍历时会造成访问空指针造成程序崩溃Bug)

Riterator rbegin()          //指向的是底层红黑树的最右结点.{Node* right = _root;while ( right  && right->_right) //不能是的空树.{right = right->_right;}return Riterator(iterator(right));      //构造一个迭代器返回.}Riterator  rend(){return Riterator( iterator(nullptr));}

[]下标访问运算符重载

[]下标访问运算符主要复用插入函数:
1: 当插入成功,返回的是刚插入结点的迭代器和返回结果为true所构成的pair键值对.

2: 当插入失败,说明已经有存有目标数据的结点,我们只要返回目标结点和返回结果false所组成的pair键值对.

3:KV模型结构才能重载[]下标访问运算符,底层红黑树不知道上层容器所传的模型结构类型,所以只能在上层容器中写.

例如:以下为在map中的[]下标访问运算符重载代码:

//因为只有K,V形式才有[],所以不能在底层红黑树写[],只能在上层容器map中写.V& operator[](const K& key){pair<iterator, bool> ret = Insert(make_pair(key, V()));           //如果插入的是未有数据,返回的是存有刚插入结点迭代器的pair,V()一般采用默认值.return ret.first->second;  //不管插入成没成功没,返回的都是指向那个存有目标数据结点迭代器的pair.}

map的模拟实现代码

#include "RBTree.h"
#include <iostream>
#include "Map.h"
using namespace std;
namespace myMap
{template<class K, class V>class map{public:struct MapKeyOfT         //仿函数{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;         //从类模板中取定义的类型,因为类模板的静态变量也是这样获取的,为了告诉编译器我所取的是,是定义的类型而不是静态变量,所以要加上typename加以区分.typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::Riterator Riterator;pair<iterator, bool> Insert(const pair<K, V>& kv){return _t.Insert(kv);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}Riterator rbegin(){return _t.rbegin();}Riterator rend(){return _t.rend();}V& operator[](const K& key){pair<iterator, bool> ret = Insert(make_pair(key, V()));return ret.first->second;  //不管插入成没成功没,返回的都是指向}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};}

map的模拟实现

#include "RBTree.h"
namespace mySet
{template<class K>class set{public:struct SetKeyOfT{const K& operator()(const K& key ){return key;}};typedef typename RBTree<K, K,SetKeyOfT>::iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::Riterator Riterator;pair<iterator, bool> Insert(const K& key){return _t.Insert(key);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}Riterator rbegin(){return _t.rbegin();}Riterator rend(){return _t.rend();}private:RBTree<K, K, SetKeyOfT> _t;};}

适用map,set容器的底层红黑树代码(修改版本)

#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;//pair<K, V> _kv;         //存储的键值对T _data;                //map就实例化为pair,set就实例化为key.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, Ref, Ptr> Self;Node* _node;//初始化列表_RBTreeIterator(Node* node = nullptr):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s) const //普通对象和const对象都可以进行调用.{return _node != s._node;}bool operator==(const Self& s) const {return _node == s._node;}Self& operator++() //前置++,返回的是自己.{Node* flag = nullptr;if (_node->_right) //右子树存在,访问的是右子树的最左节点.{Node* left = _node->_right;while ( left->_left){left = left->_left;}_node = left;flag = _node;}else if (_node == nullptr){_node = flag;}else     //右子树不存在,寻找孩子不是父亲右的那个祖先.{Node* parent = _node->_parent;Node* cur = _node;while ( parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;  //返回迭代器.}Self& operator--(){ Node* flag = nullptr;if (_node->_left) //左子树存在,访问左子树中的最右那个结点.{Node* right = _node->_left;while (right && right->_right ){right = right->_right;}_node = right;}else if( _node == nullptr ){_node = flag;}else             //左子树不存在,寻找孩子不是父亲左的那个祖先.{Node* parent = _node->_parent;Node* cur = _node;while ( parent && cur == parent->_left ){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};//反向迭代器---迭代器适配器
template<class Iterator,class Ref,class Ptr>
struct ReverseIterator
{typedef ReverseIterator<Iterator,Ref,Ptr> Self; //反向迭代器的类型Iterator _it; //反向迭代器所封装的正向迭代器//构造函数ReverseIterator(Iterator it = nullptr):_it(it) //根据所给正向迭代器构造一个反向迭代器{}Ref operator*(){return *_it; //通过调用正向迭代器的operator*返回结点数据的引用}Ptr operator->(){return _it.operator->(); //通过调用正向迭代器的operator->返回结点数据的指针}//前置++Self& operator++(){--_it; //调用正向迭代器的前置--return *this;}//前置--Self& operator--(){++_it; //调用正向迭代器的前置++return *this;}bool operator!=(const Self& s) const{return _it != s._it; //调用正向迭代器的operator!=}bool operator==(const Self& s) const{return _it == s._it; //调用正向迭代器的operator==}
};template <class K, class T,class KeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node;typedef  _RBTreeIterator<T, T&, T*> iterator;typedef ReverseIterator< iterator, T&, T* > Riterator;
public:iterator begin()          //指向的是底层红黑树的最左结点.{Node* left = _root;while ( left && left->_left ) //不能是的空树.{left = left->_left;}return iterator(left);      //构造一个迭代器返回.}iterator end()            //返回的是最后一个数据的下一个地址,如果有//哨兵位就返回哨兵位,如果没有哨兵位就返回空的迭代器.{return iterator(nullptr);}Riterator rbegin()          //指向的是底层红黑树的最右结点.{Node* right = _root;while ( right  && right->_right) //不能是的空树.{right = right->_right;}return Riterator(iterator(right));      //构造一个迭代器返回.}Riterator  rend(){return Riterator( iterator(nullptr));}Node* Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key) //如果key大于当前结点的first{cur = cur->_right;}else if (kot(cur->_data) > key) //如果key小于当前结点的first{cur = cur->_left;}else           //寻找到了{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);}pair<iterator,bool>  Insert(const T& data )            //插入函数{KeyOfT kot;if (_root == nullptr) //如果为空树,直接插入结点就可以了.{_root = new Node(data);//	cout << kot(_root->_data);_root->_col = BLACK;return make_pair(iterator(_root), true); //返回的是杠插入结点的迭代器和返回结果所构成的pair}Node* parent = nullptr;Node* cur = _root;while (cur)                          //寻找插入位置{if (kot(data) >  kot(cur->_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);//返回的是已经有数据的迭代器和返回结果所构成的pair.}}cur = new Node(data);               //找到插入位置并插入.Node* newnode = cur;               //要保留新插入的结点,因为有可能情况一调整平衡时,cur指向的结点//已经改变.//cout << kot(cur->_data);cur->_col = RED;     //新插入结点的颜色为红色.if (kot(parent->_data) < kot(data))  //与父亲结点建立联系{parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED) //达到平衡条件,需要调整平衡.{Node* grandfater = parent->_parent;assert(grandfater);assert(grandfater->_col == BLACK);if (parent == grandfater->_left) //判断父亲在祖父的位置,如果父亲在祖父的左边{Node* uncle = grandfater->_right;if (uncle && uncle->_col == RED) //将父亲和叔叔的颜色变黑,祖父的颜色变红.{parent->_col = uncle->_col = BLACK;grandfater->_col = RED;cur = grandfater;             //继续向上寻找parent = cur->_parent;}else           //uncle不存在或者存在且为黑{//     g //  p//curif (cur == parent->_left)   //如果祖父,父亲,孩子路径为一条直线{RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}//    g// p//    curelse                       //如果祖父,父亲,孩子路径为一条折线.{RotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}//走到这里大该子树的根已经变成黑色结点了,不用再往上循环了.break;}}else                    //如果父亲在祖父的右边.{//   g// u   p //       c//Node* uncle = grandfater->_left;if (uncle && uncle->_col == RED)    //如果叔叔存在且为红色结点.{parent->_col = uncle->_col = BLACK;grandfater->_col = RED;cur = grandfater;      //继续向上变色循环.parent = cur->_parent;}else                    //如果父亲不存在,或者存在且为黑色结点.{//    g //      p//        c 		if (parent->_right == cur)      //如果父亲,祖父,孩子路径为一条直线{RotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}//    g//      p//    celse                          //如果父亲,祖父,孩子路径为一条折线{RotateR(parent);RotateL(grandfater);grandfater->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK; //走到这说明这棵树没有的祖先没有parent,或者有parent但是父亲是黑色的,不需要处理.return make_pair(iterator(newnode), true);}bool IsBalance(){return _IsBalance(_root);}
private:bool PreCheck(Node* root, int& benchMark, int blackNum) //判断性质四{if (root == nullptr){if (benchMark == 0){benchMark = blackNum;;return true;}if (blackNum != benchMark){cout << "某条黑色结点数量不相等." << endl;return false;}else{return true;}}if (root->_col == RED && root->_parent->_col == RED)//判断性质三{return false;}if (root->_col == BLACK){++blackNum;}return PreCheck(root->_left, benchMark, blackNum) &&PreCheck(root->_right, benchMark, blackNum);}bool _IsBalance(Node* root) //要从红黑树的四个性质分别判断{if (root == nullptr){return true;}if (root->_col == RED)       //判断性质一{cout << "根节点不是黑色结点" << endl;return false;}int benchMark = 0;         //黑色结点数量基准值.return PreCheck(root, benchMark, 0);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateL(Node* parent)         //左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_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;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}Node* _root = nullptr;};