四川省网站建设,网站开发怎样,商务型网站,加强学校网站建设的通知前言#xff1a; 前面#xff0c;我们学习了set和map的用法#xff0c;这两个容器可以完成查找#xff0c;排序等操作#xff0c;后来我们在学习过二叉搜索树的基础上又学习了两种特殊的二叉搜索树——AVL树和红黑树#xff0c;他们俩可以是效率进一步提高#xff0c;其…前言 前面我们学习了set和map的用法这两个容器可以完成查找排序等操作后来我们在学习过二叉搜索树的基础上又学习了两种特殊的二叉搜索树——AVL树和红黑树他们俩可以是效率进一步提高其实set和map的底层就是由红黑树封装而成的 所以本篇文章我们自己学习用红黑树封装set和map。用红黑树封装特别是用同一棵红黑树实现封装有一定的难度其中很多操作比如复用我们会第一次尝试所以大家请跟紧作者的脚步来。
目录
一如何复用同一棵红黑树
二红黑树的改造流程为封装做铺垫
1、结点的定义
2、模拟实现结点的比较大小
3、改造后的红黑树
4、map和set迭代器的模拟实现
4.1模版参数的构成
4.2begin()和end()的模拟实现
4.3operator* 和 operator-模拟实现
4.4 operator 和 operator--模拟实现
4.5 operator 和 operator!模拟实现
4.6迭代器代码详解 三封装map和set 一如何复用同一棵红黑树
前提疑问
在我们这所有的之前我们知道map和set这两个容器都是用红黑树来实现的那么就有了接下来的问题。
map和set都是用的同一棵红黑树复用的吗或者这两个容器各自使用一棵红黑树吗
其实在前言中我们就知道了根据STL的设计理念和泛型编程的理念我们不会冗余的写两课红黑树而是用一棵红黑树实现复用的效果。
我们调用STL库中的原码来看 我们发现
STL库中的原码也确实调用的同一棵红黑树他们实现的都是key_value模型
我们设set中存放结点的值是Kmap中存放的节点是pairkey,value键值对
对于set而言底层红黑树的模版就是RBTreeK, K对于map而言底层红黑树的模版就是RBTreeK, pairK, V 这时我们就有了另一个疑问两个模板参数的第一个Key不能省略掉吗
首先答案肯定是不能的那么原因又是什么呢
因为map的这个类中无论怎么省略都会有一个查找函数要单独用到Key 如果第一个Key删去了那么map和set的查找函数就没法统一实现了违背了我们一开始泛型编程的思想。 综上所述
map和set都是用了Key_value模型set中的K是KV也是Kmap中的K是KV是pairKV并且模板参数中第一个K都不能省 二红黑树的改造流程为封装做铺垫
1、结点的定义 这里由于set和map存放的结点一个是Key一个是pairKey,Value所以我们使用模版把存放的结点泛化。
2、模拟实现结点的比较大小
上述提到在模拟实现中map和set我们复用同一棵红黑树的时候都是用的是Kye_value的结构但是红黑树中的数据比较又是Key值的比较而现在我们用的则是pair的比较虽然编译上是可以通过但是真的就是我们所想要的吗
pair的比较大小 很显然这种比较规则不是我们所想要的并且map和set想要取到用来比较的数据是不同的。
为了取到我们想要的数据我们引入了仿函数
根据map和set的需求不同我们在红黑树中新引入了一个模板参数KeyOfT 引入KeyOfT模板参数后我们想要不同方式的比较方法只需要在set和map的封装中给出属于他们自己的比较仿函数。
map中的仿函数 set中的仿函数 使用方法 此时前面所说的仿函数的便利之处就体现出来了。
3、改造后的红黑树
具体代码
//红黑树的实现
//KeyOfT -- 支持取出T对象中key的仿函数
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;//构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的//迭代器中序遍历要找最左结点iterator Begin(){Node* subLeft _root;while (subLeft subLeft-_left){subLeft subLeft-_left;}//树的迭代器用结点的指针就可以构造return iterator(subLeft);}iterator End(){return iterator(nullptr);}const_iterator Begin() const{Node* subLeft _root;while (subLeft subLeft-_left){subLeft subLeft-_left;}//树的迭代器用结点的指针就可以构造return const_iterator(subLeft);}const_iterator End() const{return const_iterator(nullptr);}pairiterator, bool Insert(const T data){//1、搜索树的规则插入//2、看是否违反平衡规则如果违反就需要处理旋转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;}else{parent-_left cur;}//三叉链的链接 -- 链上父节点cur-_parent parent;//存在连续红色结点while (parent parent-_col RED){//理论而言祖父是一定存在的父亲存在且是红不可能是根根一定是黑的Node* grandfather parent-_parent;assert(grandfather);if (grandfather-_left parent){Node* uncle grandfather-_right;//情况一叔叔存在且为红if (uncle uncle-_col RED){//祖父和叔叔变成黑色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}//情况二叔叔不存在 or 叔叔存在且为黑else{//单旋// g// p// cif (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}//双旋// g// p// celse{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}//无论父亲和叔叔是左是右都是一样的//grandfather-_right parent;else{Node* uncle grandfather-_left;//情况一if (uncle uncle-_col RED){//祖父和叔叔变成黑色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}else{//单旋// g// p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}//双旋// g// p// celse{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}//父亲为空就出循环将根节点设置成黑色_root-_col BLACK;return make_pair(iterator(newnode), true);}
}插入Insert和寻找Find代码
Node* Find(const K key){Node* cur _root;KeyOfT kot;while (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return cur;}}return nullptr;}pairitertaor, bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(itertaor(_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(itertaor(cur), false);}}cur new Node(data);Node* newnode cur;if (kot(parent-_data) kot(data)){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在/u存在且为黑旋转变色{// g// p u// c if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;//parent-_col RED;grandfather-_col RED;}break;}}else // (grandfather-_right parent){// g// u p// cNode* uncle grandfather-_left;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在/u存在且为黑旋转变色{// g// u p// cif (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(itertaor(newnode), true);;}
4、map和set迭代器的模拟实现
上面改造后的红黑树中已经涉及到了迭代器这里我们来模拟实现。
备注
T数据Ref引用Ptr指针Sefiterator本身
4.1模版参数的构成
要想实现同一棵红黑树的复用模版参数的构成极为重要。
之前我们也遇到过相似的情况我们这里的实现方法参看之前。
迭代器的实现中
涉及到了*解引用操作返回的是数据的引用涉及到了-指针操作返回的是数据的地址;涉及到--操作返回的是操作后迭代器本身的位置。
但是以上的行为我们都涉及结点所以结点的数据类型也尤为重要
综上模版参数的构成如下图 4.2begin()和end()的模拟实现 因为是二叉搜索树为了更有顺序所以我们采取的是中序遍历。那么中序遍历Begin就应该是最左结点我们实现的版本中End定义为空是nullptr
ps
而库中的红黑树则是设计了一个哨兵位的头结点
所以我们实现的只是简化版本。
4.3operator* 和 operator-模拟实现 就是正常的运用operator但是operator-和list中讲的一样返回的是地址的原因是为了连续访问连续的operator-会优化成一个-
4.4 operator 和 operator--模拟实现
这里迭代器的和- - 需要分类一下分别是前置- - 、后置- -
前置 因为我们是中序遍历我们访问完自己之后下一个该访问哪一个结点
我们观察任何一棵二叉树都能看出无非是下面两种情况
分如下两种情况重点
右子树为空找孩子是父亲的左的那个祖先节点否则继续往上走直到空nullptr右子树为非空找右子树的最左节点
这一过程有点类似于递归思想但是是非递归实现的
代码实现 前置--
有了上面的思路我们联想一下现在需要看当前位置左子树是否是空。
前置- -就是倒着走同样还是对当前位置分两种情况重点
左子树为空找孩子是父亲的右的那个祖先节点否则继续往上走直到空nullptr左子树为非空找左子树的最右节点 只要前置理解了那么前置- -完全就是前置倒过来走一遍。
后置、后置- -
和之前实现容器的得带器一样我们这里直接复用即可 4.5 operator 和 operator!模拟实现
有了之前封装迭代器的经验这两个的视线还是比较容易得 4.6迭代器代码详解
templateclass T, class Ref, class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;Node* _node;typedef __RBTreeIteratorT, Ref, Ptr Self;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){if (_node-_right nullptr){//找祖先里面孩子是父亲左的那个Node* cur _node;Node* parent cur-_parent;while (parent parent-_right cur){cur cur-_parent;parent parent-_parent;}_node parent;}else{//右子树的最左结点Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}//左为空_node subLeft;}return *this;}Self operator--(){if (_node-_left nullptr){//找祖先里面孩子是父亲Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}else{//左子树的最右结点Node* subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight;}return *this;}Self operator(int){Self tmp(*this);(*this);return tmp;}Self operator--(int){Self tmp(*this);--(*this);return tmp;}bool operator!(const Self s) const{return _node ! s._node;}bool operator(const Self s) const{return _node s._node;}
};三封装map和set
有了上面的红黑树的改装我们这里的对map和set的封装就显得很得心应手了。
封装主要是把map和set的基本操作封装在一个类中。
map的封装
templateclass K, class V
class map
{//定义一个内部类struct MapKeyOfT{const K operator()(const pairK, V kv)//operator() 可以像函数一样去使用{return kv.first;}};public:typedef typename RBTreeK, pairK, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, pairK, V, MapKeyOfT::const_iterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}pairiterator, bool insert(const pairK, 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, pairK, V, MapKeyOfT _t;
};这里map中的operator[ ]我们知道其原理之后模拟实现就非常方便直接调用插入函数控制好参数和返回值即可。
对set的封装
templateclass K
class set
{struct SetKeyOfT{const K operator()(const K key)//operator() 可以像函数一样去使用{return key;}};
public://加上typename告诉编译器这是个类型类模板实例化了再去取typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;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){//pairtypename RBTreeK, K, SetKeyOfT::iterator, bool ret _t.Insert(key);auto ret _t.Insert(key);return pairiterator, bool(iterator(ret.first._node), ret.second);}iterator find(const K key){return _t.Find(key);}private:RBTreeK, K, SetKeyOfT _t;
};附详细代码——》红黑树封装map和set
