公司网站建设的方案,电商付费推广方式,中职教材 网站建设,宜兴做网站哪家好目录 一、正向迭代器1.1 operator1.2 operator--1.3 参考代码 二、反向迭代器三、封装set四、封装map五、底层红黑树的实现 一、正向迭代器
我们之前vector#xff0c;list这些都是容器的迭代器都是简单的指针或者_node_node-next这样的#xff0c;那是因为它们要么是连… 目录 一、正向迭代器1.1 operator1.2 operator--1.3 参考代码 二、反向迭代器三、封装set四、封装map五、底层红黑树的实现 一、正向迭代器
我们之前vectorlist这些都是容器的迭代器都是简单的指针或者_node_node-next这样的那是因为它们要么是连续的空间要么是一个节点中存放着下一个节点的地址但是我们这里的红黑树的迭代器就没有那么简单了因为这里的红黑树的各个节点既不是连续的内存也没有在节点内存放着下一个节点的地址所以红黑树的迭代器的和–操作该如何完成呢
1.1 operator 1.2 operator– 1.3 参考代码 enum Colour{RED,BLACK};//当RBTree封装set的时候T是K类型//当RBTree封装map的时候T是pairK,V类型//这样设计RBTreeNode就可以让T接受什么类型//就是什么类型符合泛型编程template class Tstruct RBTreeNode{public://红黑树存放的值T _data;//节点的三叉链指针RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;//节点的颜色Colour _col;//构造函数RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};template class T,class Ref,class Ptrstruct __RBTree_iterator{//由于这里的iterator的传的参数是TTT*跟Self是不一样的// 所以无论如何这里的iterator就是普通迭代器typedef __RBTree_iteratorT, T, T* iterator;typedef __RBTree_iteratorT, Ref, Ptr Self;typedef RBTreeNodeT Node;public://构造函数__RBTree_iterator(Node* node):_node(node){}//当我们是实例化出const迭代器的时候这里是一个构造函数是利用普通迭代器构造一个const迭代器的构造函数//当我们是实例化出一个普通迭代器的时候这里是一个拷贝构造函数即利用普通迭代器拷贝构造出一个普通迭代器//这个函数必须提供因为后面封装set必须要用到这个否则会报错__RBTree_iterator(const iterator it):_node(it._node){}public:Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){//找下一个节点Node* subR _node-_right;//如果右子树不为空那么下一个节点就是右子树的最左节点if (subR ! nullptr){Node* leftmost subR;while (leftmost-_left){leftmost leftmost-_left;}//最后把_node更新成右子树的最左节点_node leftmost;}else{//如果右子树为空说明我的左子树访问完了我也访问完了那么下一个是访问我的父节点吗//其实不是的如果我是父亲的右孩子节点那么我访问完了但是因为我是父亲的右孩子节点//所以我访问完了并且我的父亲也访问完了所以这时的下一个需要访问的节点并不是我的//父节点而是要沿祖先路径查找我是父亲的左孩子的那个父亲这个父节点才是我们下一个//需要访问的节点因为我是父亲的左孩子那么我访问完了下一个就是访问我的父节点了Node* cur _node;Node* parent _node-_parent;while (parent){if (cur parent-_left){break;}else{//找我是父亲左孩子的那个父亲cur parent;parent parent-_parent;}}//这个父节点就是我们下一个需要访问的节点如果parent是nullptr那么//说明找到根节点都没有找到我是父亲左孩子的那个父亲说明这棵树已经访问//完了我们是用nullptr作为迭代器的end的_node parent;}return *this;}//找上一个节点Self operator--(){Node* subL _node-_left;//如果左子树存在那么当前节点的上一个节点就是左子树的最右节点if (subL ! nullptr){/*找左子树的左右节点*/Node* rightmost subL;while (rightmost-_right){rightmost rightmost-_right;}_node rightmost;}//如果左子树为nullptr那么沿祖先路径查找我是父亲的右孩子的那个父亲//因为我是父亲的右孩子那么我的前一个节点就是这个父亲else{Node* cur _node;Node* parent _node-_parent;while (parent){if (cur parent-_right){break;}else{cur parent;parent parent-_parent;}}_node parent;}return *this;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}public:Node* _node;};二、反向迭代器 //反向迭代器是使用了适配器模式利用已有的正向迭代器适配出来的//传参时传的是正向迭代器Itreator然后利用正向迭代器的接口封装//出反向迭代器的接口template class Iterator,class Ref,class Ptrstruct __RBTree_reverse_iterator{typedef __RBTree_reverse_iteratorIterator, Ref, Ptr Self;public://构造函数利用正向迭代器构造出一个反向迭代器__RBTree_reverse_iterator(const Iterator it):_it(it){}//通过运算符重载得到我们想要的效果因为反向迭代器的就是正向迭代器的--//所以直接调用正向迭代器的--接口即可完成反向迭代器的操作Self operator(){--_it;return *this;}//同理反向迭代器的--就是正向迭代器的所以直接调用正向迭代器的即可Self operator--(){_it;return *this;}bool operator!(const Self it){return _it ! it._it;}Ref operator*(){return *_it;}Ptr operator-(){return (operator*());}private:Iterator _it;};三、封装set #pragma once#include RBTree.hnamespace kb
{template class Kclass MySet{//仿函数用于取出红黑树的节点的key值方便在插入节点的时候作大小比较//如果是set的话取出来的就是key本身struct SetKeyOfT{const K operator()(const K key){return key;}};//对于set来说set的模型和map的模型是一样的都是key-value模型set的key-value//对应的是key-keymap的key-value对应的是key-pairK,V//对于set我们知道无论是set的key还是set的value都是不允许修改的所以要把通过迭代器//修改的行为直接禁掉所以对于set来说无论是iterator还是const_iterator的底层都是// 用红黑树中的const_iterator所以我们在使用set的iterator的时候看似使用的是普通//迭代器实际上底层也是const迭代器这样做就能从根本上杜绝通过普通迭代器修改set的key//或者value的行为了这个库里面的实现方式这个做法是真的绝typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;//反向迭代器也是按照正向迭代器那样设计来达到不让别人通过普通迭代器修改set的key或者value值的typedef typename RBTreeK, K, SetKeyOfT::const_reverse_iterator reverse_iterator;typedef typename RBTreeK, K, SetKeyOfT::const_reverse_iterator const_reverse_iterator;public:iterator begin(){return _set.begin();}iterator end(){return _set.end();}const_iterator cbegin()const{return _set.begin();}const_iterator cend()const{return _set.end();}reverse_iterator rbegin(){return _set.rbegin();}reverse_iterator rbegin() const{return _set.rbegin();}reverse_iterator rend(){return _set.rend();}reverse_iterator rend() const{return _set.rend();}//这个返回值的pair中的iterator是27行typedef出来的iterator所以这个iterator看起来是//普通迭代器实际上是const迭代器pairiterator,bool insert(const K x){//重点理解//调用Insert函数返回的pair中的first是普通迭代器而这里的作为返回值的pair中的// iterator实际上是const_iterator所以无法从普通的迭代器直接转化成const_iterator// 所以需要先用一个临时的pair接受Insert的返回值这个临时的pair的第一个参数必须要显式// 地指明是红黑树中的普通迭代器然后再利用临时的pair中的第一个参数的这个普通迭代器构造// 一个const迭代器注意需要在iterator中提供一个构造const迭代器的构造函数否则会报错pairtypename RBTreeK, K, SetKeyOfT::iterator,bool ret _set.Insert(x);return pairiterator, bool(ret.first, ret.second);//也可以像这样子写因为我们已经提供了一个用普通迭代器构造const迭代器的构造函数但是// //不建议这样子写因为这样子写我们对这个需要注意的细节就隐藏了降低了可读性//return _set.Insert(x);}void clear(){_set.clear();}private://对于setkey和value都是K类型并且需要把比较的仿函数也作为模板参数传过去RBTreeK, K, SetKeyOfT _set;};
}
四、封装map
#pragma once#include RBTree.hnamespace kb
{template class K,class Vclass MyMap{//仿函数用于取出红黑树的节点的key值方便在插入节点的时候作大小比较//如果是map的话取出来的就是pair中的key值struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};//对于map因为map的key值是不能被修改的但是它的value值是允许被修改的所以这里的//迭代器就不能像set那里的迭代器那样设计了因为如果像那样设计的话无论是key还是value//都没办法进行修改了那需要怎么控制住key不能被修改而value要能被修改呢库里面的操作//也很牛啊它是直接在传pair的key时直接传一个const K构造pair而V是普通的类型这样设计//就能使pair中的key不能被修改而value能被修改。//const迭代器就是pair的K和V都传const这样pair的K,V也就都不能被修改了typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, pairconst K, const V, MapKeyOfT::const_iterator const_iterator;//反向迭代器也是同样的设计typedef typename RBTreeK, pairconst K, V, MapKeyOfT::reverse_iterator reverse_iterator;typedef typename RBTreeK, pairconst K, const V, MapKeyOfT::const_reverse_iterator const_reverse_iterator;public://这里的插入函数的返回值的pair中的iterator和Insert的返回值的pair的iterator//都是相同的类型都是普通迭代器不存在类型转换所以就无需像set中的insert那样设计pairiterator,bool insert(const pairK, V x){return _map.Insert(x);}//[]的运算符的重载就是利用insert的返回值实现的V operator[](const K key){pairiterator, bool ret _map.Insert(make_pair(key, V()));return ret.first-second;}void clear(){_map.clear();}//封装迭代器iterator begin(){return _map.begin();}iterator end(){return _map.end();}const_iterator begin() const{return _map.begin();}const_iterator end() const{return _map.end();}const_reverse_iterator rbegin() const{return _map.end();}const_reverse_iterator rend() const{return _map.begin();}private://直接从这里传参实例化这棵树的时候把pair的K设置为const这样//对于map的key就不能被修改了而value依然能够被修改RBTreeK, pairconst K,V, MapKeyOfT _map;};
}
五、底层红黑树的实现
#pragma once#include iostream
using namespace std;
#include assert.hnamespace kb
{enum Colour{RED,BLACK};//当RBTree封装set的时候T是K类型//当RBTree封装map的时候T是pairK,V类型//这样设计RBTreeNode就可以让T接受什么类型//就是什么类型符合泛型编程template class Tstruct RBTreeNode{public://红黑树存放的值T _data;//节点的三叉链指针RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;//节点的颜色Colour _col;//构造函数RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};template class T,class Ref,class Ptrstruct __RBTree_iterator{//由于这里的iterator的传的参数是TTT*跟Self是不一样的// 所以无论如何这里的iterator就是普通迭代器typedef __RBTree_iteratorT, T, T* iterator;typedef __RBTree_iteratorT, Ref, Ptr Self;typedef RBTreeNodeT Node;public://构造函数__RBTree_iterator(Node* node):_node(node){}//当我们是实例化出const迭代器的时候这里是一个构造函数是利用普通迭代器构造一个const迭代器的构造函数//当我们是实例化出一个普通迭代器的时候这里是一个拷贝构造函数即利用普通迭代器拷贝构造出一个普通迭代器//这个函数必须提供因为后面封装set必须要用到这个否则会报错__RBTree_iterator(const iterator it):_node(it._node){}public:Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){//找下一个节点Node* subR _node-_right;//如果右子树不为空那么下一个节点就是右子树的最左节点if (subR ! nullptr){Node* leftmost subR;while (leftmost-_left){leftmost leftmost-_left;}//最后把_node更新成右子树的最左节点_node leftmost;}else{//如果右子树为空说明我的左子树访问完了我也访问完了那么下一个是访问我的父节点吗//其实不是的如果我是父亲的右孩子节点那么我访问完了但是因为我是父亲的右孩子节点//所以我访问完了并且我的父亲也访问完了所以这时的下一个需要访问的节点并不是我的//父节点而是要沿祖先路径查找我是父亲的左孩子的那个父亲这个父节点才是我们下一个//需要访问的节点因为我是父亲的左孩子那么我访问完了下一个就是访问我的父节点了Node* cur _node;Node* parent _node-_parent;while (parent){if (cur parent-_left){break;}else{//找我是父亲左孩子的那个父亲cur parent;parent parent-_parent;}}//这个父节点就是我们下一个需要访问的节点如果parent是nullptr那么//说明找到根节点都没有找到我是父亲左孩子的那个父亲说明这棵树已经访问//完了我们是用nullptr作为迭代器的end的_node parent;}return *this;}//找上一个节点Self operator--(){Node* subL _node-_left;//如果左子树存在那么当前节点的上一个节点就是左子树的最右节点if (subL ! nullptr){/*找左子树的左右节点*/Node* rightmost subL;while (rightmost-_right){rightmost rightmost-_right;}_node rightmost;}//如果左子树为nullptr那么沿祖先路径查找我是父亲的右孩子的那个父亲//因为我是父亲的右孩子那么我的前一个节点就是这个父亲else{Node* cur _node;Node* parent _node-_parent;while (parent){if (cur parent-_right){break;}else{cur parent;parent parent-_parent;}}_node parent;}return *this;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}public:Node* _node;};//反向迭代器是使用了适配器模式利用已有的正向迭代器适配出来的//传参时传的是正向迭代器Itreator然后利用正向迭代器的接口封装//出反向迭代器的接口template class Iterator,class Ref,class Ptrstruct __RBTree_reverse_iterator{typedef __RBTree_reverse_iteratorIterator, Ref, Ptr Self;public://构造函数利用正向迭代器构造出一个反向迭代器__RBTree_reverse_iterator(const Iterator it):_it(it){}//通过运算符重载得到我们想要的效果因为反向迭代器的就是正向迭代器的--//所以直接调用正向迭代器的--接口即可完成反向迭代器的操作Self operator(){--_it;return *this;}//同理反向迭代器的--就是正向迭代器的所以直接调用正向迭代器的即可Self operator--(){_it;return *this;}bool operator!(const Self it){return _it ! it._it;}Ref operator*(){return *_it;}Ptr operator-(){return (operator*());}private:Iterator _it;};template class K,class T,class KeyOfTclass RBTree{typedef RBTreeNodeT Node;public:typedef __RBTree_iteratorT, T, T* iterator; //正向普通迭代器typedef __RBTree_iteratorT, const T, const T* const_iterator; //正向const迭代器typedef __RBTree_reverse_iteratoriterator, T, T* reverse_iterator; //反向普通迭代器typedef __RBTree_reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;//反向const迭代器public:RBTree():_root(nullptr){}//拷贝构造RBTree(const RBTree rbt):_root(nullptr),_num(rbt._num){_root Copy(rbt._root);}Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* ret new Node(root-_data);ret-_col root-_col;ret-_left Copy(root-_left);if (ret-_left){ret-_left-_parent ret;}ret-_right Copy(root-_right);if (ret-_right){ret-_right-_parent ret;}return ret;}void Swap(Node* tmp){swap(_root, tmp);}//赋值重载RBTree operator(RBTree root){Swap(root._root);return *this;}//析构函数~RBTree(){clear();}Node* Find(const K key){KeyOfT kot;Node* cur _root;while (cur){if (key kot(cur-_data)){cur cur-_left;}else if (key kot(cur-_data)){cur cur-_right;}else{return cur;}}return nullptr;}pairiterator,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(data) kot(cur-_data)){parent cur;cur cur-_left;}else if (kot(data) kot(cur-_data)){parent cur;cur cur-_right;}else{return make_pair(cur, false);}}cur new Node(data);Node* newNode cur;if (kot(data) kot(parent-_data)){parent-_left cur;cur-_parent parent;}else if (kot(data) kot(parent-_data)){parent-_right cur;cur-_parent parent;}//走到这里已经插入完成后面是检查新插入的节点有没有破坏红黑树的规则的逻辑//检查新插入的节点是否满足红黑树的规则如果不满足就要进行变色/变色旋转//因为新插入的cur节点的颜色一定是红色的当cur的父节点存在并且为红色//时说明出现了连续的两个红色节点这时需要进行变色/变色旋转如果父节点// 不存在或者存在且为黑色时就无需再处理了。// 为什么父节点有可能不存在因为这是一个循环循环更新往祖先处理可能到达根节点//到了根节点就无需再处理了while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;if (cur parent-_left){// grandfather// parent//cur//画图//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续沿祖先路径检查cur grandfather;parent cur-_parent;//这里曾经漏写了}//叔叔不存在或者存在且为黑else//(unclenullptr||uncle-_colBLACK){//单纯的左边高进行右单旋变色RotateR(grandfather);grandfather-_col RED;parent-_col BLACK;//旋转完之后无需再沿祖先路径处理break;}}else//cur parent-_right{// grandfather// parent// cur//画图//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续往上调整cur grandfather;parent cur-_parent;//这里曾经忘记写}//叔叔不存在或者存在且为黑else//(unclenullptr || uncle-_col BLACK){//左右双旋RotateL(parent);RotateR(grandfather);//变色grandfather-_col RED;cur-_col BLACK;//旋转后就无需再沿祖先路径检查了具体原因画图理解break;}}}else//(parent grandfather-_right){Node* uncle grandfather-_left;if (cur parent-_right){// grandfather// parent// cur//画图//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续沿祖先路径检查cur grandfather;parent cur-_parent;}//叔叔不存在或者存在且为黑else//(unclenullptr || uncle-_col BLACK){//单纯的右边高进行左单旋变色RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;//旋转变色后就不需要再沿祖先路径检查了break;}}else//(cur parent-_left){// grandfather// parent// cur//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续沿祖先路径检查cur grandfather;parent cur-_parent;}//叔叔不存在或者存在且为黑else//(unclenullptr || uncle-_col BLACK){//根据模型可知需要右左双旋变色RotateR(parent);RotateL(grandfather);grandfather-_col RED;cur-_col BLACK;//旋转后就不需要再沿祖先路径检查了break;}}}}_num;//最后记得把根节点的颜色改成黑色_root-_col BLACK;return make_pair(iterator(newNode), true);}void clear(){Destroy(_root);_root nullptr;_num 0;}bool empty(){return _root nullptr;}iterator begin(){Node* leftmost _root;while (leftmost leftmost-_left){leftmost leftmost-_left;}return iterator(leftmost);}const_iterator begin() const{Node* leftmost _root;while (leftmost leftmost-_left){leftmost leftmost-_left;}return const_iterator(leftmost);}iterator end(){return iterator(nullptr);}const_iterator end() const{return const_iterator(nullptr);}reverse_iterator rbegin(){Node* rightmost _root;while (rightmost rightmost-_right){rightmost rightmost-_right;}return reverse_iterator(rightmost);}const_reverse_iterator rbegin() const{Node* rightmost _root;while (rightmost rightmost-_right){rightmost rightmost-_right;}return const_reverse_iterator(rightmost);}reverse_iterator rend(){return reverse_iterator(nullptr);}const_reverse_iterator rend() const{return const_reverse_iterator(nullptr);}size_t Size(){return _num;}bool Isbalance(){return _Isbalance(_root);}private:void Destroy(Node* root){if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}bool CheckColour(Node* root, int blackNum, int BenchMark){//走到空树说明这条路径已经走完了需要检查黑色节点的个数和基准值相不相等if (root nullptr){//如果不相等证明不平衡返回falseif (blackNum ! BenchMark){return false;}//如果相等则说明本条路径没有出事还要检查其它路径return true;}//如果出现连续红色节点证明这棵树出问题了返回falseif (root-_col RED root-_parent root-_parent-_col RED){return false;}if (root-_col BLACK){blackNum;}//递归检查所有路径的颜色return CheckColour(root-_left, blackNum, BenchMark) CheckColour(root-_right, blackNum, BenchMark);}bool _Isbalance(Node* root){//空树可以认为是平衡的if (root nullptr){return true;}//根节点不是黑色说明这棵树出事了if (root-_col ! BLACK){return false;}//先算出一条路径的黑色节点的个数作为基准值检查其它路径的黑色节点数目是否跟这个标准值//是否一样如果不一样就证明这棵树不平衡了那么如果这个基准值本身就是错的呢那也没有关系//只要有路径的黑色节点和其它路径不相等就说明肯定有其中一条路径出问题了至于是哪条路径//出问题就不重要了int BenchMark 0;Node* cur root;while (cur){if (cur-_col BLACK){BenchMark;}cur cur-_left;}//检查所有路径中是否有连续红色节点和各路径中黑色节点的数目是否相等return CheckColour(root, 0, BenchMark);}//旋转的细节如果不清楚的话请看上一篇关于AVL树的旋转红黑树的旋转和AVL树的旋转是一样的void RotateL(Node* parent){assert(parent);Node* cur parent-_right;Node* curleft cur-_left;Node* parentParent parent-_parent;parent-_right curleft;cur-_left parent;if (curleft){curleft-_parent parent;}parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left cur;}else{parentParent-_right cur;}cur-_parent parentParent;}}void RotateR(Node* parent){assert(parent);Node* cur parent-_left;Node* curright cur-_right;Node* parentParent parent-_parent;parent-_left curright;cur-_right parent;if (curright){curright-_parent parent;}parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left cur;}else{parentParent-_right cur;}cur-_parent parentParent;}}private:Node* _root nullptr;int _num 0;//统计树的节点个数};}以上就是利用红黑树封装map和set的内容啦因为map和set的接口太多了这里只是把插入接口和迭代器封装出来其它的接口就不一一封装了感兴趣的老铁可以自己尝试一下封装其它有用的接口哟。以上就是今天想要跟大家分享的内容咯你学会了吗如果你感觉到有所收获可以点点小心心点点关注哦后期还会持续更新C的相关知识哦我们下期见
