网站运营顾问,网站开发视频教程迅雷下载,百度推广的五大优势,宝盒 网站目录
引言
红黑树迭代器实现
红黑树元素的插入
map模拟实现
set模拟实现 之前我们已经学习了map和set的基本使用#xff0c;但是因为map和set的底层都是用红黑树进行封装实现的#xff0c;上期我们已经学习了红黑树的模拟实现#xff0c;所以本期我们在红黑树模拟实现…目录
引言
红黑树迭代器实现
红黑树元素的插入
map模拟实现
set模拟实现 之前我们已经学习了map和set的基本使用但是因为map和set的底层都是用红黑树进行封装实现的上期我们已经学习了红黑树的模拟实现所以本期我们在红黑树模拟实现的基础之上对红黑树进行进一步封装实现map和set的模拟实现。
引言
首先大家思考一个问题map和set既然它们底层都是使用红黑树进行模拟实现的我们知道map是搜索二叉树中的kv模型set是搜索二叉树中的k模型那么两种模型难道使用两颗红黑树实现吗
当然不是map和set底层都是使用同一颗红黑树实现的我们通过使用模板达到这一目的这也体现了泛式编程的重要性。 我们对上期红黑树模拟实现的代码进行一点点改造基于下述代码来进行map和set的模拟实现。
红黑树迭代器实现
templateclass T,class Ref,class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, Ref, Ptr Self;RBTreeIterator(Node* node){_node node;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){Node* cur _node;if (cur-_right){cur cur-_right;while (cur-_left){cur cur-_left;}_node cur;}else{Node* parent cur-_parent;while (parent){if (cur parent-_left){_node parent;break;}else{while (parent cur parent-_right){cur parent;parent cur-_parent;}_node parent;break;}}}return *this;}Self operator--(){Node* cur _node;if (cur-_left){cur cur-_left;while (cur-_left){cur cur-_right;}_node cur;}else{Node* parent cur-_parent;while (parent){if (cur parent-_right){_node parent;break;}else{while (cur parent-_left){cur parent;parent cur-_parent;}_node parent;break;}}}return *this;}bool operator!(const Self s) const{return _node ! s._node;}bool operator(const Self s) const{return _node s._node;}Node* _node;
};上述代码有两个难点分别是迭代器的和迭代器的--。迭代器的和迭代器的--操作。 搜索二叉树的遍历和--操作一般是按照搜索二叉树的中序遍历为基础来进行进一步封装的。操作要去判断当前节点是否有右孩子--操作得先去判断是否有左孩子。 红黑树元素的插入
pairiterator,bool Insert(const T data){//如果当前红黑树为空则直接插入即可if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root),true);}//如果当前红黑树不为空就要先找到合适的位置然后进行节点的插入Node* cur _root;Node* parent _root-_parent;KeyOfT kot;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;cur-_col RED;cur-_parent parent;if ( kot(cur-_data) kot(parent-_data)){parent-_right cur;}else{parent-_left cur;}//调整平衡while (parent parent-_col RED){Node* grandfather parent-_parent;//1.叔叔节点都存在且都为红色节点就要进行颜色平衡if (parent grandfather-_right){Node* uncle grandfather-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else{Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}//强制性的让根节点为黑色符合红黑树的性质_root-_col BLACK;return make_pair(iterator(newnode),true);}在进行元素的插入时我们需要注意插入函数的返回值返回值是一个pair类型的对象first为迭代器插入成功返回新插入的元素所对应的节点的迭代器插入失败返回已经存在的元素所对应的节点的迭代器second为一个bool值插入成功为true插入失败为false。 map模拟实现
#pragma once
#includeRBTree.h
namespace yjd
{templateclass K,class V class map{public:struct MapKeyOfT{const K operator()(const pairK,V pair ){return pair.first;}};typedef typename RBTreeK, pairK, V, MapKeyOfT::iterator iterator;iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}iterator find(){return _rbt.Find();}pairiterator, bool insert(const pairK,V pair){return _rbt.Insert(pair);}V operator[](const K key){auto ret _rbt.Insert(make_pair(key, V()));return ret.first-second;}private:RBTreeK, pairK, V, MapKeyOfT _rbt;};void MapTest(){mapstring, string dict;dict.insert(make_pair(sort, 排序));dict.insert(make_pair(string, 字符串));dict.insert(make_pair(map, 地图));dict[left];dict[left] 左边;dict[map] 地图、映射;auto it dict.begin();while (it ! dict.end()){cout it-first : it-second endl;it;}cout endl;}} 通过代码不难发现map的模拟实现基本上还是套用红黑树的接口唯一需要注意的就是operator[]这个函数接口第一步是先转化为元素的插入第二步通过第一步的返回值来进一步访问插入元素的元素所对应的pair对象的second成员。简单来说operator[]的返回值就是括号内部key值所对应的pair对象的第二个second成员的引用。 在进行元素的插入时我们先要找到元素合适的位置然后再进行元素的插入但是因为map元素的大小我们是根据pair对象的first成员进行比较的所以我们使用到了仿函数MapKeyOfT获取到了pair对象的第一个first成员去进行比较。 运行截图如下。 运行结果符合预期。
set模拟实现
#pragma once
#includeRBTree.h
namespace yjd
{templateclass Kclass set{public:struct SetKeyOfT{const K operator()(const K key){return key;}};typedef typename RBTreeK, K, SetKeyOfT::iterator iterator;iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}iterator find(const K key){return _rbt.Find(key);}pairiterator, bool insert(const K k){return _rbt.Insert(k);}private:RBTreeK, K, SetKeyOfT _rbt;};void test_set(){setint s;s.insert(1);s.insert(4);s.insert(2);s.insert(24);s.insert(2);s.insert(12);s.insert(6);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}}} set的模拟实现也是基于红黑树的接口是对红黑树接口的进一步封装。相比较map的模拟实现更简单一些。 运行结果如下。 运行结果符合预期。
