钓鱼网站开发系列教程,访问wordpress的xmlrpc.php,网站推广seo蜘蛛屯优化排名,网站制作公司站建设目录
一、底层原理
二、红黑树的节点
三、仿函数
四、迭代器
4.1、迭代器的定义#xff1a;
4.2、*:解引用操作
4.3、-:成员访问操作符
4.4、!、
4.5、迭代器的#xff1a;
4.6、迭代器的--
五、Map
六、Set
七、红黑树源码 一、底层原理
我们要知道#…目录
一、底层原理
二、红黑树的节点
三、仿函数
四、迭代器
4.1、迭代器的定义
4.2、*:解引用操作
4.3、-:成员访问操作符
4.4、!、
4.5、迭代器的
4.6、迭代器的--
五、Map
六、Set
七、红黑树源码 一、底层原理
我们要知道Map和Set底层是用红黑树封装的。
红黑树的底层是KV结构
RBTree是通过传入的Value的值来判断类型也就是一棵泛型的RBTree通过不同的实例化实现出了Map和Set
对于map:传key对于set:传pair 为了让我们的红黑树能够识别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的时候结点当中存储的就是Key和Value构成的键值对,所以红黑树的结点定义如下,由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()。
map:
namespace lyl
{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;};set:
namespace lyl
{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;}
}四、迭代器
4.1、迭代器的定义
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){}
}4.2、*:解引用操作
返回对应结点数据的引用:
Ref operator*(){return _node-_data;}4.3、-:成员访问操作符
返回结点数据的引用
Ptr operator-(){return _node-_data;}4.4、!、 bool operator !(const Self s) const{return _node ! s._node;}bool operator (const Self s) const{return _node s._node;}4.5、迭代器的
一个结点的正向迭代器进行操作后根据红黑树中序(左、根、右)找到当前结点的下一个结点中序的第一个节点是最左迭代器的怎么去找
如果节点的右子树不为空就是找右子树的最左节点
如果节点的右子树为空就是找祖先孩子是父亲的左的那个祖先 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;}4.6、迭代器的--
对于–如果是根–就是左子树找到左子树最大的那一个最右节点
如果节点的左子树不为空--找左子树最右的节点
如果节点的左子树为空--找祖先孩子是父亲的右的祖先 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;}4.7、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);}
}五、Map
同样是套用上底层红黑树的接口不过map的实现有一个很重要的地方那就是[]的实现
#pragma once
#include RBTree.h
namespace lyl
{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;}}
}六、Set
#pragma once
#includeRBTree.hnamespace bit
{templateclass Kclass set{public:struct SetKeyOfT{const K operator()(const K key){return key;}};typedef typename RBTreeK, K, SetKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pairiterator, bool insert(const K key){return _t.Insert(key);}private:RBTreeK, K, SetKeyOfT _t;};
}
七、红黑树源码
#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;
};
