江苏环泰建设有限公司网站,阿里云 wordpress 建站,一个公司优化需要做多少个网站,做网站运营有前途么模拟实现map和set
map和set是红黑树的两种不同封装形式#xff0c;底层使用同一颗泛型结构的红黑树。set是红黑树的K模型#xff1b;map是红黑树的KV模型。
下面的代码和讲解着重体现红黑树的底层实现和map\set上层封装的衔接。关于二叉搜索树性质#xff0c;map和set的介…模拟实现map和set
map和set是红黑树的两种不同封装形式底层使用同一颗泛型结构的红黑树。set是红黑树的K模型map是红黑树的KV模型。
下面的代码和讲解着重体现红黑树的底层实现和map\set上层封装的衔接。关于二叉搜索树性质map和set的介绍搜索树的旋转红黑树的性质等内容请依次阅读下面几篇文章
【高阶数据结构】二叉搜索树 {概念实现核心结构增删查默认成员函数应用K模型和KV模型性能分析相关练习}【STL】map和set的介绍和使用 {关联式容器键值对map和setmultimap和multisetOJ练习}【高阶数据结构】AVL树 {概念及实现节点的定义插入并调整平衡因子旋转操作左单旋右单旋左右双旋右左双旋AVL树的验证及性能分析}【高阶数据结构】红黑树 {概念及性质红黑树节点的定义红黑树插入操作详细解释红黑树的验证} 一、红黑树的核心结构 问题一map和set底层使用同一颗泛型结构的红黑树如何处理map(pairkey,value)和set(key)存储值不同的问题 解决方案泛型底层红黑树的存储类型通过不同的实例化参数实现出map和set。
1.1 节点的定义
// RBTree.hpp
#pragma once
#include utility
#include assert.h
using std::pair;
using std::make_pair;enum Color{RED,BLACK
};template class T
struct RBTreeNode{typedef RBTreeNodeT Node;Node *_left;Node *_right;Node *_parent;T _data; //泛型底层红黑树的存储类型通过不同的实例化参数实现出map和set。Color _color;RBTreeNode(const T data T(), Color color RED):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_color(color){}
};1.2 红黑树的结构定义
STL中的红黑树结构
为了后续实现关联式容器map/setSTL红黑树的实现中增加一个头结点因为根节点必须为黑色为了与根节点进行区分将头结点给成红色并且让头结点的_parent域指向红黑树的根节点_left域指向红黑树中最小的节点_right域指向红黑树中最大的节点。 头结点的作用(begin, end) STL明确规定begin()与end()代表的是一段前闭后开的区间而对红黑树进行中序遍历后可以得到一个有序的序列因此begin()可以放在红黑树中最小节点(即最左侧节点)的位置end()放在最大节点(最右侧节点)的下一个位置关键是最大节点的下一个位置在哪块能否给成nullptr呢答案是行不通的因为对end()位置的迭代器进行–操作必须要能找最后一个元素此处就不行因此最好的方式是将end()放在头结点的位置 // RBTree.hpp
// K: key的类型
// T: 如果是map则为pairK, V; 如果是set则为K
// KofT: 通过T类型的data来获取key的一个仿函数类
template class K, class T, class KofT
class RBTree{typedef RBTreeNodeT Node; //第二个模版参数T决定红黑树的存储类型Node *_phead; //指向头结点的指针public:typedef RBT_iteratorT, T, T* iterator; //普通迭代器typedef RBT_iteratorT, const T, const T* const_iterator; //const迭代器//构造创建头结点RBTree(){_phead new Node(T(), RED); //为了和根节点区分头节点设为红色_phead-_left _phead-_right _phead;}//普通对象返回普通迭代器iterator begin(){return iterator(_phead-_left); //begin放在红黑树最左节点的位置}iterator end(){return iterator(_phead); //end放在头结点的位置} //const对象返回const迭代器const_iterator begin() const{ return const_iterator(_phead-_left); }const_iterator end() const{return const_iterator(_phead);}//插入和查找pairiterator, bool Insert(const T data);iterator Find(const K k);private://获取根节点注意返回指针的引用便于修改Node* GetRoot(){return _phead-_parent;}//获取最左节点Node* LeftMost(){Node *proot GetRoot();if(proot nullptr){return _phead;}else{Node *left proot;while(left-_left ! nullptr){left left-_left;}return left;}}//获取最右节点Node* RightMost(){Node *proot GetRoot();if(proot nullptr){return _phead;}else{Node *right proot;while(right-_right ! nullptr){right right-_right;}return right;}}//旋转void RotateL(Node *parent);void RotateR(Node *parent);二、红黑树的迭代器
2.1 迭代器的基本操作
红黑树的迭代器底层封装一个指向节点的指针基本操作的详细解释请参照list迭代器的实现。
// RBTree.hpp
templateclass T, class Ref, class Ptr
class RBT_iterator{typedef RBT_iteratorT, Ref, Ptr iterator;typedef RBTreeNodeT Node;Node *_pnode; //红黑树的迭代器底层封装一个指向节点的指针public://基本操作请参照list迭代器的实现不做过多解释RBT_iterator(Node *pnode):_pnode(pnode){}Ref operator*() const{ return _pnode-_data;}Ptr operator-() const{return _pnode-_data;}bool operator(const iterator it) const{return _pnode it._pnode;}bool operator!(const iterator it) const{return _pnode ! it._pnode;}//......
};2.2 operator
红黑树迭代器的实现难点在于和–操作 operator中序左子树根右子树 如果当前节点的右子树不为空就是找右子树中序的第一个节点最左节点。11-12。 如果当前节点的右子树为空就是找孩子不是右节点的那个祖先。7-8。 特殊情况根节点没有右孩子迭代器在根位置如下图此时进行迭代器因该指向头结点end遍历结束。但如果按照上面的逻辑由于根节点恰好是头结点的右孩子根节点没有右孩子最终迭代器又会指向根节点永远无法到达头结点end导致程序陷入死循环。因此需要特殊处理。 提示右子树为空或孩子是右节点说明这棵子树已经遍历访问完了。 //前置和后置后置复用前置iterator operator(){if(_pnode-_right ! nullptr) //如果右子树不为空就是找右子树的最左节点{Node *left _pnode-_right; while(left-_left ! nullptr){left left-_left;}_pnode left;}else //如果右子树为空就是找孩子不是右节点的那个祖先{Node *parent _pnode-_parent;while(_pnode parent-_right){_pnode parent;parent parent-_parent;}//特殊情况根节点没有右孩子迭代器在根位置。//经过循环此时_pnode指向头节点parent指向根节点做特殊处理使_pnode指向头结点if(_pnode-_right ! parent)_pnode parent;}return *this;}iterator operator(int){iterator it(_pnode);*this;return it;}2.3 operator– operator–和相反右子树根左子树
如果当前节点的左子树不为空–就是找左子树的最右节点。8-7如果当前节点的左子树为空–就是找孩子不是左节点的那个祖先。12-11特殊情况如果迭代器指向end即头结点。此时进行–操作因该使迭代器指向最右节点。–操作也存在操作中的特殊情况——根节点没有左孩子。但不需要做特殊处理–后仍指向根节点即可。 提示左子树为空或孩子是左节点说明这棵子树已经遍历访问完了。 //前置和后置--后置复用前置iterator operator--(){//特殊情况如果迭代器指向end进行--操作因该使迭代器指向最右节点。if(_pnode-_parent-_parent _pnode _pnode-_color RED){_pnode _pnode-_right;}else if(_pnode-_left ! nullptr) //如果左子树不为空--就是找左子树的最右节点{Node *right _pnode-_left;while(right-_right ! nullptr){right right-_right;}_pnode right;}else //如果左子树为空--就是找孩子不是左节点的那个祖先{Node *parent _pnode-_parent;while(_pnode parent-_left){_pnode parent;parent parent-_parent;}_pnode parent; //不需要特殊处理}return *this;}iterator operator--(int){iterator it(_pnode);--*this;return it;}三、红黑树的插入和查找 问题二在进行查找、插入、删除等操作时要对key值进行比较。在同一模版中如何区别比较map和set中的key值 解决方案通过传入仿函数KofT(KeyofTree)解决。如果是set传入SetKofT返回data的值如果是map传入MapKofT返回data.first的值 注意pair中重载了关系运算符但first和second都参与运算不符合要求。要求只比较pair.first (key)。
3.1 插入
pairiterator, bool Insert(const T data){Node* rproot GetRoot(); //这里注意要用引用接收返回值if(rproot nullptr){rproot new Node(data, BLACK); //因为GetRoot返回指针的引用所以改的实际是_phead-_parentrproot-_parent _phead;_phead-_left _phead-_right rproot;//返回pairiterator, bool方便实现operator[]。return make_pair(iterator(rproot), true); }KofT kot; //创建KofT对象用于取出data中的keyNode *cur rproot;Node *parent nullptr;while(cur ! nullptr){parent cur;if(kot(data) kot(cur-_data)) //不管是map还是set都能正确的取出key进行比较。cur cur-_right;else if(kot(data) kot(cur-_data))cur cur-_left;elsereturn make_pair(iterator(cur), false);}cur new Node(data, RED);if(kot(data) kot(parent-_data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;Node* newnode cur; //在调整红黑树的过程中cur的指向会改变所以要提前记录新节点的指针。//上一次循环中grandparent 为根节点此次循环parent _phead//关于红黑树性质的检查和平衡调整请阅读文章【高阶数据结构】红黑树while(parent ! _phead parent-_color RED){Node* grandparent parent-_parent;assert(grandparent!nullptr);assert(grandparent-_color BLACK);Node* uncle grandparent-_left;if(grandparent-_left parent)uncle grandparent-_right;if(uncle ! nullptr uncle-_color RED){parent-_color uncle-_color BLACK;grandparent-_color RED;cur grandparent;parent grandparent-_parent;}else{if(parent grandparent-_left){if(cur parent-_left){RotateR(grandparent);parent-_color BLACK;grandparent-_color RED;}else{RotateL(parent);RotateR(grandparent);cur-_color BLACK;grandparent-_color RED;}}else{if(cur parent-_right){RotateL(grandparent);parent-_color BLACK;grandparent-_color RED;}else{RotateR(parent);RotateL(grandparent);cur-_color BLACK;grandparent-_color RED;}}break;}} //end of while//如果在调整过程中将根节点变为红色记得重新变回黑色。if(parent _phead)cur-_color BLACK;//令头节点的左指针指向红黑树的最左节点_phead-_left LeftMost();//令头节点的右指针指向红黑树的最右节点_phead-_right RightMost();//返回pairiterator, bool方便实现operator[]。return make_pair(iterator(newnode), true);}3.2 旋转 void RotateL(Node *parent){Node* subR parent-_right;Node* subRL subR-_left;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;parent-_right subRL;if(subRL ! nullptr)subRL-_parent parent;if(ppNode _phead) //如果parent是根节点要修改头结点的_parent指针。{_phead-_parent subR;}else{if(parent ppNode-_left)ppNode-_left subR; elseppNode-_right subR;}subR-_parent ppNode;}void RotateR(Node *parent){Node *subL parent-_left;Node *subLR subL-_right;Node *ppNode parent-_parent;subL-_right parent;parent-_parent subL;parent-_left subLR;if(subLR ! nullptr)subLR-_parent parent;if(ppNode _phead) //如果parent是根节点要修改头结点的_parent指针。{_phead-_parent subL;}else{if(parent ppNode-_left)ppNode-_left subL;elseppNode-_right subL;}subL-_parent ppNode;}3.3 查找 iterator Find(const K k){KofT kot; //创建KofT对象用于取出data中的keyNode *cur GetRoot();if(cur nullptr) return end(); //如果是空树返回end。while(cur ! nullptr){if(k kot(cur-_data)) //不管是map还是set都能正确的取出key进行比较。cur cur-_right;else if(k kot(cur-_data))cur cur-_left;elsereturn iterator(cur); //找到返回指向节点的迭代器}return end(); //如果找不到返回end。}四、map和set的封装
4.1 map
//Map.hpp
#pragma once
#include RBTree.hppnamespace zty{template class K, class Vclass map{//MapKofT返回kv.firststruct MapKofT{const K operator()(const pairK,V kv){return kv.first;}};//map是KV模型的红黑树存储pairK,V键值对typedef RBTreeK, pairK,V, MapKofT RBT;RBT _rbt;public://取类模版中的内嵌类型时需要在类型前加typename告诉编译器后面这一串是类型不是静态成员。typedef typename RBT::iterator iterator; //map的迭代器类型typedef typename RBT::const_iterator const_iterator; //const迭代器//C11的用法使用了default关键字表示使用编译器自动生成的默认构造函数map() default;//迭代器区间构造 template class InputIteratormap(InputIterator first, InputIterator last){while(first!last){_rbt.Insert(*first);first;}}iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}const_iterator begin() const{return _rbt.begin();}const_iterator end() const{return _rbt.end();}std::pairiterator, bool insert(const pairK,V kv){return _rbt.Insert(kv);}//Insert返回pairiterator, bool方便实现operator[]。//具体内容阅读文章【STL】map和set的介绍和使用 V operator[](const K k){pairiterator, bool ret _rbt.Insert(make_pair(k, V()));return ret.first-second;}iterator find(const K k){return _rbt.Find(k);}};
}4.2 set
//Set.hpp
#pragma once
#include RBTree.hppnamespace zty{
template class Kclass set{//SetKofT返回kstruct SetKofT{const K operator()(const K k){return k;}};//set是K模型的红黑树只存储key值typedef RBTreeK, K, SetKofT RBT;RBT _rbt;public://取类模版中的内嵌类型时需要在类型前加typename告诉编译器后面这一串是类型不是静态成员。typedef typename RBT::iterator iterator; //set的迭代器类型typedef typename RBT::const_iterator const_iterator; //const迭代器//C11的用法使用了default关键字表示使用编译器自动生成的默认构造函数set() default;//迭代器区间构造template class InputIteratorset(InputIterator first, InputIterator last){while(first!last){_rbt.Insert(*first);first;}}iterator begin(){return _rbt.begin();} iterator end(){return _rbt.end();}const_iterator begin() const{return _rbt.begin();}const_iterator end() const{return _rbt.end();}std::pairiterator, bool insert(const K k){return _rbt.insert(k);}iterator find(const K k){return _rbt.Find(k);}};
}
