【C++取经之路】红黑树封装set

目录

前言

红黑树的结构

红黑树的结点定义

红黑树的迭代器

红黑树

封装set

前言

本文参考《STL源码剖析》中SGI STL对红黑树的结构设计，涉及到红黑树迭代器的实现等，所以在读这篇文章之前，我希望你对红黑树有一定的了解，比如在红黑树插入时的变色和旋转操作，最好自己实现过。不然这篇文章对你可能不太友好，因为本文对红黑树的结构设计较为复杂，插入时的操作细节不会在本文详细说明。说实话，封装set对其实很简单，难点在于前期的红黑树设计上，在设计上的一些细节还是很有挑战的。下面我们进入正题，一起领略写SGI STL的大佬们的风采。

红黑树的结构

在这一模块下，我们先从上帝视角来看看到底要实现出怎样的红黑树，以便我们脑海里有个认知。

其中，header节点就是一个很巧妙的设计，它与根结点互为对方的父节点，这看起来是不是挺奇怪呀？没关系。 也就是说header的父节点是_root，_root的父节点是header。同时，header的左右指针分别指向最左节点和最右结点，也就是分别指向最小值和最大值。为了与根节点_root区分，header的颜色为红色。我们在插入节点的时候需要维护指向最左和最右节点的两个指针，确保它们的正确性。不要害怕，这两个指针维护起来并不困难。后面我们再说为什么要引入header。

红黑树的结点定义

enum Color{RED, BLACK};template <class Value>
struct RBTreeNode
{RBTreeNode<Value>* _left;RBTreeNode<Value>* _right;RBTreeNode<Value>* _parent;//旋转时需要访问父节点Color _color;//颜色Value _value;//数据域RBTreeNode(const Value& value = Value()):_left(nullptr), _right(nullptr), _parent(nullptr),_color(RED), _value(value){}
};

红黑树的迭代器

这里大家就要注意了，我们已经进入关键地带了。首先，红黑树的迭代器是双向迭代器，既要支持++，也要支持--。当然除了前进和后退操作，还有蛮多的功能需要我们实现。下面就开始吧！

template <class Value, class Ref, class Ptr>
struct RBIterator
{typedef RBIterator<Value, Ref, Ptr> Self;typedef RBTreeNode<Value> Node;Node* _node;RBIterator(Node* node) :_node(node){}
}

上面是我们实现迭代器功能的基础，我解释一下。

先解释三个模板参数，Value是数据的类型，Ref是数据类型的引用，Ptr是指向数据的指针。例如数据类型为int，Value就是int，Ref即为int&，Ptr为int*。   _node就是红黑树的节点，迭代器与红黑树之间就是靠这个节点建立起联系的。知道当前指向红黑树的哪一个结点，我们才知道下一步给去到哪。所以需要为迭代器传入红黑树的结点。

迭代器++

不管前进还是后退，迭代器依据的都是二叉搜索树的规则，再加上实现上的技巧，所谓的技巧指的就是引入的header结点。这个稍后会详细说明。现在回到迭代器的前进问题，我们知道，红黑树的遍历方式是中序遍历，因为当我们通过迭代器遍历红黑树时，得到的是有序序列。中序遍历的顺序是：左子树 根 右子树。我们要实现的迭代器的遍历方式也是按照 左子树 根 右子树 去走的。下面我结合图形来分析重点。

假设迭代器当前指向结点8，现在迭代器要往下一个结点走。

我们要时刻牢记：左子树 根 右子树 是我们要的顺序。当前迭代器指向结点8，说明以结点8为根的子树的左子树已经访问结束，根节点正在被我们访问，下一个就要去到它的右子树了。记住我们的顺序是左子树 根 右子树。

