成都网站优化排名推广,知名网站建设联系电话,软件开发公司专业的有哪些,建设网站的需求分析文章目录 前言1. 对之前实现的红黑树进行一些补充和完善1.1 析构1.2 查找 2. STL源码中map和set的实现3. 改造红黑树封装map和set3.1 红黑树结构修改3.2 map、set的结构定义3.3 insert的封装3.4 insert测试3.5 发现问题并解决3.6 红黑树迭代器实现3.7 封装set和map的迭代器并测… 文章目录 前言1. 对之前实现的红黑树进行一些补充和完善1.1 析构1.2 查找 2. STL源码中map和set的实现3. 改造红黑树封装map和set3.1 红黑树结构修改3.2 map、set的结构定义3.3 insert的封装3.4 insert测试3.5 发现问题并解决3.6 红黑树迭代器实现3.7 封装set和map的迭代器并测试3.8 map的[]重载3.9 元素可以修改的问题解决 4. 代码展示4.1 RBTree.h4.2 Map.h4.3 Set.h4.4 Test.cpp 前言 前面的文章我们学习了红黑树也提到了CSTL中的map和set的底层其实就是用的红黑树来实现的而map和set的使用我们前面也学过了。 既然红黑树我们也学习过了那这篇文章我们就用红黑树来简单实现一下STL中的map和set重点是学习它的框架。 1. 对之前实现的红黑树进行一些补充和完善
上一篇文章我们实现了红黑树但是我们实现的那个类并不是特别完善所以为了后面map和set的模拟实现我们先对之前写的那个红黑树的类做一些补充和完善。
1.1 析构
构造函数的话其实不写也没事我们给了缺省值但是析构的话有必要写一下因为我们的红黑树是涉及资源管理的。
我们来实现一下 二叉树的销毁我们之前也有讲过走一个后序遍历销毁就行了 代码很简单我就不解释了 1.2 查找
那红黑树的查找呢我们上一篇文章有提到但是当时没写因为就跟搜索二叉树的查找一样嘛。
那这里由于后面我们要用红黑树模拟实现map和set它们是有find这个接口的的缘故所以我们也补充一下 直接上代码 2. STL源码中map和set的实现
那在正式实现之前我们先一起来看一下STLSGI版本中map和set的源码大致了解一下库里面是怎么实现的。
我们先来看一下map的源码: 由于源码里面内容比较多我们这里不需要全部都看所以我这里有选择性地提取一些内容给大家看 先来看这些 我们看到它的底层这个成员变量其实就是一棵红黑树当然他这里面红黑树的类在另一个头文件里面实现后面也会带大家看它里面的一些内容 然后我们继续 我们之前说过map其实就对应搜索树的KV模型那其实这里的key_type和value_type就对应的是Key和Value的的类型我们看到这里面的key_type就是key但是value_type却是一个pair。 可以按我们之前的理解map里面存的就是一个pair键值对嘛pair的first对应keysecond对应value。 但是它里面为什么value的类型就是一个pair呢 那先不急我们后面会解释。 然后我们再来看一下set 首先set的底层也是红黑树这没什么说到我们都知道但是我们会发现map和set底层用的是同一个红黑树的类模板。 但是它们不是一个对应KV模型一个对应K模型嘛那我们想的可能是应该实现两个红黑树一棵存Key的单个值另一棵存KV的键值对然后用这两棵红黑树分别封装map和set。 那它这里是如何做到map和set底层都用同一个红黑树的类模板呢
观察set的结构我们会发现 set的里面虽然存的是单个值可它除了有key_type之外也有value_type但是set里面的key_type和value_type都是Key的typedef所以相当于传来两个key。 当然从表面上来看他之所以这样做的原因是他和map用的是同一个红黑树的类模板而这个类模板是有两个参数的所以它必须传两个。 那红黑树为什么要这样设计呢所以我们再来观察一下红黑树的实现 这里这个node_count其实就是记录了结点的数量这个map和set需要获取size的时候就很方便不需要再去遍历计数了。 然后下面这个link_type这个类型其实就是结点的指针这个header代表啥我们可以先不管。 然后我们看到红黑树这里的模板参数是固定的前两个模板参数是key和value而红黑树结点里面放的其实就是value 所以它们这里这两个模板参数的传递是这样的 这样如果是set那红黑树的结点里面存的就是key如果是map那红黑树的结点里面存的就是pair的键值对。 所以这里第二个模板参数value接收的什么就决定了红黑树结点里面存的是什么类型的数据。 那问题来了第一个模板参数的作用是啥 大家想一下map和set都有finderase这些接口那它们有什么不同 对于set来说它的查找是不是就是按结点里面存的那个key去查找的啊返回的是对应元素的迭代器。 而map呢 它里面存的是KV的键值对但是它查找的时候是不是只拿K去查找啊因为key是唯一的而value其实是可以重复的。 而map的查找返回的是整个pair的迭代器其实还是结点里面元素的迭代器map里面存的就是pair嘛。 所以我想大家现在应该就明白第一个模板参数Key是干嘛的了 因为map里面存的是KV的键值对但是查找这些操作的时候是以K为目标去查找的所以红黑树里面要多搞出来一个参数Key来单独获取这个Key。 那其实对于set来说是不需要的因为set里面存的就是单独一个key,查找也是用的key上面我们也看了它传的前两个模板就是一样的都是key但是因为你set要和map共用一个红黑树模板所以你必须迎合这个红黑树的结构也去多传一个。 当然其实map也可以不用第一个参数查找的时候用pair.first就行了但是set里面只存了一个key它可找不来什么first的东西所以红黑树才要增加一个模板参数这样红黑树里面的finderase这些函数就可以以一种统一的实现即都用第一个模板参数接收的key去查找这样map和set才可以共同复用同一个红黑树的模板类。 当然它们只是共用了同一个类模板而已最后实例化出来的还是不同的类对象但是这不就正是模板出现的主要意义嘛实现代码的复用对我们程序员来说还是方便了很多的。
那源码呢我们就先看到这里接下来我们就来自己尝试模拟实现一下其实就是去对红黑树进行一个封装嘛。 后面有需要我们再来看相应的源码。
3. 改造红黑树封装map和set
3.1 红黑树结构修改
先要封装的话首先我们得对我们之前自己实现得红黑树做一些改造。
首先结点的结构我们可以不用改虽然我们的跟库里面源码不太一样 我们这里就还用我们直接写到就可以只是实现方式不同这里没什么影响。 那红黑树的结构我们就需要修改一下了 因为我们当时是按照K模型实现的只有一个模板参数 所以要加一个至于这里为什么需要两个上面已经解释过了 这里我们就用KT大家知道代表什么就行了就对应上面源码中红黑树的前两个模板参数嘛。 当然源码里面红黑树不止这两个模板参数但我们不用管有的我们不需要加有的有需要的话我们后面再加。 3.2 map、set的结构定义
那然后我们来创建一个头文件先把map的结构简单定义一下 因为map里面pair的键key不能修改所以我们加一个const库里面也是这样搞的。 然后写一下set的 3.3 insert的封装
先来看map 其实还是复用红黑树的Insert当然之前我们学过map和set的使用它们insert的返回值其实是一个pair嘛当然只是插入一个元素的那个版本大家可以去看一下文档或复习一些之前文章 那我们这里先这样写后面需要的时候再结合具体场景修改。 然后set 也是一样 3.4 insert测试
我们分别对map和set插入一些数据试一试 然后呢 我们运行程序看起来是正常的当然我们并没有打印出来看但是这里面其实是存在问题的。 3.5 发现问题并解决
什么问题呢 我们前面实现的红黑树是K模型的里面的插入就是按照结点里面的data去比较的 但是现在map和set都是复用这棵红黑树所以data里面可能是单独一个key那就是set实例化的时候也可能是一个pair那就对于map。 那set肯定没问题因为set对应的就是K模型。 那map的时候呢map的data里面就是存的pair的键值对那pair也是可以比较大小我们直接也说过所以这里没有报错。 但是pair比较大小的方式是不是不是我们想要的啊。 而map里面元素的比较我们是不是期望只按照那个key也就是pair.first比较啊 那我们怎么去解决这个问题啊 那这个地方库里面的做法是比较不错的我们可以来学习一下 再来看源码里面红黑树的结构 大家看第三个参数的作用是啥后面那个compare就是控制比较方式大家有兴趣可以自己后面写一下 这里参数其实就是为了解决这个问题而引入的它接收一个仿函数。 我们来实现一下先来看map我们就可以这样解决 写一个仿函数取出pair里面的first 这个仿函数接收一个pair返回里面的first。 然后对于set其实是不需要的但是为了匹配因为它们用了同一个红黑树模板所以也要写一个 然后把这个仿函数传给RBTree的第三个模板参数这样在红黑树里面我们不需要管data是单独的key还是pair类型的数据都可以用一个统一的方式拿到真正用了比较的那个单独的key。 那涉及到比较的地方都需要我们改一下我这里就不全部截图出来了我最后会把完整的代码放出来。 然后大家可以看一下这个图理解一下 那这个问题我们就解决了 3.6 红黑树迭代器实现
那接下来我们来实现一下迭代器实现好之后也可以测试一下我们上面插入之后到底对不对。
迭代器我们重点实现红黑树的map和set直接复用就行了库里面源码也是这样搞的。
那红黑树的迭代器呢其实就是结点指针的封装跟我们之前学的list的迭代器差不多 那在这里我们控制const迭代器以及重载-这个运算符其实用的方法都和之前list一样通过增加模板参数去控制大家遗忘的话可以复习一下list那里相关的实现下面我就直接写了有些地方就不过多解释了 那我们先来定义一下它的结构 里面其实就是封装一个结点的指针 然后常见的几个成员函数实现一下 那红黑树的类模板里面这样写就行了 上面这些东西都不难跟之前学的list里面的是一样的相信大家都能看懂我就不解释了。 然后我们写一下迭代器的begin和end吧 首先说一下我们下面的实现和库里面有所不同库里面其实稍微麻烦一点我们后面也会提到但大家按照我们这里讲的实现就行。 那大家想一下begin返回的是啥 在这里是不是应该返回指向中序遍历第一个结点的迭代器啊。 而中序遍历的第一个结点不就是整棵树最左边的那个结点嘛。 那就是这样 那end呢 返回中序遍历最后一个结点的下一个 那最后一个结点后面就没有元素了啊所以我们直接用空构造一个迭代器返回就行了 那const版本的begin和end我们也直接写一下 另外这里稍微有点挑战的就是和- -的重载这两个重载之后我们就可以使用迭代器遍历红黑树了后面封装好就是遍历map和set那我们来讲一下 其实这里相当于我们要搞出一种新的遍历二叉树的方式之前我们学了递归和利用栈的非递归的方式。 首先的重载 大家想一下最开始迭代器it在1这个结点的位置它是中序遍历第一个嘛那怎么样让它就能走到下一个中序遍历的结点上呢 其实不论it当前在那个位置我们都可以认为它在当前所处的这棵子树的根结点上那么根结点访问完中序遍历的话下面访问什么 跟访问完了是不是要访问右子树啊。 那对于右子树来说如果它不为空的话同样要对它进行中序所以it下面要访问的就是it的右子树的最左结点 当然要注意这里前提是右子树不为空 那如果是右为空的情况呢 访问完6然后6的右为空那下一个是谁 大家想中序遍历是左、根、右嘛。那66访问完了6的右为空那是不是相当于6这棵树访问完了。 那6又是1的右子树左、根、右那是不是就是1这棵子树访问完了。 然后1的话是它的父亲8的左子树所以1这棵树访问完就相当于8的左子树访问完了那下面是不是就要访问根结点8了。 所以如果右为空的话我们就应该往上去判断it是不是它父亲的左子树如果不是就顺着父亲指针往上走是的话停下来此时这个父亲就是下一个要访问的结点。 所以我们这种方法的前提是三叉链如果不是三叉链的话那就要用我们之前讲的那种借助栈的非递归遍历方法了。 那后续就按照这个逻辑一直走就行了。 那这样最后一个结点27遍历完27的右为空判断它和它父亲的关系不是父亲的左继续往上走判断一直走到根结点13也不符合然后13的父亲是空就结束了 所以可以认为end在这个位置 代码 最后返回一下之后的迭代器。 然后再来搞一下- -map和set的迭代器是双向迭代器 那大家思考一下- -要怎么走 其实就是跟的反过来就行了中序是左子树、根、右子树那- -就右子树、根、左子树就行了 那这样反过来的话就是先判断it的左子树为不为空不为空就访问左子树的最右结点如果左为空那就要向上去找it是谁的右子树找到的话当前it的这个父亲就是下一个要访问的结点。 如果大家去看源码的话会发现它的实现跟我们有一些不同 他给这棵红黑树增加了一个头结点 头结点的左指针指向最左结点中序第一个头结点的右指向最右结点然后它的parent指向根结点根结点的parent指向这个头结点 然后其它地方其实跟我们的实现是差不多的。 那他的end就指向这个头结点就不为空。 大家有兴趣可以看一下它这个实现但是按我们上面写的就可以了当然库里面的实现在某些地方会比我们的好一些我们这样实现的话如果对end–的话其实就会有问题因为我们的end使用空nullptr构造的就没法向前寻找前一个结点因此最好的方式是将end()放在头结点的位置当然其它位置的是没问题的。 不过问题不大我们重点还是学习它的底层框架。 然后反向迭代器大家有兴趣可以自己搞一下前面我们也讲过怎么弄这里就不写了。
3.7 封装set和map的迭代器并测试
那红黑树的迭代器实现的差不多了我们就可以用它封装set和map的迭代器了。
先来搞一下set 其实就是在set里面封装一个begin和end也是去调红黑树的就行了set里面的迭代器其实本质就是红黑树迭代器的一个typedef。 那我们运行一下代码看看 没有问题是升序。 再来一组 没问题。 那有了迭代器就可以用范围for了 那然后我们再来封装一下map的迭代器并测试一下 这就好了 测试一下 没问题。 然后范围for 也是可以的。 3.8 map的[]重载
那map与set不同的是不是他还重载了[]啊这个我们之前在map和set的使用那篇文章也讲过。
那我们接下来就来实现一下map的【】 那通过前面的学习我们知道map重载的[]底层的实现是跟insert的返回值有关系的所以我们得修改一下红黑树的insert 应该让它返回一个pair 当插入成功的时候pair的first为指向新插入元素的迭代器second为true当插入失败的时候其实就是插入的键已经存在了那它的first为容器中已存在的那个相同的等效键元素的迭代器second为false。 所以后面这个bool其实是标识插入成功还是失败。 这都是之前讲过的。 改造一下 那map和set里面insert的封装我们也要改一下 其实把返回值改一下就行了 然后就可以给map重载[]了 那这就写好了 我们可以用统计次数那个程序测试一下 没有问题。 3.9 元素可以修改的问题解决
但是我们上面的实现其实还存在一些问题 通过前面的学习我们知道set里面的元素是不能修改的因为底层是搜索树如果可以随意修改的话就会破坏搜索树的关系。 而对于mapkey是不可以修改的不过value可以修改。 但我们现在是可以修改的你看这样他还满足搜索树吗 就不是了。 那如何解决呢 我们可以看一下库里面是怎么解决的 先来看set里面的迭代器 我们看到它里面的普通迭代器和const迭代器都是用的红黑树的const迭代器。 那我们也这样写呗 但是现在会有报错 什么原因呢 大家看 这里_t调用begin返回的是普通迭代器但是现在这个返回值iterator是不是红黑树里面const迭代器的typedef所以这里无法进行类型转换普通迭代器转换为const迭代器就出现了问题。 那我们再来看一下库里面怎么解决的 不过我们看到库里面并没有在这里做处理。 那其实我们要来看一下红黑树里面的这个地方 大家看这里红黑树的迭代器的第三个构造函数。 仔细看一下是拷贝构造吗 不是的大家回忆一下拷贝构造他要求参数必须是当前类同类型对象的引用 而大家看这里 Self才是当前类类型的别名而第三个构造函数的参数是iterator跟Self是不一样的如果它用Self的话那就是拷贝构造了。 而这里iterator一定是普通迭代器类型因为它的后两个参数引用和指针都没有加const而Self的话如果传过来的Ref和Ptr是普通的引用和指针那它就是普通迭代器如果是const修饰的那它就是const迭代器。 所以这里第三个构造函数参数写成iterator的情况下 如果当前__rb_tree_iterator这个迭代器的类模板被实例化成iterator的话那它就是一个拷贝构造了因为这是这个参数就跟类对象的类型匹配了 如果被实例化成这个 即const_iterator的话那它就是一个可以用iterator去构造const_iterator的构造函数了。 那它这里支持了普通迭代器构造const迭代器的话我们上面提到的那个问题是不是就解决了因为单参数的构造函数是可以支持隐式类型转换的这个我们之前学过的。 那大家可能会想既然不能修改那直接让红黑树只实现const迭代器不就行了 这样对于set是可行的但是map也要复用这棵红黑树啊map的key虽然不支持修改但是value是可以修改的。 所以map是要区分普通迭代器和const迭代器的不能像set那样普通迭代器和const迭代器都是用的红黑树的const迭代器。 那现在我们来解决一下 我们也加一个可以支持普通迭代器构造const迭代器的构造函数就行了 这样的话不论你__RBTreeIterator被实例化成了普通迭代器还是const迭代器取决于Ref和Ptr传的是啥我这里都是用普通迭代器去构造你的因为参数是T, T, T* 然后再运行 就不报错了 而且现在就不能修改了 那map要如何解决Key不能修改但是value可以修改的问题呢 那这个我们其实上面已经提到过了 就是传这个模板参数的时候K用const修饰就行了 我们来试一下 second即value是可以修改的 而first即key是不行的。 那我们的map和set的模拟实现就差不多讲到这里其它一些我们这里没实现的东西大家有兴趣的可以自己补充这里我们就不写了。
4. 代码展示
4.1 RBTree.h
#pragma onceenum Colour
{RED,BLACK,
};template class T
struct RBTreeNode
{RBTreeNodeT* _parent;RBTreeNodeT* _left;RBTreeNodeT* _right;T _data;Colour _col;RBTreeNode(const T data):_parent(nullptr), _left(nullptr), _right(nullptr), _data(data), _col(RED){}};template class T, class Ref, class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}//不论__RBTreeIterator被实例化成了普通迭代器还是const迭代器取决于Ref和Ptr传的是啥//我这里都是用普通迭代器去构造的因为参数是T, T, T*__RBTreeIterator(const __RBTreeIteratorT, T, T* it):_node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator(){//如果右不为空下一个访问的是右子树的最左结点if (_node-_right){Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}//右为空往上找it是谁的左子树else{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){//如果左不为空下一个访问的是左子树的最右结点if (_node-_left){Node* subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight;}//左为空往上找it是谁的右子树else{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;}
};template class 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* cur _root;while (cur cur-_left){cur cur-_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}//const版本begin和endconst_iterator begin()const{Node* cur _root;while (cur cur-_left){cur cur-_left;}return const_iterator(cur);}const_iterator end()const{return const_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(data) kot(cur-_data)){parent cur;cur cur-_left;}else if (kot(data) kot(cur-_data)){parent cur;cur cur-_right;}else{return make_pair(iterator(cur), false);}}//走到这里cur为空就是key应该插入的位置cur new Node(data);Node* newNode cur;//链接if (kot(data) kot(parent-_data))parent-_left cur;if (kot(data) kot(parent-_data))parent-_right cur;//链接父亲指针cur-_parent parent;//如果插入之后它的parent是红的就需要进行调整while (parent parent-_col RED){Node* grandfather parent-_parent;//如果父亲是祖父的左孩子那右孩子就是叔叔if (parent grandfather-_left){Node* uncle grandfather-_right;//这里处理的情况是叔叔存在且为红变色向上继续处理if (uncle uncle-_col RED){//将p,u改为黑g改为红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//更新cur为grandfather判断它的父亲是什么情况//1.如果不存在或者为黑就需要继续处理了也不会进行循环了//2.如果它的父亲存在且为红重新循环进行调整cur grandfather;parent cur-_parent;}else//叔叔不存在/叔叔存在且为黑的情况{// 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;grandfather-_col RED;}//这里调整完就可以break了因为颜色都变的合适了而相关的链接关系旋转会帮我们处理break;}}//如果父亲是祖父的右孩子那左孩子就是叔叔else //parent grandfather-_right{Node* uncle grandfather-_left;//这里处理的情况是叔叔存在且为红if (uncle uncle-_col RED){//将p,u改为黑g改为红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//更新cur为grandfather判断它的父亲是什么情况//1.如果不存在或者为黑就需要继续处理了也不会进行循环了//2.如果它的父亲存在且为红重新循环进行调整cur grandfather;parent cur-_parent;}else{if (cur parent-_right)//右右——左单旋变色{// g// u p// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else//右左——右左双旋变色{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}//上面处理过程中有可能会把根变成红色这里统一处理一下把根置成黑_root-_col BLACK;return make_pair(iterator(newNode), true);}void InOrder(){_InOrder(_root);cout endl;}bool IsBlance(){if (_root _root-_col RED){cout 根结点是红色 endl;return false;}//先求出一条路径黑色结点数量int mark 0;Node* cur _root;while (cur){if (cur-_col BLACK)mark;cur cur-_left;}//检查是否出现连续红色结点及所有路径黑色结点数量是否相等return _Check(_root, 0, mark);}int TreeHeight(){return _TreeHeight(_root);}Node* find(const T data){KeyOfT kot;Node* cur _root;while (cur){if (kot(data) kot(cur-_data)){cur cur-_left;}else if (kot(data) kot(cur-_data)){cur cur-_right;}else{return cur;}}return nullptr;}~RBTree(){_Destroy(_root);_root nullptr;}
private:void _Destroy(Node* root){if (root nullptr)return;_Destroy(root-_left);_Destroy(root-_right);delete root;}int _TreeHeight(Node* root){if (root nullptr)return 0;int RightH _TreeHeight(root-_left);int leftH _TreeHeight(root-_right);return RightH leftH ? RightH 1 : leftH 1;}bool _Check(Node* root, int blackNum, int mark){if (root nullptr){//走到空就是一条路径走完了比较一下是否相等if (blackNum ! mark){cout 存在黑色结点数量不相等 endl;return false;}return true;}if (root-_col BLACK)blackNum;if (root-_col RED root-_parent-_col RED){cout 出现连续红色结点 endl;return false;}return _Check(root-_left, blackNum, mark) _Check(root-_left, blackNum, mark);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_data ;_InOrder(root-_right);}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//旋转并更新_parent指针parent-_right subRL;if (subRL)subRL-_parent parent;//先保存一下parent-_parent因为下面会改它Node* pparent parent-_parent;//旋转并更新_parent指针subR-_left parent;parent-_parent subR;//若pparent为空则证明旋转的是一整棵树因为根结点的_parent为空if (pparent nullptr){//subR是新的根_root subR;_root-_parent nullptr;}//若pparent不为空则证明旋转的是子树parent上面还有结点else{//让pparent指向子树旋转之后新的根if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}//同时也让新的根指向pparentsubR-_parent pparent;}}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;//旋转并更新_parent指针parent-_left subLR;if (subLR)subLR-_parent parent;//先保存一下parent-_parent因为下面会改它Node* pparent parent-_parent;//旋转并更新_parent指针subL-_right parent;parent-_parent subL;//若parent等于_root则证明旋转的是一整棵树这也是一种判断方法if (parent _root){_root subL;_root-_parent nullptr;}else{//让pparent指向子树旋转之后新的根if (parent pparent-_left){pparent-_left subL;}else{pparent-_right subL;}//同时也让新的根指向pparentsubL-_parent pparent;}}private:Node* _root nullptr;
};4.2 Map.h
#pragma once#include RBTree.hnamespace yin
{template class K, class Vclass map{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V operator[](const K key){pairiterator, bool ret _t.Insert(make_pair(key, V()));return ret.first-second;}pairiterator,bool insert(const pairconst K, V kv){return _t.Insert(kv);}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};void test_map1(){mapstring, string dict;dict.insert(make_pair(sort, 排序));dict.insert(make_pair(left, 左边));dict.insert(make_pair(right, 右边));dict.insert(make_pair(string, 字符串));dict.insert(make_pair(insert, 插入));dict.insert(make_pair(erase, 删除));dict.insert(make_pair(erase, 删除));mapstring, string::iterator it dict.begin();while (it ! dict.end()){cout it-first : it-second endl;it;}cout endl;/*for (auto e : dict){cout e.first : e.second endl;}*/}void test_map2(){string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 香蕉 };mapstring, int m;for (auto e : arr){m[e];}for (auto e : m){cout e.first : e.second endl;}}
}4.3 Set.h
#pragma once#include RBTree.hnamespace yin
{template class Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_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;};void test_set1(){int arr[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };setint s1;for (auto e : arr){s1.insert(e);}setint::iterator it s1.begin();while (it ! s1.end()){cout *it ;it;}/*for (auto e : s1){cout e ;}*/cout endl;}
}4.4 Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include iostream
using namespace std;
#include Map.h
#include Set.h
#include setint main()
{//yin::test_set1();yin::test_map1();return 0;
}
