什么网站可以免费发广告,wordpress vue主题,品牌建设促进中心,网站建设工作室wp主题模板点击蓝字关注我们一、红黑树及其节点的设计对于底层都是红黑树的map和set来说#xff0c;他们之间存在的最大的区别就是#xff1a;对于set是K模型的容器#xff0c;而map是KV模型的容器。为了更好的灵活兼容实现map和set#xff0c;就需要在红黑树以及树节点上进行特别的设…点击蓝字关注我们一、红黑树及其节点的设计对于底层都是红黑树的map和set来说他们之间存在的最大的区别就是对于set是K模型的容器而map是KV模型的容器。为了更好的灵活兼容实现map和set就需要在红黑树以及树节点上进行特别的设计1、树节点的设计对于红黑树的节点我们需要节点对于set来说储存key对于map来说储存key-value键值对所以这里我们就直接让节点类型的阈值类型为T用来控制储存类型实现代码templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;//T可以是key也可以是pairK,VColour _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};解释对于set实现我们传入key对于map实现我们传入pairkey,value由此满足set和map各自的需求2、红黑树的设计想要兼容map和set我们依旧需要红黑树的模板有两个类型来控制和满足上层对下层的需求实现代码templateclass K, class T
class RBTree
{typedef RBTreeNodeT Node;
public://.......
private:Node* _root;
};注这里的Node我们不想让外部直接获取使用我们typedef在private域中解释为了兼容set和map对于第一个参数我们是用来比较的key类型第二个参数是用来储存数据的类型这里我们对红黑树第二个模板参数进行灵活传参可能是键值key也可能是pairkey,value对于set传入底层红黑树的模板参数就是key和key对于map传入底层红黑树的模板参数就是key和pairkey,value注对于set来说第二个参数有点多余但是对于map来说因为map的接口当中有些是只要求给出键值key用来比较的如find()和erase(),如果只有一个参数传入pairkey,value类型但是只能得到第一个key类型的值无法获得key的类型不能实现模板函数3、取值仿函数的使用我们在设计树节点之后达到了对于不同容器存入不同类型的效果但是真实在实现时在插入或者删除时我们需要要拿出节点中储存类型的数据进行比较分析对于set的T本身就是键值key直接用T进行比较即可但是对于map的储存类型是pairKey, Value我们需要取出pair的firstkey值进行比较这两种的都是取值比较但是需要的行为是不一样的由此我们还需要一个仿函数用来灵活取值比较对于不同容器我们需要不同的仿函数类型由此在红黑树的模板列表中还需要一个模板类型参数灵活控制传入的仿函数类型注仿函数就是使一个类的使用看上去像一个函数其实现就是类中实现一个operator()这个类就有了类似函数的行为就是一个仿函数类了红黑树框架templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public://...
private:Node* _root;
};map实现框架namespace cole
{templateclass K, class Vclass map{struct MapOfKey{const K operator()(const pairK, V kv)
{return kv.first;}};public://...private:RBTreeK, pairconst K, V, MapOfKey _t;};
}set实现框架namespace cole
{templateclass Kclass set{struct SetOfKey{const K operator()(const K key)
{return key;}};public://...private:RBTreeK, K, SetOfKey _t;};
}仿函数使用示例Node* Find(const K key)
{KeyOfT kot;Node* cur _root;while (cur){if (kot(cur-_kv.first) key){cur cur-_left;}else if (kot(cur-_kv.first) key){cur cur-_right;}else{return cur;}}return nullptr;
}二、红黑树的迭代器迭代器本质上是指针的一个封装的类其底层就是指针好处是可以方便遍历是数据结构的底层实现与用户透明对于string,vector,list等容器其本身的结构上是比较简单的迭代器的实现也很简单但是对于二叉树结构的红黑树来说需要考虑很多的问题1、begin()与end()STL明确规定begin()与end()代表的是一段前闭后开的区间对红黑树进行中序遍历后可以得到一个有序的序列因此begin()可以放在红黑树中最小节点(即最左侧节点)的位置end()放在最大节点(最右侧节点)的下一个位置即nullptr示图2、operator()与operator–()找到begin()和end()之后要遍历红黑树最主要的还是能找到要遍历的下一个节点红黑树的中序遍历是有序的也就是说当一个结点的正向迭代器进行操作后应该根据红黑树中序遍历的序列找到当前结点的下一个结点实现逻辑对于中遍历到当前节点来说该节点的左子树应该是已经被遍历过了所以只需要考虑右子树如果当前结点的右子树不为空则操作后应该找到其右子树当中的最左结点如果当前结点的右子树为空则该子树已经被遍历完了则操作后应该在该结点的祖先结点中找到孩子不在父亲右的祖先说明如果是孩子节点在父亲的左说明父亲的右节点没有遍历如果孩子在父亲的右说明以父亲节点为根的子树已经遍历完了还需要继续向上找如果一直向上遍历到nullptr说明整颗树已经遍历完了end()返回的就是nullptr注怎么看该节点的右节点遍历过没有这里需要一个指针记录上一次经过的节点地址进行比较地址就行了实现代码Self operator()
{if (_node-_right)//右子节点存在{//找到右子树中最左节点Node* cur _node-_right;while (cur-_left){cur cur-_left;}_node cur;}else//右子节点不存在向上找{Node* cur _node;//记录走过的节点Node* parent _node-_parent;while (parent parent-_right cur){cur parent;parent parent-_parent;}_node parent;}return *this;
}注对于–来说可以参考的实现逻辑是完全相反的实现–代码Self operator--()
{
if (_node-_left)//左子节点存在{
//找左子树中的最右节点Node* cur _node-_left;
while (cur-_right){cur cur-_right;}_node cur;}
else//左子节点不存在{Node* cur _node;Node* parent _node-_parent;
while (parent parent-_left cur){cur parent;
parent parent-_parent;}_node parent;}
return *this;
}3、正反迭代器的实现对于正向迭代器与反向迭代器的区别就是begin()指向的位置不一样迭代器的和–的实现相反但本质上还是差不多的所以实现正向迭代器后我们可以直接使用适配器在正向迭代器的基础上对其接口进行封装达到反向迭代器的效果正向迭代器实现代码templateclass T, class Ref, class Ptr
struct _TreeIterator
{
//声明类型便于反向迭代器对类型的提取typedef Ref reference;typedef Ptr pointer;typedef RBTreeNodeT Node;typedef _TreeIteratorT, Ref, Ptr Self;Node* _node;_TreeIterator(Node* node):_node(node){}Ref operator*(){
return _node-_data;}Ptr operator-(){
return _node-_data;}bool operator(const Self it)const{
return _node it._node;}bool operator! (const Self it)const{
return _node ! it._node;}Self operator(){
if (_node-_right){Node* cur _node-_right;
while (cur-_left){cur cur-_left;}_node cur;}
else{Node* cur _node;Node* parent _node-_parent;
while (parent parent-_right cur){cur parent;
parent parent-_parent;}_node parent;}
return *this;}Self operator--(){
if (_node-_left){Node* cur _node-_left;
while (cur-_right){cur cur-_right;}_node cur;}
else{Node* cur _node;Node* parent _node-_parent;
while (parent parent-_left cur){cur parent;
parent parent-_parent;}_node parent;}return *this;}
};反向迭代器实现代码//适配器构造反向迭代器
templateclass Iterator
struct ReverseIterator
{
//类型未实例化无法取出里面的类型此时需要使用typename告诉编译器等实例化后再到类里面找对应的类型
typedef typename Iterator::reference Ref;
typedef typename Iterator::pointer Ptr;
typedef ReverseIteratorIterator Self;Iterator _it;ReverseIterator(Iterator it):_it(it){}//在正向迭代器接口上进行封装复用 Ref operator*(){
return *_it;}Ptr operator-(){
return _it.operator-();}bool operator(const Self it)const{
return it._it_it;}bool operator! (const Self it)const//两个const{
return _it ! it._it;}Self operator(){--_it;
return *this;}Self operator--(){_it;
return *this;}
};三、map和set的实现1、红黑树的实现具体实现代码//颜色
enum Colour
{RED,BLACK,
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;//T可以是key也可以是pairK,VColour _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef _TreeIteratorT, T, T* iterator;typedef _TreeIteratorT,const T, const T* const_iterator;typedef ReverseIteratoriterator reverse_iterator;typedef ReverseIteratorconst_iterator reverse_const_iterator;RBTree():_root(nullptr){}~RBTree(){_Destory(_root);}iterator begin(){Node* cur _root;
while (curcur-_left){cur cur-_left;}
return iterator(cur);}reverse_iterator rbegin(){Node* cur _root;
while (curcur-_right){cur cur-_right;}
return reverse_iterator(iterator(cur));}reverse_iterator rend(){
return reverse_iterator(iterator(nullptr));}iterator end(){
return iterator(nullptr);}Node* Find(const K key){KeyOfT kot;Node* cur _root;
while (cur){
if (kot(cur-_kv.first) key){cur cur-_left;}
else if (kot(cur-_kv.first) key){cur cur-_right;}
else{
return cur;}}
return 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* cur _root, * parent _root;
while (cur){
if (kot(cur-_data) kot(data)){
parent cur;cur cur-_left;}
else if (kot(cur-_data) kot(data)){
parent cur;cur cur-_right;}
else{
return make_pair(iterator(cur), false);}}//创建链接节点cur new Node(data);Node* newnode cur;
if (kot(parent-_data) kot(data)){
parent-_left cur;}
else{
parent-_right cur;}cur-_parent parent;//父节点存在且为红则需要调整不能存在连续的红色节点
while (parent parent-_col RED){
//此时当前节点一定有祖父节点Node* granparent parent-_parent;
//具体调整情况主要看叔叔节点
//分左右讨论
if (parent granparent-_left){Node* uncle granparent-_right;
//情况1叔叔节点存在且为红
if (uncle uncle-_col RED){
//修改颜色继续向上检查granparent-_col RED;
parent-_col uncle-_col BLACK;cur granparent;
parent cur-_parent;}
else//情况2和3叔叔节点不存在 或者存在且为黑{
//单旋(三代节点为斜线)变色
if (cur parent-_left){RotateR(granparent);granparent-_col RED;
parent-_col BLACK;}
else//双旋(三代节点为折线)变色{RotateL(parent);RotateR(granparent);cur-_col BLACK;granparent-_col RED;}
//旋转后不需再向上调整了
break;}}
else//parentgrandparent-right{Node* uncle granparent-_left;
if (uncle uncle-_col RED){
parent-_col uncle-_col BLACK;granparent-_col RED;cur granparent;
parent cur-_parent;}
else{
if (cur parent-_right){RotateL(granparent);parent-_col BLACK;granparent-_col RED;}
else{RotateR(parent);RotateL(granparent);cur-_col BLACK;granparent-_col RED;}
break;}}}//确保根节点为黑_root-_col BLACK;
return make_pair(iterator(newnode), true);}bool IsRBTree(){
if (_root nullptr){
return true;}if (_root-_col RED){cout 根节点为红色 endl;
return false;}int Blacknum 0;Node* cur _root;
while (cur){
if (cur-_col BLACK)Blacknum;cur cur-_left;}int i 0;
return _IsRBTree(_root, Blacknum, i);}private:void _Destory(Node* root){
if (root nullptr)
return;_Destory(root-_left);_Destory(root-_right);delete root;root nullptr;}bool _IsRBTree(Node* root, int blacknum, int count){
if (root nullptr){
if (blacknum count)
return true;cout 各路径上黑色节点个数不同 endl;
return false;}if (root-_col RED root-_parent-_col RED){cout 存在连续红色节点 endl;
return false;}if (root-_col BLACK)count;return _IsRBTree(root-_left, blacknum, count) _IsRBTree(root-_right, blacknum, count);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;Node* parentP parent-_parent;parent-_right subRL;
if (subRL){subRL-_parent parent;}subR-_left parent;
parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}
else{subR-_parent parentP;
if (parentP-_left parent){parentP-_left subR;}
else{parentP-_right subR;}}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* parentP parent-_parent;parent-_left subLR;
if (subLR){subLR-_parent parent;}subL-_right parent;
parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}
else{subL-_parent parentP;
if (parentP-_left parent){parentP-_left subL;}
else{parentP-_right subL;}}}private:Node* _root;
};2、map的封装具体实现代码namespace cole
{
templateclass K, class V
class map{
struct MapOfKey{
const K operator()(const pairK, V kv)
{
return kv.first;}};
public:
typedef typename RBTreeK, pairconst K, V, MapOfKey::iterator iterator;
typedef typename RBTreeK, pairconst K, V, MapOfKey::reverse_iterator reverse_iterator;iterator begin()
{
return _t.begin();}iterator end()
{
return _t.end();}reverse_iterator rbegin()
{
return _t.rbegin();}reverse_iterator rend()
{
return _t.rend();}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;}iterator find(const K key)
{
return _t.Find(key);}private:RBTreeK, pairconst K, V, MapOfKey _t;};
}3、set的封装具体实现代码namespace cole
{
templateclass K
class set{
struct SetOfKey{
const K operator()(const K key)
{
return key;}};
public:
typedef typename RBTreeK,K, SetOfKey::iterator iterator;
typedef typename RBTreeK,K, SetOfKey::reverse_iterator reverse_iterator;iterator begin()
{
return _t.begin();}iterator end()
{
return _t.end();}reverse_iterator rbegin()
{
return _t.rbegin();}reverse_iterator rend()
{
return _t.rend();}pairiterator, bool insert(const K key){
return _t.Insert(key);}iterator find(const K key)
{
return _t.Find(key);}private:RBTreeK, K, SetOfKey _t;};
}*声明本文于网络整理版权归原作者所有如来源信息有误或侵犯权益请联系我们删除或授权事宜。戳“阅读原文”我们一起进步
