【C++】19.红黑树模拟实现 set 和 map

我们想要实现STL中的set和map，那么第一步就需要看一下库函数是如何实现的：
在这里插入图片描述
通过查看源代码我们发现两个容器都包含了stl_tree.h，因此我们猜测此头文件实现的是红黑树。
但是set和map很显然不是使用同一棵树实现的，那么STL库是怎么解决这个问题的呢？

我们发现在构造红黑树的value时map使用的是pair<Key,T>，而set使用的则是Key

在这里插入图片描述

但是为什么在rb_tree类的构造时，要传四个参数呢？
我们知道Value是数据域，那么为什么还有传递Key呢？这难道不是重复了吗？
剩下的两个参数又代表着什么意思呢？
接下来我们的任务就是解决上述的问题。

一、set 和 map 的插入

首先value在插入时非常完美，但是在查找和删除时我们又应如何操作呢？set实现时，可以通过Value来进行操作，但是map实现时，我们有应如何操作呢？提取first元素吗？这样的话传递一个Key类型来方便操作。
接下来我们来实现一下插入部分发现：

if (kv < cur->_kv)
{parent = cur;cur = cur->_left;
}

当我们进行到比较操作的修改时，这个数据如何比较呢？
set的话我们当然可以直接比较，但是map呢？
在这里插入图片描述
通过查阅我们发现不是仅仅按first比较，因此我们需要定义方法来解决这个问题。
我们如何按照我们所预想的情景比较呢？
这样的话我们可以定义一个类来取得想要比较的元素

因此插入部分代码修改如下：

bool Insert(const V& v)
{//根节点为空,那此时插入的节点就是新节点if (_root == nullptr){_root = new Node(v);_root->_col = Black;return true;}KeyOfV kov;//提取key//此时根节点不为空//开始找应该插入的位置Node* cur = _root;Node* parent = cur->_parent;while (cur){if (kov(v) <kov( cur->_v)){parent = cur;cur = cur->_left;}else if (kov(v) >kov( cur->_v)){parent = cur;cur = cur->_right;}elsereturn false;//相等就表示已经存在了}//插入新节点cur = new Node(v);if (kov(v)<kov( parent->_v))parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//红色才修改while (parent&&parent->_col == Red){//取得g节点和u节点Node* grandfather = parent->_parent;Node* uncle = nullptr;//父节点此时为左孩子if (parent == grandfather->_left){uncle = grandfather->_right;}//父节点此时为右孩子else{uncle = grandfather->_left;}//u节点为红色if (uncle && uncle->_col == Red){parent->_col = uncle->_col = Black;grandfather->_col = Red;cur = grandfather;parent = cur->_parent;}//u节点不存在或u节点为黑色else{//父节点是g的左孩子if (parent == grandfather->_left){//cur是父节点的左孩子if (cur == parent->_left){RotateR(grandfather);parent->_col = Black;grandfather->_col = Red;}//cur是父节点的右孩子else{RotateLR(grandfather);cur->_col = Black;grandfather->_col = Red;}break;//调整完此时一定ok}//父节点是g的右孩子else{//cur是父节点的左孩子if (cur == parent->_left){RotateRL(grandfather);cur->_col = Black;grandfather->_col = Red;}//cur是父节点的右孩子else{RotateL(grandfather);parent->_col = Black;grandfather->_col = Red;}break;}}}_root->_col = Black;return true;
}

二、set 和 map 迭代器实现遍历

我们通过查看源代码发现，map和set底层都是通过调用红黑树的迭代器来完成遍历的：
在这里插入图片描述
那么此时我们只需要关注红黑树的迭代器是怎么实现的即可。

而底层的红黑树实现是利用头结点：

我们没有设置头节点，因此在这里简单实现一下：

//红黑树迭代器
template<class V,class Ref,class Ptr>
struct RBTreeIterator
{typedef typename RBTreeNode<V>	Node;//节点typedef typename RBTreeIterator<V, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node,Node* root) :_node(node),_root(root){}//++_nodeSelf& operator++(){Node* cur = _node;if (cur->_right ){Node* LeftMost = cur->_right;while (LeftMost->_left){LeftMost = LeftMost->_left;}_node = LeftMost;}else{Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//--_nodeSelf& operator--(){if (_node == nullptr){Node* RightMost = _root;while (RightMost->_right){RightMost = RightMost->_right;}_node = RightMost;}else{Node* cur = _node;if (cur->_left){Node* RightMost = cur->_left;while (RightMost->_right){RightMost = RightMost->_right;}_node = RightMost;}else{Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}}return *this;}Ref  operator*(){return _node->_v;}Ptr operator->(){return &_node->_v;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};