网站建设承诺,国外建站数据,大兴建设网站,萧山中兴建设有限公司网站目录
介绍
红黑树代码
set
insert的迭代器转换问题
为什么会有这样的问题?
如何解决
代码
map
注意点
代码 介绍 set和map的底层都是红黑树,所以我们可以在自己实现的红黑树(简易版)的基础上,进行封装,成为简易的set和map 红黑树代码
#pragma once#include …目录
介绍
红黑树代码
set
insert的迭代器转换问题
为什么会有这样的问题?
如何解决
代码
map
注意点
代码 介绍 set和map的底层都是红黑树,所以我们可以在自己实现的红黑树(简易版)的基础上,进行封装,成为简易的set和map 红黑树代码
#pragma once#include iostream
#include vector
#include string
#include queue
#include cassert
#include cstdlib
#include utility// 有迭代器的红黑树
namespace my_RB_Tree
{enum colour{black,red};template class Tstruct RBTreeNode // 结点{RBTreeNode(const T data): _left(nullptr),_right(nullptr),_parent(nullptr),_col(red),_data(data){}RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;colour _col;T _data;};template class T, class Ptr, class Ref // T是元素类型,ptr是指针类型,ref是引用类型(后两种会有const类型)struct RBTreeIterator // 迭代器{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, Ptr, Ref Self;//为了可以能让普通迭代器初始化const迭代器,需要来一个普通迭代器对象typedef RBTreeIteratorT, T*, T iterator;Node* _pNode;RBTreeIterator(Node* pNode): _pNode(pNode){}RBTreeIterator(const iterator it) // const迭代器时,它是一个初始化;普通迭代器时,它是一个拷贝: _pNode(it._pNode){}// 让迭代器具有类似指针的行为Ref operator*(){return _pNode-_data;}Ptr operator-(){return (_pNode-_data);}// 让迭代器可以移动前置/后置Self operator(){Increament();return *this;}Self operator(int){Self tmp(*this);Increament();return tmp;}// 让迭代器可以移动前置/后置--Self operator--(){DeIncreament();return *this;}Self operator--(int){Self tmp(*this);DeIncreament();return tmp;}// 让迭代器可以比较bool operator!(const Self s) const{return _pNode ! s._pNode;}bool operator(const Self s) const{return _pNode s._pNode;}private:void Increament();void DeIncreament();};// 为了后序封装map和set本代码的红黑树会有一个作为哨兵位的头结点template class K, class T, class KeyOfT // K是关键字的类型,T是元素类型(区分这两个的原因:会用该红黑树封装成set和map,而map是key_value的)// keyofT是返回关键字类型的值(否则map无法返回)class RBTree // 红黑树{public:typedef RBTreeNodeT Node;typedef RBTreeIteratorT, T*, T iterator;typedef RBTreeIteratorT, const T*, const T const_iterator;public:RBTree(){_pHead new Node(T());_pHead-_left _pHead;_pHead-_parent nullptr;_pHead-_right _pHead;}// 在红黑树中插入值为data的节点插入成功返回true否则返回falsestd::pairiterator, bool Insert(const T data);// 检测红黑树中是否存在值为data的节点存在返回该节点的地址否则返回nullptrNode* Find(const K data);// 获取红黑树最左侧节点Node* LeftMost() const;// 获取红黑树最右侧节点Node* RightMost() const;iterator begin(){return iterator(LeftMost());}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(LeftMost());}const_iterator end() const{return const_iterator(_pHead);}// 检测红黑树是否为有效的红黑树注意其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){Node* root _pHead-_parent;if (root-_col red){return false;}int count 0;find_blacknode(count, _pHead-_parent);return _IsValidRBTRee(_pHead-_parent, count, 0);}private:bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack);// 左单旋void RotateL(Node* pParent);// 右单旋void RotateR(Node* pParent);// 为了操作树简单起见获取根节点Node* GetRoot(){return _pHead-_parent;}void find_blacknode(int count, Node* root){if (root nullptr){return;}if (root-_col black){count;}find_blacknode(count, root-_left);find_blacknode(count, root-_right);}private:Node* _pHead nullptr;};template class K, class T, class KeyOfTvoid RBTreeK, T, KeyOfT::RotateL(Node* pParent){Node* cur pParent-_right, * curleft cur-_left;// 连接p和cur左树,因为该位置被p占据pParent-_right curleft;if (curleft){curleft-_parent pParent;}// 连接父结点if (pParent-_parent ! _pHead){Node* ppnode pParent-_parent;if (ppnode-_left pParent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}else{_pHead-_parent cur;cur-_parent _pHead;}// 连接p和curpParent-_parent cur;cur-_left pParent;}template class K, class T, class KeyOfTvoid RBTreeK, T, KeyOfT::RotateR(Node* pParent){Node* cur pParent-_left, * curright cur-_right;// 连接p和cur右树,因为该位置被p占据pParent-_left curright;if (curright){curright-_parent pParent;}// 连接父结点if (pParent-_parent ! _pHead){Node* ppnode pParent-_parent;if (ppnode-_left pParent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}else{_pHead-_parent cur;cur-_parent _pHead;}// 连接p和curpParent-_parent cur;cur-_right pParent;}template class K, class T, class KeyOfTtypename RBTreeK, T, KeyOfT::Node* RBTreeK, T, KeyOfT::LeftMost() const{Node* cur _pHead-_parent;while (cur-_left){cur cur-_left;}return cur;}template class K, class T, class KeyOfTtypename RBTreeK, T, KeyOfT::Node* RBTreeK, T, KeyOfT::RightMost() const{Node* cur _pHead-_parent;while (cur-_right){cur cur-_right;}return cur;}template class K, class T, class KeyOfTtypename RBTreeK, T, KeyOfT::Node* RBTreeK, T, KeyOfT::Find(const K data) // 注意这里,{Node* cur _pHead-_parent;KeyOfT kot;while (cur){if (data kot(cur-_data)){cur cur-_right;}else if (data kot(cur-_data)){cur cur-_left;}else{return cur;}}return nullptr;}template class K, class T, class KeyOfTstd::pairtypename RBTreeK, T, KeyOfT::iterator, bool RBTreeK, T, KeyOfT::Insert(const T data) // 为了和map适配,要返回pair类型//(first是插入元素所在的迭代器,second是bool值,判断是否成功插入){KeyOfT kot;Node* newnode nullptr;if (_pHead-_parent nullptr){newnode new Node(data);newnode-_col black;_pHead-_parent newnode;newnode-_parent _pHead;return std::make_pair(iterator(newnode), true);}else{Node* cur _pHead-_parent, * parent cur;while (cur){if (kot(data) kot(cur-_data)){parent cur;cur cur-_right;}else if (kot(data) kot(cur-_data)){parent cur;cur cur-_left;}else{return std::make_pair((iterator)cur, false);}}newnode new Node(data);cur newnode;cur-_parent parent;if (kot(parent-_data) kot(cur-_data)){parent-_left cur;}else{parent-_right cur;}Node* grandfather nullptr;while (parent ! _pHead parent-_col red){grandfather parent-_parent; // 因为父结点是红色,所以肯定有爷爷结点(注意红黑树规则:根结点必须是黑色)if (grandfather-_left parent) // 确定父亲位置{Node* uncle grandfather-_right; // 也就能确定叔叔位置if (uncle uncle-_col red){parent-_col uncle-_col black;grandfather-_col red;}else // 如果uncle不存在/为黑,就需要旋转变色了{// 需要先判断旋转类型(也就是判断 -- parent和cur的相对位置)if (parent-_left cur){// 一条偏右的直线,需要右旋RotateR(grandfather);// 旋转完后parent成为根结点// 更改完结点指向后,就可以改颜色了(都是根结点为黑,另外两个为红)parent-_col black;cur-_col grandfather-_col red; // 和cur一层}else{// 拐角在左边,也就是先左旋,再右旋RotateL(parent);RotateR(grandfather);// cur成为根结点// 改颜色cur-_col black;parent-_col grandfather-_col red;}break;}}else // parent在grandfather的右树{Node* uncle grandfather-_left;if (uncle uncle-_col red){parent-_col uncle-_col black;grandfather-_col red;}else // 如果uncle不存在/为黑,就需要旋转变色了{// 需要先判断旋转类型(也就是判断 -- parent和cur的相对位置)if (parent-_right cur){// 一条偏左的直线,需要左旋RotateL(grandfather);parent-_col black;cur-_col grandfather-_col red; // 和cur一层}else{// 拐角在右边,也就是先右旋,再左旋RotateR(parent);RotateL(grandfather);// 改颜色cur-_col black;parent-_col grandfather-_col red;}break;}}cur grandfather; // 注意,这里会改cur的指向,但返回值需要返回插入位置的迭代器,所以需要另外保存parent cur-_parent;}(_pHead-_parent)-_col black; // 根结点必须为黑(防止它在上面的循环中被修改)}_pHead-_left LeftMost();_pHead-_right RightMost();//std::cout (_pHead-_left)-_data (_pHead-_right)-_data std::endl;return std::make_pair(iterator(newnode), true);}template class K, class T, class KeyOfTbool RBTreeK, T, KeyOfT::_IsValidRBTRee(Node* cur, size_t blackCount, size_t pathBlack){if (cur nullptr){// 到空结点后,就说明一条路径已经走通了,可以用得到的黑色结点数与基准数对比,不一样就说明红黑树错误if (pathBlack ! blackCount){return false;}else{return true;}}if (cur-_parent){Node* ppnode cur-_parent;if (cur-_col red ppnode-_col red){return false;}}if (cur-_col black){pathBlack;}return _IsValidRBTRee(cur-_left, blackCount, pathBlack) _IsValidRBTRee(cur-_right, blackCount, pathBlack);}template class T, class Ptr, class Refvoid RBTreeIteratorT, Ptr, Ref::Increament(){Node* cur _pNode, * parent _pNode-_parent;if (cur-_right){// 找到右子树的最小结点Node* curright cur-_right;while (curright-_left){curright curright-_left;}_pNode curright;}else{while (parent-_parent ! cur parent-_right cur) // 找到cur是parent的左结点的位置,这样parent的位置就是下一个位置{cur parent;parent parent-_parent;}_pNode parent;}}template class T, class Ptr, class Refvoid RBTreeIteratorT, Ptr, Ref::DeIncreament(){Node* cur _pNode, * parent _pNode-_parent;if (cur-_left){// 找到左子树的最大结点Node* curleft cur-_left;while (curleft-_right){curleft curleft-_right;}_pNode curleft;}else{while (parent-_parent ! cur parent-_left cur) // 找到cur是parent的左结点的位置,这样parent的位置就是下一个位置{cur parent;parent parent-_parent;}_pNode parent;}}
}
set
set我们只实现它的插入和迭代器部分,大概可以看到效果就行
insert的迭代器转换问题 不考虑别的,因为insert返回的都是pair类型的,都是迭代器布尔值,所以set直接调用红黑树的插入即可 但是,编译过不去! 大概就是说,普通迭代器无法转换为const迭代器 为什么会有这样的问题? 注意,set中,无论是普通迭代器还是const迭代器,其实都封装的是红黑树的const迭代器 stl源码中就是这么定义的: 但是,tree的insert返回的是普通迭代器,而set的insert要返回的是const迭代器这就存在一个普通迭代器向const迭代器转换的过程 如何解决 所以我们需要在红黑树的迭代器类中增加这一功能 typedef RBTreeNodeT Node;
typedef RBTreeIteratorT, Ptr, Ref Self;
//为了可以能让普通迭代器初始化const迭代器,需要来一个普通迭代器对象
typedef RBTreeIteratorT, T*, T iterator;
Node* _pNode;RBTreeIterator(Node* pNode): _pNode(pNode)
{}
RBTreeIterator(const iterator it) // const迭代器时,它是一个初始化;普通迭代器时,它是一个拷贝: _pNode(it._pNode)
{}代码
#include RB_Tree.hppnamespace my_set
{template class Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename my_RB_Tree::RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename my_RB_Tree::RBTreeK, K, SetKeyOfT::const_iterator const_iterator;const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}std::pairiterator, bool insert(const K data) {//return _t.Insert(data);//这里在构建时,set的insert调用tree的insert//而tree中insert的返回值,返回的pair中,第一个成员是tree的普通迭代器//然后回到该函数,该函数返回的pair的第一个成员是set中的普通迭代器(实质上是tree中的const迭代器)//所以我们本质上是用不同类型的pair在赋值//所以要先转换std::pairtypename my_RB_Tree::RBTreeK, K, SetKeyOfT::iterator, bool ret _t.Insert(data); //这里是tree的普通迭代器iterator it(ret.first);return std::pairiterator, bool(it,ret.second); //这里是要用普通迭代器初始化一个const迭代器,所以需要在tree迭代器中增加这个功能}private:my_RB_Tree::RBTreeK, K, SetKeyOfT _t;};
}
map 注意点 map的重点就在insert和[ ]的重载上 也没啥别的了,就需要自己先构建一个pair类型,其他的就注意返回值和接收值到底是谁 K:key值类型 V:value类型 T:map的元素类型 代码
#include RB_Tree.hppnamespace my_map
{template class K, class Vclass map{public:typedef std::pairconst K, V T; // map中key不能变value可以变struct MapKeyOfT{const V operator()(const T data){return data.second;}};typedef typename my_RB_Tree::RBTreeK, T, MapKeyOfT::iterator iterator;typedef typename my_RB_Tree::RBTreeK, T, 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();}std::pairiterator, bool insert(const T data){return _t.Insert(data);}V operator[](const K data){auto ret insert(std::make_pair(data,V()));return (ret.first)-second;}private:my_RB_Tree::RBTreeK, T, MapKeyOfT _t;};
}
