网站建设实施方案及预算,男男床做视频网站在线,陕西大型网站建设,网站创建工具每一个不曾起舞的日子都是对生命的辜负 红黑树封装map和set前言一.改良红黑树的数据域结构1.1 改良后的结点1.2 改良后的类二. 封装的set和map2.1 set.h2.2 map.h三. 迭代器3.1 迭代器封装3.2 const迭代器四.完整代码实现4.1 RBTree.h4.2 set.h4.3 map.h4.4 Test.cpp前言 上一节… 每一个不曾起舞的日子都是对生命的辜负 红黑树封装map和set前言一.改良红黑树的数据域结构1.1 改良后的结点1.2 改良后的类二. 封装的set和map2.1 set.h2.2 map.h三. 迭代器3.1 迭代器封装3.2 const迭代器四.完整代码实现4.1 RBTree.h4.2 set.h4.3 map.h4.4 Test.cpp前言 上一节中说到了红黑树的实现并且已经知道map和set的底层共用了同一套红黑树的结构。但这样就会出现一个问题map的数据域和set不一样比较大小的方式自然也就不一样。因此上一篇中的红黑树还需要做出一些改变才能用来实现map和set。 一.改良红黑树的数据域结构 对于如何设计针对map、set的红黑树结构看源码的实现无疑是最好的方式 对于源码的实现我们知道set是k,k的键值对但是在使用时却只显示一个kmap是k,value的键值对通过观察源码发现map的节点结构为rb_treekey_type, value_type但发现其设计方式很特殊value_type是pairconst Key, T的重命名也就是说map节点结构的key_type并不作为数据域value_type单一类型就充当了数据域而key_type实际上可以充当查找的作用。因此下面改良红黑树就采用这种方式一个类型T作为结点的全部数据域。 1.1 改良后的结点
enum Color//颜色采用枚举但STL库采用的是特殊的bool值后续会看
{RED,//0BLACK//1
};templateclass T
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Color _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};与之前的双参数class K, class V相比改良之后的T作为了全部的数据域即T也可以代表pair类型。
1.2 改良后的类
在前言中提到比较方式也是一个头疼的问题这个时候就可以自己封装一个比较方式即以仿函数的形式进行比较。 由于只有比较方式进行了改变因此除了insert其他的都没有变化所以下面只展示insert enum Color//颜色采用枚举但STL库采用的是特殊的bool值后续会看
{RED,//0BLACK//1
};templateclass T
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Color _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};// set-RBTreeK, K, SetKeyOfT _t;
// map-RBTreeK, pairconst K, V, MapKeyOfT _t;
templateclass K, class T, class KeyOfT//新增的KeyOfT就是仿函数
class RBTree
{typedef RBTreeNodeT Node;
public:bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;//根节点为黑色return true;}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);cur-_col RED;//重要插入的结点初始化成红色if (kot(parent-_data) kot(data)){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}while (parent parent-_col RED)//如果父亲的颜色为红才需要去处理{Node* grandfather parent-_parent;//找到祖父才能找到叔叔if (parent grandfather-_left){Node* uncle grandfather-_right;//看叔叔颜色//情况1uncle存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//情况2或3不用考虑叔叔的问题即叔叔为空还是为黑{if (cur parent-_left)//情况2{// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//情况3{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else//与上述代码的左右反过来了而已步骤一样但左右相反。{Node* uncle grandfather-_left;//情况1if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//情况2和3{// g// p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}}}}_root-_col BLACK;return true;}
private:Node* _root nullptr;
};
二. 封装的set和map 以仿函数封装就可以完成比较。 2.1 set.h
#pragma once
#includeRBTree.hnamespace cfy
{templateclass Kclass set{struct SetKeyOfT//仿函数{const K operator()(const K key){return key;}};public:bool insert(const K key){return _t.Insert(key);}private:RBTreeK, K, SetKeyOfT _t;};void test_set(){int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };setint s;for (auto e : a){s.insert(e);}}
}2.2 map.h
#pragma once
#includeRBTree.h
namespace cfy
{templateclass K, class Vclass map{struct MapKeyOfT//仿函数{const K operator()(const pairconst K, V kv){return kv.first;}};public:bool insert(const pairconst K, V kv){return _t.Insert(kv);}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};void test_map(){int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };mapint, int m;for (auto e : a){m.insert(make_pair(e, e));}}
}三. 迭代器
需要将有关迭代器的功能都封装起来这在之前的vector、list模拟实现时已经了解过。对于map和set的迭代器重要的函数重载就是和–了。为了map和set能够共用这一套迭代器因此将其封装在RBTree里。
3.1 迭代器封装
迭代器的好处是可以方便遍历是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器需要考虑以前问题begin()与end() STL明确规定begin()与end()代表的是一段前闭后开的区间而对红黑树进行中序遍历后可以得到一个有序的序列因此begin()可以放在红黑树中最小节点(即最左侧节点)的位置end()放在最大节点(最右侧节点)的下一个位置关键是最大节点的下一个位置在哪块 能否给成nullptr呢答案是行不通的因为对end()位置的迭代器进行–操作必须要能找最后一个元素此处就不行因此最好的方式是将end()放在头结点的位置
但由于我们上一届中设计的RBTree没有头结点这个结构因此我们也就不与STL的实现方式完全一样end()就直接设置为nullptr。
//迭代器
templateclass T
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT Self;//迭代器类进行typedefNode* _node;__RBTreeIterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}//迭代器//迭代器--//上面两个都拿出来在下面bool operator!(const Self s){return _node ! s._node;}};一. 对于有这么两种选择
如果右树不为空则找到右树的最左节点。如果右树为空则找到孩子是父亲的左孩子的那个祖先。
Self operator()//迭代器返回的还是迭代器
{if (_node-_right)//1.右不为空找到右子树的最左节点{Node* min _node-_right;while (min-_left){min min-_left;}_node min;}else//2.右为空则找祖先孩子是父亲的左的那个祖先{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;
}二. 对于–有这么两种选择事实上思路就是与相反
如果左树不为空则找到左树的最右结点也就是最大结点)。如果左树为空则找到孩子是父亲的右孩子的那个祖先。
Self operator--()
{if (_node-_left){Node* max _node-_left;while (max-_right)//max一定存在因此不需要写出max条件{max max-_right;}_node max;}else{Node* cur _node;Node* parent _node-_parent;while (parent cur parent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;
}3.2 const迭代器
如果是const迭代器那可以在迭代器类中多加上两个模板参数T, T*偏特化当然实际上是RefPtr的全特化由于set不能修改因此set的普通迭代器和const迭代器都应该是const类型但map的value可以修改因此我们就需要在RBTree中把普通迭代器和const迭代器均实现出来。此外对于map来讲需要实现operator[]的重载因此我们插入函数返回的值也应该从bool变成pair类型这样才便于在operator[]重载中进行操作。由于代码繁琐且需要处理一些细节问题因此代码的注释将会就那些进行解释看下面代码就可以了。
四.完整代码实现 提示需要注意细节问题如普通迭代器可以赋值给const迭代器的原理。 4.1 RBTree.h
#pragma onceenum Color//颜色采用枚举但STL库采用的是特殊的bool值后续会看
{RED,//0BLACK//1
};templateclass T
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Color _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};//迭代器
// class T, T, T*
templateclass T, class Ref, class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;//迭代器类进行typedef//如果Ref和Ptr都是非const则下面与上面没区别但如果是const则下面仍是非const因此可以const迭代器可以赋值给非const就是因为下面的这个就是一个构造typedef __RBTreeIteratorT, T, T* iterator;//满足普通迭代器可以赋值给const迭代器Node* _node;__RBTreeIterator(Node* node):_node(node){}// 普通迭代器的时候他是拷贝构造// const迭代器的时候他是构造支持用普通迭代器构造const迭代器__RBTreeIterator(const iterator s)//加上这个就满足普通迭代器赋值给const迭代器:_node(s._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator()//迭代器返回的还是迭代器{if (_node-_right)//1.右不为空找到右子树的最左节点{Node* min _node-_right;while (min-_left){min min-_left;}_node min;}else//2.右为空则找祖先孩子是父亲的左的那个祖先{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){if (_node-_left){Node* max _node-_left;while (max-_right)//max一定存在因此不需要写出max条件{max max-_right;}_node max;}else{Node* cur _node;Node* parent _node-_parent;while (parent cur parent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}bool operator!(const Self s) const{return _node ! s._node;}};// set-RBTreeK, K, SetKeyOfT _t;
// map-RBTreeK, pairconst K, V, MapKeyOfT _t;
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef __RBTreeIteratorT, T, T* iterator;typedef __RBTreeIteratorT, 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);}const_iterator begin() const{Node* left _root;while (left left-_left){left left-_left;}return const_iterator(left);}const_iterator end() const{return const_iterator(nullptr);}pairiterator, bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;//根节点为黑色return make_pair(iterator(_root), true);}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 make_pair(iterator(cur), false);}}cur new Node(data);Node* newnode cur;//加上这个是为了pair返回值时return的时候需要返回因为cue会变因此记录一下这个结点cur-_col RED;//重要插入的结点初始化成红色if (kot(parent-_data) kot(data)){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}while (parent parent-_col RED)//如果父亲的颜色为红才需要去处理{Node* grandfather parent-_parent;//找到祖父才能找到叔叔if (parent grandfather-_left){Node* uncle grandfather-_right;//看叔叔颜色//情况1uncle存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//情况2或3不用考虑叔叔的问题即叔叔为空还是为黑{if (cur parent-_left)//情况2{// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//情况3{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else//与上述代码的左右反过来了而已步骤一样但左右相反。{Node* uncle grandfather-_left;//情况1if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//情况2和3{// g// p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}}}}_root-_col BLACK;return make_pair(iterator(newnode), true);}//旋转代码和AVL一样只是去掉了平衡因子void RotateL(Node* parent)//左单旋{//1.记录subR, subRLNode* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)//subRL不为空则需要连接到parent{subRL-_parent parent;}Node* ppNode parent-_parent;//记录保存subR-_left parent;parent-_parent subR;if (ppNode nullptr)//说明根节点变化{_root subR;_root-_parent nullptr;}else//如果是局部子树{//判断ppNode之前是左连接还是右连接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 (ppNode nullptr){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}void Inorder(){_Inorder(_root);}bool IsBalance()//检查是否为红黑树结构{if (_root nullptr){return true;}if (_root-_col ! BLACK){return false;}int ref 0;Node* left _root;while (left){if (left-_col BLACK){ref;}left left-_left;}//遍历这棵树就好了检查是否存在连续的红结点。//检查父亲因为孩子不一定有但是一定有父亲return Check(_root, 0, ref);}private:bool Check(Node* root, int blackNum, int ref){if (root nullptr){if (blackNum ! ref){cout 违反规则一条路径上的黑色节点数量不同 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续红色结点 endl;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);}void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}Node* _root nullptr;
};
4.2 set.h
#pragma once
#includeRBTree.hnamespace cfy
{templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public://加上typename是由于没有实例化的模板不能进行typedef。由于不能修改因此均用consttypedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;iterator begin() const{return _t.begin();//_t.begin()是普通迭代器iterator是const,因此需要修改}iterator end() const{return _t.end();}pairiterator, bool insert(const K key){//直接return会造成const与非const的类型不匹配//因为set的iterator默认就是const但return的并不是const//因此需要如下修正pairtypename RBTreeK, K, SetKeyOfT::iterator, bool ret _t.Insert(key);return pairiterator, bool(ret.first, ret.second);}private:RBTreeK, K, SetKeyOfT _t;};void test_set(){int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };setint s;for (auto e : a){s.insert(e);}setint::iterator it s.begin();while (it ! s.end()){//*it 10;//set这里不能被修改因此const迭代器统一cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;}
}4.3 map.h
#pragma once
#includeRBTree.h
namespace cfy
{templateclass K, class Vclass map{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public://加上typename是由于没有实例化的模板不能进行typedef。typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::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();}pairiterator, bool insert(const pairconst K, V kv){return _t.Insert(kv);}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};void test_map(){int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };mapint, int m;for (auto e : a){m.insert(make_pair(e, e));}mapint, int::iterator it m.begin();while (it ! m.end()){//it-first; 经过const就不能修改了it-second;//允许被修改cout it-first : it-second endl;it;}cout endl;//map统计水果操作的次数string arr[] { 苹果, 西瓜, 香蕉, 草莓, 西瓜,苹果, 苹果,西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){countMap[e];}for (const auto kv : countMap)//注意加引用不给就是拷贝构造代价大{cout kv.first : kv.second endl;}}
}4.4 Test.cpp
#includeiostream
#includemap
#includeset
using namespace std;
#includeRBTree.h
#includeMap.h
#includeSet.h
int main()
{cfy::test_set();cfy::test_map();return 0;
}
