建设网站的模板,哪些网站可以接任务做兼职,战略网页游戏开服表,北京网站建设公司排行榜在STL的源代码中#xff0c;map和set的底层原理都是红黑树。但这颗红黑树跟我们单独写的红黑树不一样#xff0c;它需要改造一下#xff1a;
改造红黑树
节点的定义
因为map和set的底层都是红黑树。而且map是拥有键值对pairK,V的#xff0c;而set是没有键值对map和set的底层原理都是红黑树。但这颗红黑树跟我们单独写的红黑树不一样它需要改造一下
改造红黑树
节点的定义
因为map和set的底层都是红黑树。而且map是拥有键值对pairK,V的而set是没有键值对只有一个K。因此为了应对这两种不同的情况就使用模板参数T。
当map使用这棵红黑树的时候T就会变成pairK,V。当set使用时T就会变成K。
//使用枚举
enum Colour
{RED,BLACK,
};// 如果是map则为pairK, V; 如果是set则为k
//因此对于节点来说需要再套一层模板来应付两种不同的情况
templateclass T
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) //默认是红色{}
};
改版的红黑树的插入操作
红黑树的模板参数有三个K、valueType和仿函数KeyOfValue。
K是key的类型ValueTyp要么是set的K要么是map的pairconst K,V。
而仿函数是为了比较节点的值的大小的因为官方库中键值对pairK,V比较大小的方法是比较first和second。但是红黑树中新增节点是通过比较first因此我们需要自己写一个仿函数用于单独比较first。
//跟节点的定义一样
//因为关联式容器中存储的是key, value的键值对因此
// k为key的类型
// ValueType: 如果是map则为pairK, V; 如果是set则为k。如下
// map-RBTreeK,pairconst K,V,MapKeyOfT _t;
// set-RBTreeK,K,SetKeyOfT _t
//
// KeyOfValue: 通过value来获取key的一个仿函数类。其作用就是用于比较。
templateclass K,class ValueType,class KeyOfValue
class RBTree
{typedef RBTreeNodeValueType Node;
public: //迭代器typedef __RBTreeIteratorValueType iterator;//......
private:Node* _root nullptr;
};迭代器
红黑树的迭代器不能使用原生指针因为它是一棵树节点地址不连续因此需要封装起来。
//set的Kmap的pairK,V
templateclass ValueType
struct __RBTreeIterator
{typedef RBTreeNodeValueType Node;typedef __RBTreeIteratorValueType Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}
};
1.operator()
红黑树是二叉搜索树采用的是中序遍历的方法。因此迭代器每次向前走是按照中序遍历的顺序走的。
因此对于往前有两种情况第一种情况是当前节点的右孩子不为空那么按照中序遍历的顺序下一个节点便是右子树的最小值。第二种情况是当前节点的右孩子为空这种情况下又分两种情况①当前节点是父节点的左孩子那么下一个节点肯定是当前节点的父节点。②当前节点是父节点的右孩子这意味着当前节点的父节点也被遍历了又没有右孩子节点只能往上找了找的节点是祖先节点而这个祖先节点是特征是孩子节点是它的左节点。 //左 根 右Self operator(){//当当前节点的右子树不为空根据中序遍历的顺序那就找右子树最小值if (_node-_right){Node* minValue _node-_right;while (minValue-_left){minValue minValue-_left;}//找到最小值的节点后更新节点_node minValue;}else //当当前节的的右子树为空说明它是叶子节点。此时需要判断情况{//判断当前节点是父亲节点的左孩子还是右孩子//第一种情况如果是curparent-_right即当前节点是父节点的右孩子的话就//去找祖先节点这个祖先节点的特征孩子节点是它的左节点//第二种情况当前节点是父亲节点的左孩子那么下一个节点就是父亲节点了Node* cur _node;//定义父亲节点。Node* parent cur-_parent;//如果当前节点不是父亲的右孩子并且父亲是不存在那么就是根节点或者是左孩子节点了//那就不进入循环。while (parent cur parent-_right){//如果是那就往上找到下一个节点。cur cur-_parent;parent parent-_parent;}//更新节点_node parent;}return *this;}
2.begin()和end();
迭代器的begin和end是左闭右开的区间。那么begin就是最左的节点end则是最右节点的下一个节点。这里不使用哨兵来作为end节点。
对于begin就找到最左的节点就好啦
iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}
对于end这里选择直接置为空传入匿名对象。这样子做的话当遍历到最后一个节点后它会往回遍历一直到了根节点的上面一个节点也就是空。此时就会结束循环。 iterator end(){return iterator(nullptr);}
迭代器整体代码
templateclass ValueType
struct __RBTreeIterator
{typedef RBTreeNodeValueType Node;typedef __RBTreeIteratorValueType Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}ValueType operator*(){return _node-_data;}ValueType* operator-(){return _node-_data;}Self operator(){if (_node-_right){Node* minValue _node-_right;while (minValue-_left){minValue minValue-_left;}_node minValue;}else {Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}bool operator!(const Self s){return _node ! s._node;}
};
set的模拟实现
仿函数
由于set只有Key因此就让仿函数直接返回Key值就可以了。
templateclass Kclass set{//set的仿函数返回set的K值struct SetKeyOfValue{const K operator()(const K key){return key;}};
整体都是复用了红黑树的接口并没有什么技术含量问题都在红黑树中解决了。
namespace my_set
{templateclass Kclass set{//set的仿函数返回set的K值struct SetKeyOfValue{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, K, SetKeyOfValue::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const K key){return _t.Insert(key);}private:RBTreeK, K, SetKeyOfValue _t;};
map的模拟实现
仿函数
由于比较的是first因此我们返回键值对中的first即可。
templateclass K, class Vclass map{struct MapKeyOfValue{const K operator()(const pairconst K, V kv){return kv.first;}};
整体代码一样的都是复用了红黑树的接口并没有什么技术含量
namespace my_map
{templateclass K, class Vclass map{struct MapKeyOfValue{const K operator()(const pairconst K, V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfValue::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const pairconst K, V kv){return _t.Insert(kv);}private:RBTreeK, pairconst K, V, MapKeyOfValue _t;};
最后是红黑树的整体代码这段代码跟单独写的红黑树的代码差不多就是在新增节点的操作那里比较节点的值使用的是仿函数。
#pragma once//使用枚举
enum Colour
{RED,BLACK,
};// 如果是map则为pairK, V; 如果是set则为k
//因此对于节点来说需要再套一层模板来应付两种不同的情况
templateclass T
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) //默认是红色{}
};templateclass ValueType
struct __RBTreeIterator
{typedef RBTreeNodeValueType Node;typedef __RBTreeIteratorValueType Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}ValueType operator*(){return _node-_data;}ValueType* operator-(){return _node-_data;}//左 根 右Self operator(){//当当前节点的右子树不为空根据中序遍历的顺序那就找右子树最小值if (_node-_right){Node* minValue _node-_right;while (minValue-_left){minValue minValue-_left;}//找到最小值的节点后更新节点_node minValue;}else //当当前节的的右子树为空说明它是叶子节点。此时需要判断情况{//判断当前节点是父亲节点的左孩子还是右孩子//第一种情况如果是curparent-_right即当前节点是父节点的右孩子的话就//去找祖先节点这个祖先节点的特征孩子节点是它的左节点//第二种情况当前节点是父亲节点的左孩子那么下一个节点就是父亲节点了Node* cur _node;//定义父亲节点。Node* parent cur-_parent;//如果当前节点不是父亲的右孩子并且父亲是不存在那么就是根节点或者是左孩子节点了//那就不进入循环。while (parent cur parent-_right){//如果是那就往上找到下一个节点。cur cur-_parent;parent parent-_parent;}//更新节点_node parent;}return *this;}bool operator!(const Self s){return _node ! s._node;}
};
//跟节点的定义一样
//因为关联式容器中存储的是key, value的键值对因此
// k为key的类型
// ValueType: 如果是map则为pairK, V; 如果是set则为k。如下
// map-RBTreeK,pairconst K,V,MapKeyOfT _t;
// set-RBTreeK,K,SetKeyOfT _t
//
// KeyOfValue: 通过value来获取key的一个仿函数类。其作用就是用于比较。
templateclass K,class ValueType,class KeyOfValue
class RBTree
{typedef RBTreeNodeValueType Node;
public:typedef __RBTreeIteratorValueType iterator;iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}bool Insert(const ValueType data){//先按二叉搜索树的规矩来创建一棵二叉搜索树if (_root nullptr){_root new Node(data);//因为红黑树的根节点是黑色的_root-_col BLACK;return true;}KeyOfValue 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;}}cur new Node(data);cur-_col RED;//多写一步防止写错代码。if (kot(parent-_data) kot(data)){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//创建完二叉搜索树//开始创建红黑树使用颜色来判断是否需要调整//循环往上走循环条件当走到的parent不为空并且parent是红色的//即我们列举是三种情况parent都是红的就需要重新调整//如果parent是黑色的那就不需要了。直接就是一棵红黑树,不进入循环while (parent parent-_col RED){//保存祖先节点即g节点Node* grandfther parent-_parent;//判断父节点是在祖先节点的哪边if (parent grandfther-_left){//父节点在左边那么叔叔节点就在右边Node* uncle grandfther-_right;//情况一uncle存在且为红。改变颜色即可if (uncle uncle-_col RED){//变色。parent-_col uncle-_col BLACK;grandfther-_col RED;//往上走cur grandfther;parent cur-_parent;}else //uncle不存在 或者 存在但是黑色{//情况二 p是g的左孩子cur是p的左孩子以g为轴右单旋if (cur parent-_left){//右单旋RotateR(grandfther);//变色 右单旋后parent为根节点变黑色。cur和g节点为红色parent-_col BLACK;grandfther-_col RED;}else //情况三 p是g的左孩子cur是p的右孩子.{//先以p为轴左旋转RotateL(parent);//变成情况二再以g为轴右单旋RotateR(grandfther);//变色 cur变成根节点为黑色。p和g是红色cur-_col BLACK;grandfther-_col RED;}break;}}else //parent是在grandfther的右边{//叔叔节点就在祖先节点的左边Node* uncle grandfther-_left;//情况一uncle存在且为红。改变颜色即可if (uncle uncle-_col RED){//变色。parent-_col uncle-_col BLACK;grandfther-_col RED;//往上走cur grandfther;parent cur-_parent;}else //uncle不存在 或者 存在但是黑色{//情况二 p是g的右孩子cur是p的右孩子。if (cur parent-_right){//左单旋RotateL(grandfther);//变色 右单旋后parent为根节点变黑色。cur和g节点为红色parent-_col BLACK;grandfther-_col RED;}else //情况三 p是g的右孩子cur是p的左孩子.{//先以p为轴右旋转RotateR(parent);//变成情况二再以g为轴左单旋RotateL(grandfther);//变色 cur变成根节点为黑色。p和g是红色cur-_col BLACK;grandfther-_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;subL-_right parent;parent-_parent subL;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);std::cout root-_kv.first : root-_kv.second std::endl;_Inorder(root-_right);}bool Check(Node* root, int blackNum, const 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;
};
