【C++】基于红黑树的 Map 和 Set 封装及实现过程详述
【C++】基于红黑树的 Map 和 Set 封装及实现过程详述
C++语法 相关知识点 可以通过点击 以下链接进行学习 一起加油！
命名空间 缺省参数与函数重载 C++相关特性 类和对象-上篇 类和对象-中篇
类和对象-下篇 日期类 C/C++内存管理 模板初阶 String使用
String模拟实现 Vector使用及其模拟实现 List使用及其模拟实现 容器适配器Stack与Queue Priority Queue与仿函数
模板进阶-模板特化 面向对象三大特性-继承机制 面向对象三大特性-多态机制 STL 树形结构容器 二叉搜索树
AVL树 红黑树
今天将为大家详细讲解如何基于红黑树封装和实现 Map 和 Set，并深入解析底层逻辑。希望通过这篇文章，能帮助大家在使用 Map 和 Set 类相关接口时更加得心应手。
前言
模拟实现
set
和
map
，
set
和
map
底层结构都是通过红黑树实现的，因此在
set
和
map
中直接分装一棵红黑树，然后将其接口包装下接口。
但是set是属于K搜索模型，而是map是KV搜索模型，对此虽然实现都通过以底层红黑树实现，很明显不是使用同一个红黑树，那么这样子就会很麻烦，而库中的做法是set和map调用同一棵红黑树，那么具体是如何识别set和map的呢？
一、前往底层初步分析
首先，我们去库中找到set和map实现的代码，再将对于讲述这篇内容无关的代码删除，通过画图梳理当前的信息，得到以下这张图片
从图中可以得到一些信息，
_rb<key_type, value_type>
这里第二个模板参数，在set类中是以key 作为
value_type
，而在map是以为
pair<const Key, T>
作为
value_type
，那么可以大致猜测红黑树就是通过
value_type
第二个模板参数去控制set还是map的，需要考虑到红黑树节点储存类型，还有泛型编程等因素，所以map的第二个模板参数为pair<K, V>类型。
二、map第二个参数
问题:为什么map的第二个模板参数为pair<K,V>类型，而不是V类型呢？
2.1 键值对本质
std::map
是一个关联容器，通常是一个有序的二叉搜索树（红黑树实现），其目的是根据键
K
来查找与之对应的值
V
。每个元素都由一个键和值组成，因此，
map
的元素类型被定义为
std::pair<const K, V>
，即一个键值对。
- 键 (
K
)：唯一标识值的标记，不能重复。 - 值 (
V
)：与键相关联的数据，可以修改。
为了保证键的不可变性，
std::pair
中的键类型是
const K
，这样可以避免误修改键，因为修改键会破坏
map
的有序性或查找机制。
2.2 map 的接口设计
std::map
的设计是围绕键值对的存储和查找而设计的。它的内部元素是键值对，并且对这些键值对进行操作时需要涉及到两者的关系。因此，
std::map
的接口与
pair<K, V>
紧密相关
- 插入操作：当你向
map
插入元素时，插入的是一个键值对
std::pair<K, V>
，而不是单独的值。因为要有键才能确定值存储的位置。 - 查找操作：
map.find(key)
会返回一个迭代器，指向的也是一个
std::pair<const K, V>
，表示找到的键值对。 - 迭代操作：当你遍历
map
时，迭代器会指向
pair<const K, V>
，使得你可以访问键和对应的值。 - 就是pair中K是为了跟K取得联系，
std::map
中，值
V
与键
K
是独立的实体。通过将键和值一起存储在
std::pair<K, V>
中，可以有效地让键用于比较和查找操作，而值
V
则保持不变。这种设计保证了当我们执行查找或比较时，只有键会参与这些操作，而不会影响与键关联的值。(理解点在这里了)
2.3 不用 V类型作为第二个模板参数
如果
map
的元素类型只是
V
，那么容器将无法保存键和值的关联关系。原因是：
V
类型只包含值，没有与之相关联的键。
map
需要将键和值配对起来才能进行查找、插入、删除等操作。
map
的查找、插入、删除等操作基于键
K
，而不仅仅是值
V
。
pair<K, V>
才能表示出键和值的完整关系。
2.4 map第二个参数类型不为pair类型
int main()
{
map<string,string> m;
pair<K,V> kv = {"sort"，"排序"}；
m.insert(kv);
}
map类中存储元素是pair<K,V>类型，但是在定义传递给map类类模板参数，由于只要需要K，V是什么，底层存储pair<K,V>类型元素是进行相对应的处理。
三、红黑树内部(map与set构成模板)
将set和map与红黑树相关的图拿出来，进行梳理逻辑，可以清楚的发现他们之间的联系是十分的巧妙的，如果存在多个需要使用同一个类，使用类在类型上有所差异可以将这个类写成模板类，提供不同类型进行使用
3.1 set和map的第一个模板参数会不会多余?
这里红黑树节点元素存储了set和map第二个模板参数，这里实例了两个红黑树只是这件事情是由编译器完成的。这样说明了为什么set需要存储<key,key>键值对，是为了跟map构成模板。
提出这个问题可能是考虑到第二个人模板参数存在了K，为什么还需要第一个模板参数存在，看起来就很多余，对于set而言也许是多余的，但是map而言不是的。map使用Find()和Erase()接口时，不是使用V而是使用K，至于set为什么需要多余一个K呢？因为需要跟map构成模板。
四、修改红黑树实现逻辑
了解上面的分析，对此我们需要修改下红黑树的实现逻辑。
先看看我们之前模拟实现的红黑树
4.1 T代替K，V类型
在节点上通过T来代替了K,V。那么对于红黑树节点以T来接受可能来自set的K或map的pair<K，V>，对此红黑树不知道这里T代表着谁？
4.2 红黑树的插入
这里返回值类型在set和map那篇提及过，如果插入数据存在，为假，返回当前K位置的迭代器，如果插入数据不存，为真，返回插入新K位置的迭代器。
红黑树插入实际上没有多大的改动，插入过程中需要通过搜索树按照K比较找到合适的位置进行插入，现在 _date不知道是K还是pair<K, V>类型，如果按照之前
_kv.first
是不可取的，万一类型是K呢？
既然红黑树内部无法识别类型，但是对于set和map是知道的。这里可以通过使用仿函数其他的用法，之前我们是使用仿函数控制比较大小的逻辑，而这里可以通过使用仿函数来调用对应的数值。
4.3 类模板根据传参调用仿函数
这里仿函数通过一个类来实现，本质也是运算符重载。如果是set的话，就调用set对应的数值，map也是一个道理。但是这里类如何去识别，这里类里面的仿函数是给set还是map使用呢？这里还是十分复杂，可以通过画图来理清楚这里的逻辑，这里由于想使用对应仿函数，而是仿函数在类中实现，那么可以使用类模板根据传参决定使用哪个类的仿函数。(这里可以由外部进行控制传参)
这里set又搞个仿函数出来，得到的还是K。这里是保证泛型编程，也可以理解为同用模板，陪伴太子读书。
4.4 直接比较大小,可行？
问题:这里是不是可以不用这么麻烦，还要设计一个仿函数，为什么需要仿函数去重写行为，直接进行对比，不行吗？，pair不是用比较大小的接口吗？set就K来比较，map就pair调用比较大小的接口不是好了吗?
这里需要搞清楚pair是支持比较，但是不是单纯的去比较，不符合我们的预期。
五、实现迭代器在红黑树中移动
完成上述工作，接下需要实现迭代器
Begin是返回指向首元素的迭代器，End是返回指向最后元素的下一个位置。如果二叉搜索树，最小或首元素在最左边，而最大或最右元素的下一个位置也是nullptr。
5.1 operator++()
如果是++逻辑，以某个节点为起点，这个节点左子树所有节点是小于该节点，右子树所有节点是大于该节点的，这里需要重点关注右子树即可。
首先我们创建二叉搜索树的逻辑是根据中序遍历(左子树 根节点 右子树)的规则，这里需要搞懂两张图或两种情况就可以搞懂如何实现++逻辑了
首先是第一张图:
当前it遍历完了左边，就访问它的父亲。右为空，下一个访问，倒着在祖先里找，找到孩子是父亲左的祖先，也可以这样子想，it这边右子树遍历完了，根据中序遍历(左子树 根节点 右子树)的规则，意味以it父亲节点为根节点的子树全部遍历完了，需要回祖先子树遍历了。
大白话说明:++逻辑就是找下一个大的节点，那么只需要关注右子树就行了。无非就是在建立以为右子树为中心，不断左子树 根这样子的结构递归下去，左子树和根遍历完了，找下一个右子树进行搞。最后遍历完了，cur就是在parent->right位置，不断退出来。
5.2 operator–()
如果是–逻辑，以某个节点为起点，这个节点左子树所有节点是小于该节点，右子树所有节点是大于该节点的，这里需要重点关注左子树即可。
首先我们创建二叉搜索树的逻辑是根据中序遍历(左子树 根节点 右子树)的规则，这里需要搞懂两张图或两种情况就可以搞懂如何实现–逻辑了
Node* operator--()
{
if (current == nullptr) return nullptr;
// Case 1: If there is a left child, move to the rightmost node in the left subtree
if (current->left != nullptr)
{
current = current->left;
while (current->right != nullptr) {
current = current->right;
}
}
// Case 2: If no left child, move up until we find a parent where we are the right child
else
{
Node* parent = current->parent;
while (parent != nullptr && current == parent->left)
{
current = parent;
parent = parent->parent;
}
current = parent;
}
return current;
}
六、红黑树实现的类相关默认成员函数的实现
6.1 红黑树的析构函数
6.2 红黑树的拷贝构造函数
RBTree(const RBTree<T>& other)
{
root = copyTree(other.root, nullptr);
}
private:
// 递归地复制树
Node<T>* copyTree(Node<T>* node, Node<T>* parent)
{
if (node == nullptr)
{
return nullptr;
}
// 创建一个新的节点，并复制数据和颜色
Node<T>* newNode = new Node<T>(node->data, node->color);
newNode->parent = parent;
// 递归复制左子树和右子树
newNode->left = copyTree(node->left, newNode);
newNode->right = copyTree(node->right, newNode);
return newNode;
}
这是一个递归函数，它从源树的根节点开始，递归地遍历并复制每一个节点。
node
是要复制的当前节点，
parent
是新节点的父节点指针。而且节点是在堆上开辟的，递归结束不会销毁。
以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！