蓬莱网站建设哪家专业,网站开发前端课程,做公司网站需要准备什么科目,wordpress 悬浮页文章目录一、前情回顾二、简化源码三、仿函数四、迭代器五、set的实现六、map的实现七、红黑树代码一、前情回顾
set 参数只有 key#xff0c;但是map除了key还有value。我们还是需要KV模型的红黑树的#xff1a;
#pragma once
#include iostream
#include ass…
文章目录一、前情回顾二、简化源码三、仿函数四、迭代器五、set的实现六、map的实现七、红黑树代码一、前情回顾
set 参数只有 key但是map除了key还有value。我们还是需要KV模型的红黑树的
#pragma once
#include iostream
#include assert.h
#include time.h
using namespace std;
enum Color
{RED,BLACK,
};
templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;RBTreeNode(const pairK,V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};templateclass K,class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}while (parent parent-_col RED){Node* grandfater parent-_parent;if (parent grandfater-_left){Node* uncle grandfater-_right;//情况一u存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;//向上调整cur grandfater;parent cur-_parent;}else{//情况2if (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}//情况3else{// g// p// c RotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else//parentgrandfater-_right{Node* uncle grandfater-_left;//情况1u存在且为红色if (uncle uncle-_col RED){uncle-_col parent-_col BLACK;grandfater-_col RED;//向上调整cur grandfater;parent cur-_parent;}else{//情况2u不存在/u存在为黑色//g// p// cif (cur parent-_right){RotateL(grandfater);grandfater-_col RED;parent-_col BLACK;}//情况3// g// p// celse{RotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}//根变黑_root-_col BLACK;return true;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{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;parent-_parent subL;subL-_right parent;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);}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}bool Check(Node*root,int blackNum,int ref){if (root nullptr){//cout blackNum endl;if (blackNum ! ref){cout 违反规则本条路径的黑色结点的数量根最左路径不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续的红色结点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left,blackNum,ref) Check(root-_right,blackNum,ref);}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:Node* _root nullptr;
};二、简化源码
翻开源码一看
RBTree的结构源码是KV结构的红黑树
RBTree是通过传入的Value的值来判断类型也就是一棵泛型的RBTree通过不同的实例化实现出了Map和Set
对于map:传key对于set:传pair map的结构简化源码 set的结构简化源码 为了让我们的红黑树能够识别set与map我们增加一个模板参数T
templateclass K, class T
class RBTree对于T模板参数可能是键值Key也可能是由Key和Value共同构成的键值对。
如果是set容器那么它传入底层红黑树的模板参数就是Key和Key
templateclass K
class set
{private:RBTreeK,K _t;
};如果是map容器传入底层红黑树的模板参数就是Key和Key和value的键值对
class map
{
private:RBTreeK, pairconst K,V _t;
};通过上面我们可以知道对于set和map的区别我们只要通过第二个模板参数就能进行区分那是不是第一个模板参数就没有意义了呢 对于insert(const Valuev)来说需要放入存入的值确实是这个样子的插入的值是value对于set就是key对于map就是pair。 但是对于find(const Keykey)来说查找的参数不是value找的不是pair而是Key对于map容器来说就不行了。 **红黑树的节点**set容器K和T都是键值Key; map容器K是键值KeyT由Key和Value构成的键值对但是底层红黑树并不知道上层容器到底是map还是set因此红黑树的结点当中直接存储T就行了如果是set的时候结点当中存储的是键值Key如果是map的时候结点当中存储的就是键值对,所以红黑树的结点定义如下,由T类型来决定红黑树存的是key还是pair
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){}
};三、仿函数
这里存在一个问题插入的时候data的大小如何去进行比较我们并不知道是什么类型是key还是pair的比较而我们刚开始kv结构就直接用kv.first去比较了。 对于set是Key可以比较 对于map是pair那我们要取其中的first来比较但是pair的大小并不是直接按照first去进行比较的而我们只需要按照first去进行比较 由于底层的红黑树不知道传的是map还是set容器当需要进行两个结点键值的比较时底层红黑树传入的仿函数来获取键值Key进行两个结点键值的比较这个时候我们就需要仿函数了如果是set那就是用于返回T当中的键值Key,如果是map那就是用于返回pair的first
仿函数/函数对象也是类是一个类对象。仿函数要重载operator()。
namespace HWC
{templateclass K,class Vclass map{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public:private:RBTreeK, pairconst K,V,MapKeyOfT _t;};namespace HWC
{templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};private:RBTreeK,K,SetKeyOfT _t;};博主画了个图更加容易进行比对 查找过程此时就可以套上我们所写的仿函数对象去进行数据的大小比较了 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;}}四、迭代器
红黑树的正向迭代器是对结点指针进行了封装所以这里的正向迭代器就只有一个成员变量结点的指针并没有什么其他的地方迭代器的定义
templateclass T,class Ref,class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT,Ref,Ptr Self;typedef __RBTreeIteratorT, T, T* iterator;Node* _node;__RBTreeIterator(Node*node):_node(node){}//普通迭代器的时候它是拷贝构造//const迭代器的时候它是构造支持用普通迭代器构造const迭代器__RBTreeIterator(const iterator s):_node(s._node){}
}*:解引用操作返回对应结点数据的引用:
Ref operator*(){return _node-_data;}-:成员访问操作符,返回结点数据的引用
Ptr operator-(){return _node-_data;}!、:比较简单 bool operator !(const Self s) const{return _node ! s._node;}bool operator (const Self s) const{return _node s._node;}这里的迭代器重点是迭代器的:
一个结点的正向迭代器进行操作后根据红黑树中序(左、根、右)找到当前结点的下一个结点中序的第一个节点是最左迭代器的怎么去找
如果节点的右子树不为空就是找右子树的最左节点
如果节点的右子树为空就是找祖先孩子是父亲的左的那个祖先
代码实现✍ Self operator(){if (_node-_right){Node* min _node-_right;while (min-_left){min min-_left;}_node min;}else{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-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;while (parentcurparent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}不要忘记迭代器的两个核心成员begin()与end()
begin()返回中序左、根、右第一个结点的正向迭代器即最左节点返回的是最左节点,直接找最左节点即可
end()返回中序左、根、右最后一个结点下一个位置的正向迭代器这里直接用空指针
templateclass K, class T,class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef __RBTreeIteratorT iterator;iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}
}五、set的实现
通过前面底层红黑树的接口进行套用即可实现set的实现
值得注意的是typename:没有实例化的模板区分不了是静态变量还是类型typename告诉编译器是类型
#pragma once
#include RBTree.hnamespace hwc
{template class Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public://typename:没有实例化的模板区分不了是静态变量还是类型typename告诉编译器是类型typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;//key不可以修改typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;iterator begin() const {return _t.begin();}iterator end() const {return _t.end();}pairiterator,bool insert(const K key){//底层红黑树的iterator是普通迭代器pairtypename RBTreeK, K, SetKeyOfT::iterator, bool ret _t.Insert(key);return pairiterator, bool(ret.first, ret.second);//用普通迭代器构造const迭代器}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()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;}
}六、map的实现
同样是套用上底层红黑树的接口不过map的实现有一个很重要的地方那就是[]的实现
#pragma once
#include RBTree.h
namespace hwc
{templateclass K,class Vclass map{struct MapkeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public://typename:没有实例化的模板区分不了是静态变量还是类型typename告诉编译器是类型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-second;cout it-first : it-second endl;it;}cout endl;mapstring, int countMap;string arr[] { 苹果,西瓜,香蕉,苹果};for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}}
}七、红黑树代码
最后在这里送上源码
#pragma once#pragma once
#include iostream
#include assert.h
#include time.h
using namespace std;
enum Color
{RED,BLACK,
};
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){}
};templateclass T,class Ref,class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT,Ref,Ptr Self;typedef __RBTreeIteratorT, T, T* iterator;Node* _node;__RBTreeIterator(Node*node):_node(node){}//普通迭代器的时候它是拷贝构造//const迭代器的时候它是构造支持用普通迭代器构造const迭代器__RBTreeIterator(const iterator s):_node(s._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){if (_node-_right){Node* min _node-_right;while (min-_left){min min-_left;}_node min;}else{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-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;while (parentcurparent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}bool operator !(const Self s) const{return _node ! s._node;}bool operator (const Self s) const{return _node s._node;}
};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;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);}iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return 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;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* grandfater parent-_parent;if (parent grandfater-_left){Node* uncle grandfater-_right;//情况一u存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;//向上调整cur grandfater;parent cur-_parent;}else{//情况2if (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}//情况3else{// g// p// c RotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else//parentgrandfater-_right{Node* uncle grandfater-_left;//情况1u存在且为红色if (uncle uncle-_col RED){uncle-_col parent-_col BLACK;grandfater-_col RED;//向上调整cur grandfater;parent cur-_parent;}else{//情况2u不存在/u存在为黑色//g// p// cif (cur parent-_right){RotateL(grandfater);grandfater-_col RED;parent-_col BLACK;}//情况3// g// p// celse{RotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}//根变黑_root-_col BLACK;return make_pair(iterator(newnode),true);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{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;parent-_parent subL;subL-_right parent;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);}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}bool Check(Node* root, int blackNum, int ref){if (root nullptr){//cout blackNum endl;if (blackNum ! ref){cout 违反规则本条路径的黑色结点的数量根最左路径不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续的红色结点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);}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:Node* _root nullptr;
};本篇结束…
