网站制作 文案,外贸跟单的流程,房产类网站制作商,新媒体营销思维我们之前学的map和set在stl源码中都是用红黑树封装实现的#xff0c;当然#xff0c;我们也可以模拟来实现一下。在实现之前#xff0c;我们也可以看一下stl源码是如何实现的。我们上篇博客写的红黑树里面只是一个pair对象#xff0c;这对于set来说显然是不合适的#xff… 我们之前学的map和set在stl源码中都是用红黑树封装实现的当然我们也可以模拟来实现一下。在实现之前我们也可以看一下stl源码是如何实现的。我们上篇博客写的红黑树里面只是一个pair对象这对于set来说显然是不合适的所以要想让一个红黑树的代码同时支持map和set就用上模板就可以了 我们来看看stl源码中是如何实现的 前两个模板参数是两个类型就是我们要在set或map中放入什么 set不是只需要放入一个吗所以set在传参数的时候是这么传的 它的前两个传的全是Key它这么实现还是为了兼容mapmap传的是什么呢我们再来看一下 传的一个是Key一个是pair类的对象。那pair中不是已经有Key了吗为什么还要传Key呢因为一个最简单的原因之一find函数的参数是Key。 那么看第三个模板参数keyofvalue传这个类型是为了从value中找到key因为我们树这个类传给节点类的时候只传了value如下图 因为map中value是一个pair对象set中value就是key它们的获取方式不一样所以传这个参数是为了实现仿函数来取出key值用于比较。 那么了解了这个大体的结构之后下一个就是要实现我们的迭代器了我们其实可以在红黑树中实现一个树形的迭代器然后map和set再封装一层就行了其实我们的迭代器就是一个类它用来实现类似于指针的一些操作所以我们就用指针来当作这个类的成员变量在这个类的基础上实现迭代器的功能。 在实现迭代器的时候最关键的一个函数就是重载这里迭代器肯定是按中序因为这样才有意义有顺序那么我们如何通过一个节点找到它的中序遍历的下一个节点呢这其实是有规律的。比如我们看这样一颗红黑树 首先我们中序遍历是左子树 根 右子树 1.假设这个节点有右子树那么这个节点之后就是它的右子树的中序的第一个节点就是右子树中最左边的节点 2.假设这个节点没有右子树那么走完这个节点以后以这个节点为根的树就走完了假如它是它父亲的左孩子那么就该走它的父亲如果它是它父亲的右孩子那么它父亲也走完了就按照此规律走它的爷爷。 有了这个理论基础我们就可以来实现了。 同样--的话跟是完全相反的反过来的遍历顺序就是右子树根左子树然后我们再分别去看这棵树有没有左子树如果有那就走左子树中第一个该走的节点就是左子树中最右节点如果没有那就看它是它父亲的什么节点一直往上找直到找到它是它父亲的右子树的节点它父亲就是下一个要遍历的节点。 下面还有一些细节问题比如说把迭代器写成模板 那么只需要传不同的类型就可以实现const或非const的迭代器 我们const对象要用const版本的迭代器因为const对象用普通版本的属于权限放大所以我们要设计const版本的迭代器 我们也要对红黑树的插入函数进行修改原来插入函数返回一个bool值但是库中应该是返回一个pair对象其中first是个迭代器second是个bool值表示是否新插入 看到这样的代码的时候这个typename表示后面是一个类型名因为static静态成员也可以指明类域然后去访问 另外我们这里为什么传const K呢因为就算是普通的迭代器我们也不希望key值改变因为map的key值改了就不满足二叉搜索树了 这是如何使用const_iterator首先s就是一个普通的map对象就调用普通版本的begin() 调完之后它返回一个iterator而我们用的const_iterator去接收的所以要写个构造函数用普通迭代器构造出const迭代器 那么下面我们再整体的来展示一下红黑树和map set之间的封装关系 这就是如何用红黑树封装出map和set下面是所有的代码 RBTree.h
#includeiostream
#includeassert.h
using namespace std;enum col {RED,BLACK
};
templateclass T
struct RBTreeNode {RBTreeNode(const T data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}RBTreeNode* _left nullptr;RBTreeNode* _right nullptr;RBTreeNode* _parent nullptr;T _data;col _colRED;
};
templateclass T,class Ptr,class Ref
struct RBTreeIterator {typedef RBTreeNodeT Node;typedef RBTreeIteratorT,Ptr,Ref self;typedef RBTreeIteratorT, T*, T iterator;typedef RBTreeIteratorT, const T*, const T const_iterator;Node* _node;RBTreeIterator(const iterator it):_node(it._node) {}RBTreeIterator(Node*node):_node(node){}Ref operator*() {return _node-_data;}Ptr operator-() {return _node-_data;}bool operator(const selfs) {return _node s._node;}bool operator!(const self s) {return _node ! s._node;}self operator() {if (_node nullptr) {cout end()不能 endl;assert(false);}if (_node-_right) {//有右子树那么这个节点之后就是它的右子树的中序的第一个节点就是右子树中最左边的节点_node _node-_right;while (_node-_left ! nullptr)_node _node-_left;return *this;}else {//没有右子树直到找到孩子是父亲左子树的那个父亲节点Node* parent _node-_parent;while (parent _node ! parent-_left) {parent parent-_parent;_node _node-_parent;}_node parent;return *this;}}self operator--() {if (_node-_left) {_node _node-_left;while (_node-_right ! nullptr)_node _node-_right;return *this;}else {Node* parent _node-_parent;while (parent _node ! parent-_right) {parent parent-_parent;_node _node-_parent;}_node parent;return *this;}}
};templateclass K,class V,class Keyofvalue
class RBTree {typedef RBTreeNodeV Node;
public:typedef RBTreeIteratorV,V*,V iterator;typedef RBTreeIteratorV,const V*,const V const_iterator;const_iterator begin()const {Node* cur _root;while (cur cur-_left)cur cur-_left;return const_iterator(cur);}iterator begin() {Node* cur _root;while (curcur-_left)cur cur-_left;return iterator(cur);}const_iterator end()const {return const_iterator(nullptr);}iterator end() {return iterator(nullptr);}iterator Find(const K key) {Keyofvalue kov;Node* cur _root;while (cur) {if (kov(cur-_data) key) {cur cur-_right;}else if (kov(cur-_data) key) {cur cur-_left;}else {return iterator(cur);}}return end();}pairiterator,bool insert(const V data) {if (_root nullptr) {_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root),true);}Node* cur _root;Node* parent nullptr;Keyofvalue kov;while (cur) {if (kov(cur-_data) kov(data)) {parent cur;cur cur-_right;}else if (kov(cur-_data) kov(data)) {parent cur;cur cur-_left;}else return make_pair(iterator(cur),false);}cur new Node(data);Node* ret cur;if (kov(parent-_data) kov(cur-_data)) {parent-_right cur;cur-_parent parent;}else {parent-_left cur;cur-_parent parent;}Node* c cur;Node* p cur-_parent;Node* g p-_parent;Node* u nullptr;while (p p-_col RED) {if (p g-_left)u g-_right;else u g-_left;if (u nullptr || u-_col BLACK) {if (p g-_left c p-_left) {RotateR(g);p-_col BLACK;g-_col RED;}else if (p g-_right c p-_right) {RotateL(g);p-_col BLACK;g-_col RED;}else if (p g-_left c p-_right) {RotateL(p);RotateR(g);c-_col BLACK;g-_col RED;}else if (p g-_right c p-_left) {RotateR(p);RotateL(g);c-_col BLACK;g-_col RED;}else assert(false);break;}else if (u-_col RED) {p-_col BLACK;u-_col BLACK;g-_col RED;if (g _root) {g-_col BLACK;break;}else {c g;p c-_parent;g p-_parent;}}else assert(false);}return make_pair(iterator(ret),true);}void RotateL(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;Node* ppnode parent-_parent;if (subRL)subRL-_parent parent;parent-_right subRL;subR-_left parent;parent-_parent subR;if (parent _root) {_root subR;subR-_parent nullptr;}else {subR-_parent ppnode;if (ppnode-_left parent)ppnode-_left subR;else ppnode-_right subR;}}void RotateR(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;Node* ppnode parent-_parent;if (subLR)subLR-_parent parent;parent-_left subLR;subL-_right parent;parent-_parent subL;if (parent _root) {_root subL;subL-_parent nullptr;}else {subL-_parent ppnode;if (ppnode-_left parent)ppnode-_left subL;else ppnode-_right subL;}}Node* getroot() {return _root;}private:Node* _root nullptr;
};
MySet.h namespace jxh {templateclass Tclass set {typedef RBTreeNodeT Node;struct keyofvalue {const T operator()(const Tkey) {return key;}};void _inorder(Node* root) {if (root nullptr)return;_inorder(root-_left);cout root-_data endl;_inorder(root-_right);}public:typedef typename RBTreeT, const T, keyofvalue::iterator iterator;typedef typename RBTreeT, const T, keyofvalue::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 T key){return _t.insert(key);}iterator find(const T key){return _t.find(key);}void inorder() {_inorder(_t.getroot());}private:RBTreeT,const T,keyofvalue _t;};
MyMap.h
namespace jxh {templateclass K,class Vclass map {typedef RBTreeNodepairK,V Node;struct keyofvalue {const K operator()(const pairK,V kv) {return kv.first;}};void _inorder(Node* root) {if (root nullptr)return;_inorder(root-_left);cout root-_data.first root-_data.second endl;_inorder(root-_right);}public://typedef RBTreeIteratorpairK,V iterator;typedef typename RBTreeK, pairconst K, V, keyofvalue::iterator iterator;typedef typename RBTreeK, pairconst K, V, keyofvalue::const_iterator const_iterator;const_iterator begin()const {return _t.begin();}const_iterator end() const{return _t.end();}iterator begin() {return _t.begin();}iterator end() {return _t.end();}pairiterator, bool insert(const pairK, V kv){return _t.insert(kv);}iterator find(const K key){return _t.find(key);}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}void inorder() {_inorder(_t.getroot());}private:RBTreeK, pairconst K,V, keyofvalue _t;};