好，8的右子树不为空，我们往里走，来到结点11，此时我们能直接访问11吗？当然不能！因为以11为根节点的树的左子树我们都还没访问，怎么就轮到根呢？我们的顺序是左子树 根 右子树呀。所以此时我们往11结点的左子树走，发现11结点的左子树为空，这时我们才可以访问根节点11。那么，我们下一步是不是该往11的右子树走了？是的，一点没错！但我们往里走时发现11的右子树为空，此时说明以11为根节点的子树我们都已按照预想访问完毕。我们下一步从节点11回到节点8，也就是说从8的右子树回到节点8,说明以8为根节点的子树我们已经访问完毕，下一个节点时13……

我讲了那么多，希望你能记住，每到达一个节点，都要先考虑它的左子树，如果左子树不为空，就访问左子树，访问完左子树了才能访问根，最后访问右子树，从右子树回到根结点的那一刻，说明当前的子树全部访问完毕。知道了这一点足够了，不必去纠结上面的细节了，来，我们马上进入代码，看看它的细节，这时该纠结就纠结吧！

//因为要说的比较多，就不写注释了，我在代码下方另做解释
Self& operator++()
{if (_node->_right != nullptr){Node* node = _node->_right;while (node->_left != nullptr)node = node->_left;_node = node;}else{Node* parent = _node->_parent;while (parent->_right == _node){_node = parent;parent = _node->_parent;}if (_node->_right != parent)//最难理解的部分，这与红黑树的设计有关_node = parent;}return *this;
}

迭代器指向的当前结点已被访问，说明它的左子树也已经访问过了，就剩下右子树了。如果当前结点的右子树不为空，则进入。然后一直往左走，别回头，直到走到当前子树的最左结点。为什么？还是那句话，左子树 根 右子树。我们每到一个节点，如果它的左子树不为空，我们就不能直接访问它，要先访问它的左节点，然而，它的左节点左节点也为人父母呀，也就是说左节点也是它所在子树的根，所以我们也还不能访问，一直走到左节点为空为止。如果还是不理解的话，对照着图，按着这规则走一遍就好多了。

如果右子树为空，也就是进入了else语句里。这时我们需要做的就是往回走，边走边回头。如果一个棵树的高度较高，我们在往回走时，回头看去都是我们已经访问的结点，这就需要继续往回走。例如我们从上图的11开始往回走，走到8，回头看(看的是右边)，11我们已经访问过了，所以8继续往回走，走到13，往右一看，发现这些节点我们都还未访问，说明我们应该访问13了，访问完13我们才可以去访问往右看所看到的。记住：左子树 根 右子树。

下面解释else语句中的后两行代码

如果_node为指向header节点， 那么parent就是_root结点。此时不满足while循环的进入条件，所以不会进入循环。如果直接执行_node=parent的话，_node就是指向_root，这是不是很离谱呀？！原本_node是指向end()，即header，++了之后反而回退了。所以需要对这种情况做特殊处理。如果了解红黑树的结构的话也不难想到。

迭代器--

牢牢记住，逆着走的顺序是：右子树 根 左子树。所以，每当我们到达一个节点时，都首先要考虑这个节点是否有右节点，如果有，先访问右节点，在访问根，最后访问左节点。明白了这一点，无论是前进还是好后退，都可以游刃有余。

Self& operator--()
{//特殊处理——与红黑树的结构设计有关if (_node->_color == RED && _node == _node->_parent->_parent)_node = _node->_right;else if (_node->_left != nullptr){Node* node = _node->_left;while (node->_right != nullptr)node = node->_right;_node = node;}else{Node* parent = _node->_parent;while (parent->_left == _node){_node = parent;parent = _node->_parent;}_node = parent;}return *this;
}

在解释上述代码之前，我们先来聊一聊end()的指向。别小看这一问题哈，这里面可大有文章。

首先问大家一个问题，end()应该指向哪里？最大元素？nullptr？

如果end()指向最大元素，那么我们在使用范围for遍历传递begin当end区间时，是访问不到最大元素的，因为规定区间是左闭右开。这就很不合理，所以end()不应该指向最大元素。如果end()指向nullptr，因为红黑树的迭代器是双向迭代器，我们在--end()时就会报错——对空指针进行解引用。SGI STL的做法是将end()指向header，因为header的_rigjht指针指向的是最大节点，--end()时，很容易就可以找到最大节点。所以上述代码首先处理了这种情况。剩下的都是常规情况，就不过多解释了。下面给出红黑树迭代器的完整代码。

template <class Value, class Ref, class Ptr>
struct RBIterator
{typedef RBIterator<Value, Ref, Ptr> Self;typedef RBTreeNode<Value> Node;Node* _node;RBIterator(Node* node) :_node(node){}Ref operator*() { return _node->_value; }Ptr operator->() { return &(_node->_value); }bool operator==(Self& self) { return _node == self._node; }bool operator!=(Self& self) { return _node != self._node; }Self& operator++(){if (_node->_right != nullptr){Node* node = _node->_right;while (node->_left != nullptr)node = node->_left;_node = node;}else{Node* parent = _node->_parent;while (parent->_right == _node){_node = parent;parent = _node->_parent;}if (_node->_right != parent)//最难理解的部分，这与红黑树的设计有关_node = parent;}return *this;}Self operator++(int){Self tmp = *this;++(*this);return tmp;}Self& operator--(){//特殊处理——与红黑树的结构设计有关if (_node->_color == RED && _node == _node->_parent->_parent)_node = _node->_right;else if (_node->_left != nullptr){Node* node = _node->_left;while (node->_right != nullptr)node = node->_right;_node = node;}else{Node* parent = _node->_parent;while (parent->_left == _node){_node = parent;parent = _node->_parent;}_node = parent;}return *this;}Self operator--(int){Self tmp = *this;--(*this);return tmp;}
};

红黑树

这里我只解释如何维护header的left和right指针，剩下的操作也都是红黑树的基本操作，不赘述了。

要维护header的left和right指针，我们只需要在插入时留意：

当新插入节点插入在parent的左边时，如果parent == header->_left，也就是说parent在新节点插入前是最小值，那么在插入新节点后就需要更新header的left。

当新插入节点插入在parent的右边时，如果parent == header->_right，也就是说parent在新节点插入之前是最大值，那么在插入新节点后就需要更新header的right。


template <class Key, class Value, class KeyOfValue>
class RBTree
{typedef RBTreeNode<Value> Node;
public:typedef RBIterator<Value, Value&, Value*> iterator;RBTree() { init(); }pair<iterator, bool> insert(const Value& val){if (_root == nullptr){_root = new Node(val);_root->_color = BLACK;_root->_parent = header;header->_parent = _root;header->_left = header->_right = _root;return make_pair(iterator(_root), true);}Node* cur = _root;Node* parent = nullptr;while (cur){if (KeyOfValue()(val) > KeyOfValue()(cur->_value)){parent = cur;cur = cur->_right;}else if (KeyOfValue()(val) < KeyOfValue()(cur->_value)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(val);cur->_parent = parent;if (KeyOfValue()(parent->_value) > KeyOfValue()(val)){parent->_left = cur;if (parent == header->_left)header->_left = cur;}else{parent->_right = cur;if (parent == header->_right)header->_right = cur;}while (parent && parent != header && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* unclue = grandfather->_right;if (unclue && unclue->_color == RED){parent->_color = BLACK;unclue->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){RotateRight(grandfather);}else{RotateLeft(parent);RotateRight(grandfather);}grandfather->_color = RED;parent->_color = BLACK;break;}}else{Node* unclue = grandfather->_left;if (unclue && unclue->_color == RED){parent->_color = BLACK;unclue->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = cur->_parent;}else{if (parent == grandfather->_right){RotateLeft(grandfather);}else{RotateRight(parent);RotateLeft(grandfather);}parent->_color = BLACK;grandfather->_color = RED;break;}}}_root->_color = BLACK;return make_pair(iterator(cur), true);}iterator begin(){ return iterator(header->_left); }iterator end() { return iterator(header); }void inorder() { _inorder(_root); cout << endl; }Node* Maximum(){ return header->_right;}Node* Minimum(){ return header->_left;}
private:void RotateLeft(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;subR->_parent = parentParent;if (parentParent != header){if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_right = subR;}else{_root = subR;subR->_color = BLACK;subR->_parent = header;header->_parent = subR;}}void RotateRight(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* parentParent = parent->_parent;parent->_parent = subL;subL->_parent = parentParent;if (parentParent != header){if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;}else{_root = subL;subL->_color = BLACK;subL->_parent = header;header->_parent = subL;}}void init(){header = new Node();header->_left = header;header->_right = header;}void _inorder(Node* root){if (root == nullptr)return;_inorder(root->_left);cout << root->_value << " ";_inorder(root->_right);}
private:Node* _root = nullptr;Node* header = nullptr;
};

封装set

set的函数基本是转调底层的红黑树。实现起来就是转调红黑树，所以我这里直接给代码了。


namespace pcz
{template <class Key>class set{struct KeyOfValue{const Key& operator()(const Key& key){return key;}};typedef typename RBTree<Key, Key, KeyOfValue>::iterator iterator;public:pair < iterator, bool> insert(const Key& val){return _rb.insert(val);}void inorder() { return _rb.inorder(); }Key minimum() { return _rb.Minimum()->_value; }Key maximum() { return _rb.Maximum()->_value; }iterator begin() { return _rb.begin(); }iterator end() { return _rb.end(); }private:RBTree<Key, Key, KeyOfValue> _rb;};void test_set(){set<int> s;int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15, 0 };for (auto val : arr){s.insert(val);}s.inorder();cout << s.minimum() << endl;cout << s.maximum() << endl;cout << *s.begin() << endl;}
}

本文到这就结束啦~感谢支持！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/150697.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

网站建设中，常用的后台技术有哪些，他们分别擅长做什么网站平台

网站建设中，常用的后台技术有哪些，他们分别擅长做什么网站平台

PHP、Python、JavaScript、Ruby、Java和.NET各自适用于不同类型的网站平台。以下是对这些编程语言适用场景的具体介绍&#xff1a; PHP Web开发&#xff1a;PHP是一种广泛使用的开源服务器端脚本语言&#xff0c;特别适合Web开发。全球有超过80%的网站使用PHP作为服务器端编程语…
阅读更多...
SuperMap GIS基础产品FAQ集锦(20240923)

SuperMap GIS基础产品FAQ集锦(20240923)

一、SuperMap iDesktopX 问题1&#xff1a;请问一下&#xff0c;桌面11i导入功能好像有bug&#xff0c;shp导入到pg库中丢数据&#xff0c;明明60多万条但是导入进去只剩13万条了&#xff0c;这个哪位同事能处理一下呢 11.2.0 【问题原因】2个问题原因&#xff1a;1、序列已…
阅读更多...
两张图讲透软件测试实验室认证技术体系与质量管理体系

两张图讲透软件测试实验室认证技术体系与质量管理体系

软件测试实验室在申请相关资质认证时&#xff0c;需要建立一套完整的质量管理体系和过硬的技术体系。这其中涉及到的要素非常繁杂&#xff0c;工作量非常庞大&#xff0c;为了帮助大家快速梳理清楚软件测试实验室认证过程中质量管理体系和技术体系的建设思路&#xff0c;我们梳…
阅读更多...
HttpServletRequest简介

HttpServletRequest简介

HttpServletRequest是什么&#xff1f; HttpServletRequest是一个接口&#xff0c;其父接口是ServletRequest&#xff1b;HttpServletRequest是Tomcat将请求报文转换封装而来的对象&#xff0c;在Tomcat调用service方法时传入&#xff1b;HttpServletRequest代表客户端发来的请…
阅读更多...
普渡大学和麻省理工学院合作开发集成视触觉指尖传感器的5自由度抓手

普渡大学和麻省理工学院合作开发集成视触觉指尖传感器的5自由度抓手

虽然机器人已经开始在现代制造业、医疗、服务业等领域进行渗透&#xff0c;但对于机器人尤其是机械臂的操作能力&#xff0c;仍然有很大的提升空间&#xff0c;传统多指机器人手虽然能够实现复杂的操作任务&#xff0c;但其高度冗余性也带来了不必要的复杂性。近日来自普渡大学…
阅读更多...
使用Kolors生成图像：从部署到生成

使用Kolors生成图像：从部署到生成

文章目录 1. Kolors模型的背景什么是Kolors&#xff1f;运行Kolors需要的条件 2. 在DAMODEL上准备环境创建计算实例 3. 部署Kolors模型安装Anaconda下载Kolors代码创建虚拟环境并安装依赖 4. 开始生成你的图像5. 个人体验与总结一些建议&#xff1a; 最近我接触到了一个非常有趣…
阅读更多...
【数学分析笔记】第3章第4节闭区间上的连续函数（1）

【数学分析笔记】第3章第4节闭区间上的连续函数（1）

3. 函数极限与连续函数 3.4 闭区间上的连续函数 3.4.1 有界性定理 【定理3.4.1】 f ( x ) f(x) f(x)在闭区间 [ a , b ] [a,b] [a,b]上连续&#xff0c;则 f ( x ) f(x) f(x)在闭区间 [ a , b ] [a,b] [a,b]上有界。 【证】用反证法&#xff0c;假设 f ( x ) f(x) f(x)在 [ …
阅读更多...
【day20240925】常见数据集科普

【day20240925】常见数据集科普

文章目录 常见数据集Fashion-MNISTCIFAR-10CIFAR-100IMDbTiny Imagenet 常见数据集 Fashion-MNIST CIFAR-10 CIFAR-100 IMDb Tiny-ImageNet Fashion-MNIST Fashion-MNIST数据集涵盖了来自 10 种类别的共 7 万个不同商品的正面图片。它的大小、格式和训练集 / 测试集划分与原…
阅读更多...
【AIGC】ChatGPT提示词解析：如何生成爆款标题、节日热点文案与完美文字排版

【AIGC】ChatGPT提示词解析：如何生成爆款标题、节日热点文案与完美文字排版

博客主页&#xff1a; [小ᶻZ࿆] 本文专栏: AIGC | ChatGPT 文章目录 &#x1f4af;前言&#x1f4af;情绪化的吸睛爆款标题提示词使用方法 &#x1f4af;紧跟节日热点生成文案提示词使用方法 &#x1f4af;高效文字排版技巧提示词使用方法 &#x1f4af;小结 &#x1f4af…
阅读更多...
揭秘“隐形杀手”：谐波对医院电网的隐形危害

揭秘“隐形杀手”：谐波对医院电网的隐形危害

谐波主要由非线性负载设备如医疗器械、节能照明、变频调速装置等产生。在医院的复杂配电网络中&#xff0c;这些谐波成分如同细小的波纹&#xff0c;不断叠加&#xff0c;最终扰乱了电能的纯净性&#xff0c;导致电能品质下降&#xff0c;电力供应的可靠性也随之降低。 医院里…
阅读更多...
IO相关流

IO相关流

IO流 一、C语言的输入与输出1、介绍2、输入输出缓冲区&#xff08;1&#xff09;介绍&#xff08;2&#xff09;示意图 二、流1、介绍2、主要特点 三、CIO流1、介绍2、示意图 四、iostream1、介绍2、基本概念3、注意 五、类型转换1、operator bool&#xff08;1&#xff09;介绍…
阅读更多...
Hi.Events —— 您的全方位活动管理与票务平台

Hi.Events —— 您的全方位活动管理与票务平台

大家好&#xff01;今天给大家介绍一个超厉害的开源项目&#xff1a;Hi.Events&#xff0c;这是一个功能丰富的自托管活动管理和票务平台&#xff0c;无论是会议还是俱乐部活动&#xff0c;它都能帮你轻松搞定&#xff01; 项目介绍 Hi.Events是一款功能丰富、自托管的开源活动…
阅读更多...
Vue3: readonly与shallowreadonl

Vue3: readonly与shallowreadonl

目录 一.readonly 1.性质 2.作用 二.shallowReadonly 1.性质 2.作用 三.readonly 四.shallowReadonly 五.运行代码 Vue3中的readonly和shallowReadonly是两个用于创建只读响应式对象的函数。 一.readonly 1.性质 readonly函数会将一个对象或数组包装成一个完全只读…
阅读更多...
vant Uploader 文件上传 修改上传icon样式

vant Uploader 文件上传 修改上传icon样式

修改前 <van-uploader :after-read"afterRead" :max-count"1" upload-icon"plus"/>.van-icon {font-size: 25px !important;color: #929292; }修改后 完结
阅读更多...
ubuntu重新安装clickhouse

ubuntu重新安装clickhouse

1.卸载clickhouse 关闭原来的clickhouse sudo systemctl stop clickhouse-server 查看关闭clickhouse是否成功 sudo systemctl status clickhouse-server 备份配置文件 /etc/clickhouse-server/user.xml /etc/clickhouse-server/config.d/metrika.xml /etc/clickhouse…
阅读更多...
探寻舟山自闭症寄宿制学校：为孩子提供独特的教育和培养

探寻舟山自闭症寄宿制学校：为孩子提供独特的教育和培养

在自闭症儿童教育的广阔天地中&#xff0c;寄宿制学校以其独特的教育模式和生活环境&#xff0c;为孩子们提供了前所未有的成长机遇。舟山&#xff0c;这座美丽的海岛城市&#xff0c;也在积极探索自闭症寄宿制学校的建设与发展&#xff0c;致力于为自闭症儿童打造一片专属的成…
阅读更多...
简单的算法题

简单的算法题

1、求12345 #include <stdio.h> int main(){int i,s1;for(i1;i<5;i){s s*i;}printf("%d",s); }2、求1357911 #include <stdio.h> int main(){int i,s1;for(i1;i<11;ii2){s s*i;}printf("%d",s); }3、判定2000—2500年中的每一年是否…
阅读更多...
虚拟电厂：智慧编织电动汽车新能源管控

虚拟电厂：智慧编织电动汽车新能源管控

一、为什么要搭建虚拟电厂 在当今绿色低碳转型的浪潮中&#xff0c;电动汽车作为未来出行的主力军&#xff0c;其充电行为却悄然成为影响电网安全与经济效益的关键因素。传统模式下&#xff0c;电动汽车的随机充电行为如同电网中的“不速之客”&#xff0c;频繁冲击电网稳定&a…
阅读更多...
Leecode刷题之路从今天开始

Leecode刷题之路从今天开始

前言 众所周知&#xff0c;数据结构算法程序。算法对程序的重要性不言而喻。我们后端研发在写业务代码的时候很容易忽略算法&#xff0c;因此为了加强算法功底&#xff0c;从今日起&#xff0c;决定每日记录Leecode刷题记录&#xff0c;每道题都有相关的demo代码和文档&#x…
阅读更多...
从事新闻、出版、教育、药品和医疗器械、文化、广播电影电视节目等互联网信息服务小程序备案说明

从事新闻、出版、教育、药品和医疗器械、文化、广播电影电视节目等互联网信息服务小程序备案说明

根据《互联网信息服务管理办法》、《非经营性互联网信息服务备案管理办法》规定&#xff0c;从事新闻、出版、教育、药品和医疗器械、文化、广播电影电视节目等互联网信息服务&#xff0c;依照法律、行政法规以及国家有关规定须经有关主管部门审核同意的&#xff0c;在履行备案…
阅读更多...
最新文章

Copyright @ 2022~2023